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

Groups > linux.kernel > #1390697

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

Show all headers | View raw

On Thu, Apr 28, 2016 at 4:26 PM, Thomas Gleixner <tglx@linutronix.de> wrote:
>
> I'll try to dig up some time to analyze the hash_long failure unless someone
> familiar with the problem is beating me to it.

I'm not sure you need to spend time analyzing failure: if you get bad
hashing with hash_long(), then we know that is a bad hash without
having to really try to figure out why.

It's the hashes that _look_ like they might be good hashes, but
there's not a lot of analysis behind it, that I would worry about. The
simple prime modulus _should_ be fine, but at the same time I kind of
suspect we can do better. Especially since it has two multiplications.

Looking around, there's

    http://burtleburtle.net/bob/hash/integer.html

and that 32-bit "full avalanche" hash in six shifts looks like it
could be better. You wouldn't want to inline it, but the point of a
full avalanche bit mixing _should_ be that you could avoid the whole
"upper bits" part, and it should work independently of the target set
size.

So if that hash works better, it would be a pretty good replacement
option for hash_int().

There is also

    https://gist.github.com/badboy/6267743

that has a 64 bit to 32 bit hash function that might be useful for
"hash_long()".

Most of the people who worry about hashes tend to have strings to
hash, not just a single word like a pointer, but there's clearly
people around who have tried to search for good hashes that really
spread out the bits.

                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