Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1391642

Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism

Show all headers | View raw

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

Back to linux.kernel | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

[patch 0/7] futex: Add support for process private hashing Thomas Gleixner <tglx@linutronix.de> - 2016-04-28 18:50 +0200
  [patch 1/7] futex: Add some more function commentry Thomas Gleixner <tglx@linutronix.de> - 2016-04-28 18:50 +0200
  [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-04-28 18:50 +0200
    Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus Torvalds <torvalds@linux-foundation.org> - 2016-04-28 20:40 +0200
      Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-04-29 01:30 +0200
        Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus Torvalds <torvalds@linux-foundation.org> - 2016-04-29 04:30 +0200
          Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-04-30 15:10 +0200
            Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Eric Dumazet <eric.dumazet@gmail.com> - 2016-04-30 18:50 +0200
              Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus Torvalds <torvalds@linux-foundation.org> - 2016-04-30 19:20 +0200
                Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Eric Dumazet <eric.dumazet@gmail.com> - 2016-04-30 19:40 +0200
      Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus Torvalds <torvalds@linux-foundation.org> - 2016-04-29 23:20 +0200
        Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus Torvalds <torvalds@linux-foundation.org> - 2016-04-30 02:00 +0200
          Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Rik van Riel <riel@redhat.com> - 2016-04-30 03:40 +0200
          Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Torvald Riegel <triegel@redhat.com> - 2016-05-02 11:40 +0200
        Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-04-30 17:30 +0200
  [patch 6/7] perf/bench/futex-hash: Support NUMA Thomas Gleixner <tglx@linutronix.de> - 2016-04-28 18:50 +0200
  [patch 3/7] futex: Hash private futexes per process Thomas Gleixner <tglx@linutronix.de> - 2016-04-28 18:50 +0200
  [patch 7/7] perf/bench/futex-hash: Support preallocate hash table Thomas Gleixner <tglx@linutronix.de> - 2016-04-28 18:50 +0200
  [patch 5/7] futex: Add sysctl knobs for process private hash Thomas Gleixner <tglx@linutronix.de> - 2016-04-28 18:50 +0200
  [patch 4/7] futex: Add op for hash preallocation Thomas Gleixner <tglx@linutronix.de> - 2016-04-28 18:50 +0200

csiph-web