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

Groups > linux.kernel > #1391646

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

Show all headers | View raw

On Sat, Apr 30, 2016 at 9:45 AM, Eric Dumazet <eric.dumazet@gmail.com> wrote:
>
> 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.

So hash_32() really is much better than hash_64(). I think we'll tweak
it a bit, but largely leave it alone.

The 64-bit case needs to be tweaked a _lot_.

For the 32-bit case, I like the one that George Spelvin suggested:

   #define GOLDEN_RATIO_32 0x61c88647      /* phi^2 = 1-phi */

because of his slow multiplier fallback version that we could also use:

  /* Returns x * GOLDEN_RATIO_32 without a hardware multiplier */
  unsigned hash_32(unsigned x)
  {
          unsigned y, z;
                                /* Path length */
          y = (x << 19) + x;      /* 1 shift + 1 add */
          z = (x << 9) + y;       /* 1 shift + 2 add */
          x = (x << 23) + z;      /* 1 shift + 3 add */
          z = (z << 8) + y;       /* 2 shift + 3 add */
          x = (x << 6) - x;       /* 2 shift + 4 add */
          return (z << 3) + x;    /* 3 shift + 4 add */
  }

and I don't think that we really need the several big constants with
the fancy "full cascade" function.

If you have a test-case for that sch_fq.c case, it might be a good
idea to test the above GOLDEN_RATIO_32 value, but quite frankly, I
don't see any way it would be materially different from the one we use
now. It does avoid that long series of zeroes in the low bits, but
that's actually not a huge problem for the 32-bit hash to begin with.
It's not nearly as long a series (or in the wrong bit positions) as
the 64-bit hash multiplier value had.

Also, I suspect that since you hash the kernel "struct sock" pointers,
you actually never get the kinds of really bad patterns that Thomas
had.

But maybe you use hash_32() on a pointer because you noticed that
hash_long() or hash_ptr() (which use hash_64 on 64-bit architectures,
and would have been more natural) gave worse performance?

Maybe you thought that it was the bigger multiply that caused the
performance problems? If you did performance work, I suspect it really
could have been that hash_64() did a bad job for you.

                 Linus

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