netdev - Re: Extensible hashing and RCU

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:	Tue, 20 Feb 2007 11:49:59 +0100
From:	Eric Dumazet <dada1@...mosbay.com>
To:	David Miller <davem@...emloft.net>
Cc:	johnpol@....mipt.ru, akepner@....com, linux@...izon.com,
	netdev@...r.kernel.org, bcrl@...ck.org
Subject: Re: Extensible hashing and RCU

On Tuesday 20 February 2007 11:12, David Miller wrote:
> From: Eric Dumazet <dada1@...mosbay.com>
> Date: Tue, 20 Feb 2007 11:04:15 +0100
>
> > Using a jenkin's hash permits a better hash distribution for a litle
> > cpu cost.  I will post later a distribution simulation based on the
> > data gathered from the same real server.
>
> Actually someone (I think it was Evgeniy in fact) made such
> comparisons and found in his studies that not only does the current
> ehash xor hash function distribute about as well as jenkins, it's
> significantly cheaper to calculate :-)
>
> If you find jenkins is better, great, but I hope it works that
> way for many workloads.

Here are results from real workload :

ehash_addr=0xffff810476000000
ehash_size=1048576
330241 chains, 2441 twchains
Distribution of sockets/chain length
[chain length]:number of sockets
[0]:718335 0%
[1]:223485 42.1436%
[2]:60655 65.0196%
[3]:22451 77.7207%
[4]:11164 86.1416%
[5]:6376 92.1534%
[6]:3236 95.8148%
[7]:1600 97.9268%
[8]:793 99.1231%
[9]:286 99.6085%
[10]:111 99.8178%
[11]:56 99.934%
[12]:20 99.9793%
[13]:4 99.9891%
[14]:2 99.9943%
[15]:2 100%
total : 530294 sockets


Imagine we double hash size (2097152). Distribution would be:
[0]:1698209 0%
[1]:309255 58.3177%
[2]:61638 81.5644%
[3]:18593 92.0829%
[4]:6479 96.97%
[5]:2092 98.9425%
[6]:655 99.6836%
[7]:184 99.9265%
[8]:37 99.9823%
[9]:6 99.9925%
[10]:4 100%

If we use jenkin hash: jhash_3words(daddr, saddr, (dport<<16)|sport, 0);

[0]:632435 0%
[1]:319916 60.328%
[2]:80465 90.6754%
[3]:13816 98.4914%
[4]:1735 99.8001%
[5]:196 99.9849%
[6]:11 99.9974%
[7]:2 100%

-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html