Re: my previous post, it seems that one reason for SBCL being so much faster on that code was SXHASH on fixnums. All other [*] implementations (tested: Allegro, ABCL, CLisp, CMUCL, ECL, GCL, Lispworks) seem to just chop off the sign bit from the input, and possibly shift the result a bit. Technically this is sufficient to fulfill what the spec says about SXHASH:

4 The hash-code is intended for hashing This places no verifiable
   constraint on a conforming implementation, but the intent is that
   an implementation should make a good-faith effort to produce
   hash-codes that are well distributed within the range of
   non-negative fixnums

[*] According to Dan Knapp OpenMCL also has a more reasonable fixnum sxhash.

When each non-negative fixnum is mapped to itself, the result is a perfectly even distribution. However, a good hash function should also avoid clustering the hash codes of "nearby" values together. Just like when hashing strings you want the hash codes of short english words written in uppercase to be distributed all over the space of valid codes, the hash codes of 16-bit integers should also be well distributed in the whole code space. Or at least that's how I feel about the matter. Most CL implementors apparently disagree :-)

SBCL attempts to do some mixing of the input bits for all hashing. For fixnums it isn't very thorough, but it was both fast and sufficient for my needs. To make the code portably efficient I'd either need to convince 7 CL vendors to change their SXHASH implementation or use my own hash function. The latter option seems more realistic. Not having time to actually research this, I just threw together a bunch of shifts, xors and adds:

(defun hash (key)
  (declare (type (unsigned-byte 24) key)
  (macrolet ((frob (form)
               `(setf result (logand most-positive-fixnum ,form))))
    (let ((result #x1f3c5a78)) ;; Arbitrary
      (frob (+ result (ash key 10)))
      (frob (logxor result (ash result -6)))
      (frob (+ result (ash key -12)))
      (frob (logxor result (ash result 7)))
      (frob (+ result (ash result -11)))
      (frob (logxor result (ash result 15)))
      (logand most-positive-fixnum result))))

Works for me, probably overkill, use at your own risk.

Update: Actually I wasn't declaring the type of KEY as FIXNUM, but a defined type that expanded to (UNSIGNED-BYTE ...). The code above has been updated to reflect this.