On Sun, 1 May 2016, George Spelvin wrote:
> But I noticed a much greater difference.
>
> Wang * PHI % 4093 Wang * PHI % 4093
> 13599486 3494816 5238442 13584166 3460266 5239463
> 13589552 3466764 5237327 13582381 3422304 5276253
> 13569409 3407317 5236239 13566738 3393215 5267909
> 13575257 3413736 5237708 13596428 3379811 5280118
> 13583607 3540416 5325609 13650964 3380301 5265210
>
> At 3.7 GHz, that's
>
> * PHI: 1059 M ops/second
> * Modulo: 706 M ops/second
> * Wang: 271 M ops/second
>
> Of course, that's a tight loop hashing; I presume your test case
> has more overhead.
Indeed.
> Anyway, my recommendation (I'll write the patches if you like) is:
>
> * Modify the multiplicative constants to be
> #define COLDEN_RATIO_32 0x61C88647
> #define COLDEN_RATIO_64 0x61C8864680B583EB
Works for me. I ran them through my test case and they behaved reasonably
well.
> * Change the prototype of hash_64 to return u32.
Makes sense.
> * Create a separate 32-bit implementation of hash_64() for the
> BITS_PER_LONG < 64 case. This should not be Wang's or anything
> similar because 64-bit shifts are slow and awkward on 32-bit
> machines.
> One option is something like __jhash_final(), but I think
> it will suffice to do:
>
> static __always_inline u32 hash_64(u64 val, unsigned int bits)
> {
> u32 hash = (u32)(val >> 32) * GOLDEN_RATIO_32 + (u32)val;
> hash *= GOLDEN_RATIO_32;
> return hash >> (32 - bits);
> }
Works. That's more or less the same overhead as the modulo one, which behaved
well on 32bit.
Thanks,
tglx
