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

From	Rik van Riel <riel@redhat.com>
Newsgroups	linux.kernel
Subject	Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism
Date	2016-04-30 03:40 +0200
Message-ID	<rts2Z-7Pi-5@gated-at.bofh.it> (permalink)
References	<rsXiy-6Zu-7@gated-at.bofh.it> <rsXiy-6Zu-11@gated-at.bofh.it> <rsZ10-cC-21@gated-at.bofh.it> <rtnZo-4me-23@gated-at.bofh.it> <rtqud-6qS-3@gated-at.bofh.it>
Organization	linux.* mail to news gateway

Show all headers | View raw

[Multipart message — attachments visible in raw view] - view raw

On Fri, 2016-04-29 at 16:51 -0700, Linus Torvalds wrote:

> There's presumably a few optimal values from a "spread bits out
> evenly" standpoint, and they won't have anything to do with random
> irrational constants, and will have everything to do with having nice
> bitpatterns.
> 
> I'm adding Rik to the cc, because the original broken constants came
> from him long long ago (they go back to 2002, originally only used
> for
> the waitqueue hashing. Maybe he had some other input that caused him
> to believe that the primeness actually mattered.

I do not remember where I got that hashing algorithm and
magic constant from 14 years ago, but the changelog suggests
I got it from Chuck Lever's paper.

Chuck Lever's paper does mention that primeness "adds
certain desirable qualities", and I may have read too
much into that.

I really do not remember the "bit sparse" thing at all,
and have no idea
where that came from. Googling old email
threads about the code mostly
makes me wonder "hey, where
did that person go?"

I am all for magic numbers that work better.

-- 
All Rights Reversed.

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