While browsing the SBCL source code I noticed that the hash function used for strings wasn't that good. It's pretty fast (especially considering it's written as pure Lisp, instead of an assembler VOP), but it doesn't actually hash very well. A straightforward implementation of the FNV 1a algorithm (again in Lisp) improved performance in some hashing related benchmarks by 30%, and even the compiler speed benchmark by 5%.

The new algorithm does have one disadvantage; it needs fast multiplication mod 2**32, and that's currently not supported on most platforms that SBCL runs on. I spent a couple of hours trying to properly select the algorithm by checking whether fast multiplication actually exists on the target platform, but doing this turned out to be non-trivial due to the way the build-process works. In the end I settled for just hardcoding it for x86, but even that turned out ugly [#+(not (or (and sb-xc-host !x86) (and (not sb-xc-host) x86)))].

But at least I now have some idea of how building SBCL actually works, so this wasn't a complete waste of time.