lkml.org 
[lkml]   [2016]   [Apr]   [30]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
SubjectRe: [patch 2/7] lib/hashmod: Add modulo based hash mechanism
From
Date
On Sat, 2016-04-30 at 15:02 +0200, Thomas Gleixner wrote:

> Yes. So I tested those two:
>
> u32 hash_64(u64 key)
> {
> key = ~key + (key << 18);
> key ^= key >> 31;
> key += (key << 2)) + (key << 4);
> key ^= key >> 11;
> key += key << 6;
> key ^= key >> 22;
> return (u32) key;
> }
>
> u32 hash_32(u32 key)
> {
> key = (key + 0x7ed55d16) + (key << 12);
> key = (key ^ 0xc761c23c) ^ (key >> 19);
> key = (key + 0x165667b1) + (key << 5);
> key = (key + 0xd3a2646c) ^ (key << 9);
> key = (key + 0xfd7046c5) + (key << 3);
> key = (key ^ 0xb55a4f09) ^ (key >> 16);
> return key;
> }
>
> They are really good and the results are similar to the simple modulo prime
> hash. hash64 is slightly faster as the modulo prime as it does not have the
> multiplication.
>
> I'll send a patch to replace hash_64 and hash_32.
>
> Text size:
> x86_64 i386 arm
> hash_64 88 148 128
> hash_32 88 84 112
>
> So probably slightly too large to inline.

I use hash_32() in net/sched/sch_fq.c, for all packets sent by Google
servers. (Note that I did _not_ use hash_ptr())

That's gazillions of packets per second, and the current multiply worked
just fine in term of hash spreading.

Are you really going to use something which looks much slower ?

u32 hash_32(u32 key)
{
key = (key + 0x7ed55d16) + (key << 12);
key = (key ^ 0xc761c23c) ^ (key >> 19);
key = (key + 0x165667b1) + (key << 5);
key = (key + 0xd3a2646c) ^ (key << 9);
key = (key + 0xfd7046c5) + (key << 3);
key = (key ^ 0xb55a4f09) ^ (key >> 16);
return key;
}

Probably having a simple multiple when ARCH_HAS_FAST_MULTIPLIER is
defined might be good enough, eventually by choosing a better
GOLDEN_RATIO_PRIME_32




\
 
 \ /
  Last update: 2016-04-30 19:01    [W:0.035 / U:0.408 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site