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

Groups > linux.kernel > #1391774

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

Show all headers | View raw

On Sat, 30 Apr 2016, George Spelvin wrote:
> Thomas Gleixner wrote:
> You say that
> > hash64 is slightly faster as the modulo prime as it does not have the
> > multiplication.
> 
> Um... are you sure you benchmarked that right?  The hash_64 code you
> used (Thomas Wang's 64->32-bit hash) has a critical path consisting of 6
> shifts and 7 adds.  I can't believe that's faster than a single multiply.

Sorry I did not express myself clear enough.

hash64 (the single multiply with the adjusted golden ratio) is slightly faster
than the modulo one which has two mutiplications.
 
So here is the list:

hash_64(): (key * GOLDEN_RATIO) >> (64 - bits)		31Mio Ops/sec

modulo:	   	  		       	 		28Mio Ops/sec

Thomas Wangs 64 -> 32 bit				21Mio Ops/sec

Thanks,

	tglx

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

Thread

Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism "George Spelvin" <linux@horizon.com> - 2016-04-30 23:00 +0200
  Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-05-01 10:40 +0200
    Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism "George Spelvin" <linux@horizon.com> - 2016-05-01 11:50 +0200
      Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-01 19:00 +0200
      Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism Thomas Gleixner <tglx@linutronix.de> - 2016-05-02 09:20 +0200
        [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-02 12:30 +0200
          [PATCH 2/2] <linux/hash.h>: Fix hash_64()'s horrible collision problem "George Spelvin" <linux@horizon.com> - 2016-05-02 12:30 +0200
            Re: [PATCH 2/2] <linux/hash.h>: Fix hash_64()'s horrible collision problem Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 22:10 +0200
          [RFC PATCH 3/2] (Rant) Fix various hash abuses "George Spelvin" <linux@horizon.com> - 2016-05-02 12:30 +0200
          [RFC PATCH 4/2] namei: Improve hash mixing if CONFIG_DCACHE_WORD_ACCESS "George Spelvin" <linux@horizon.com> - 2016-05-02 12:40 +0200
          Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32  bits Peter Zijlstra <peterz@infradead.org> - 2016-05-02 15:30 +0200
            Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-02 21:10 +0200
          Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 18:30 +0200
            Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-02 22:30 +0200
              Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 23:20 +0200
                Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-02 23:50 +0200
                Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits "George Spelvin" <linux@horizon.com> - 2016-05-03 04:00 +0200
                Re: [PATCH 1/2] <linux/hash.h>: Make hash_64(), hash_ptr() return 32 bits Linus Torvalds <torvalds@linux-foundation.org> - 2016-05-03 05:10 +0200

csiph-web