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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Sun, 1 May 2016 10:35:54 +0200 (CEST)
From:	Thomas Gleixner <tglx@...utronix.de>
To:	George Spelvin <linux@...izon.com>
cc:	eric.dumazet@...il.com, linux-kernel@...r.kernel.org,
	riel@...hat.com, torvalds@...ux-foundation.org
Subject: Re: [patch 2/7] lib/hashmod: Add modulo based hash mechanism

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