linux-kernel - Re: [PATCH 0/1] Rosebush, a new hash table

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]

Message-ID: <awtiorxst6k5skhzzvrrt5kfhz67cqza2x5acuc7xiejo4sasw@vd6ohpsx76fd>
Date: Sun, 25 Feb 2024 01:14:39 -0500
From: Kent Overstreet <kent.overstreet@...ux.dev>
To: Herbert Xu <herbert@...dor.apana.org.au>
Cc: Matthew Wilcox <willy@...radead.org>, 
	David Laight <David.Laight@...lab.com>, "linux-kernel@...r.kernel.org" <linux-kernel@...r.kernel.org>, 
	Thomas Graf <tgraf@...g.ch>, "netdev@...r.kernel.org" <netdev@...r.kernel.org>, 
	"linux-fsdevel@...r.kernel.org" <linux-fsdevel@...r.kernel.org>, 
	"maple-tree@...ts.infradead.org" <maple-tree@...ts.infradead.org>, "rcu@...r.kernel.org" <rcu@...r.kernel.org>
Subject: Re: [PATCH 0/1] Rosebush, a new hash table

On Sun, Feb 25, 2024 at 01:53:35PM +0800, Herbert Xu wrote:
> On Sun, Feb 25, 2024 at 12:51:06AM -0500, Kent Overstreet wrote:
> >
> > but your distribution actually is accurate in general, golden ratio hash
> > is relly nice for sequential integers. the actual problem with your test
> > is that you're testing 100% occupancy - no one does that.
> > 
> > 75% occupancy, siphash:
> > 0: 933
> > 1: 60
> > 2: 6
> > 3: 1
> > 4: 0
> > 
> > that looks about right to me.
> 
> The point is that the worst-case length grows with the size of
> the table so it won't always be 3.  You need to take into account
> the largest table size that you will support.

ok, but - one million entries, siphash, 75% fill factor

0: 472053
1: 354786
2: 132663
3: 33267
4: 6218
5: 884
6: 110
7: 17
8: 2
9: 0

100 million:

0: 51342703
1: 34224025
2: 11413241
3: 2534946
4: 421816
5: 56271
6: 6346
7: 593
8: 56
9: 3
10: 0

it's a log curve - chain length of 16 means you picked a bad hash
function.