Hi -
My recent foray into gsync left me thinking a bit about its hash function:
#define MIX2_LL(x, y) ((((x) << 5) | ((x) >> 27)) ^ (y))
which seems a bit weak. The result of gsync_key_hash is then taken modulo GSYNC_NBUCKETS, which is currently 512.
libihash has a similar issue. It seems to use no hash function by default, but provides Murmur3 if you want it, which looks better than just shifting bits, but also slower.
I've been looking at the CRC32 instruction, which was introduced ten years ago in SSE 4.2. According to the Intel Software Developer's Manual, CRC32 works like this:
Starting with an initial value in the first operand (destination operand), accumulates
a CRC32 (polynomial 0x11EDC6F41) value for the second operand (source operand)
and stores the result in the destination operand. The source operand can be a
register or a memory location. The destination operand must be an r32 or r64
register. If the destination is an r64 register, then the 32-bit result is stored in the
least significant double word and 00000000H is stored in the most significant double
word of the r64 register.
Agner Fog (
www.agner.org) reports that this instruction executes in a single micro-op.
It seems a bit silly to agonize over performance when we've got so many other issues, but I just wanted to shoot a message to the list to document my research. I'm thinking that CRC32 is our best bet to compute hash functions on the Intel architecture. Of course, it comes with issues like detecting whether the processor supports it.
agape
brent