svn commit: r272906 - in head/sys: conf libkern netpfil/pf sys

[Gleb Smirnoff]

On Wed, Oct 15, 2014 at 07:04:55AM +0400, Gleb Smirnoff wrote:
T> On Mon, Oct 13, 2014 at 06:42:11PM +0200, Olivier Cochard-Labbé wrote:
T> O> > Author: gnn
T> O> > Date: Fri Oct 10 19:26:26 2014
T> O> > New Revision: 272906
T> O> > URL: https://svnweb.freebsd.org/changeset/base/272906
T> O> >
T> O> > Log:
T> O> >   Change the PF hash from Jenkins to Murmur3.  In forwarding tests
T> O> >   this showed a conservative 3% incrase in PPS.
T> O> 
T> O> It's not easy to measure 3% of difference ;-)
T> 
T> However, it is easy to estimate distribution of a hash function. Also
T> doing the calculation speed test along the way.
T> 
T> I've got very disappointing results with this murmur3 against jenkins.
T> I am running 87k states just taken from a live system against a 32k
T> state hash table (which is a default size).
T> 
T> Look at results at the end of email. Guess what -j and -m mean. I
T> want either proving me doing the test wrong, or backing the change
T> out ASAP.

And now for a generate case, which actually is a practical case. We've
got an internal load balancer, where all connections come from the same
IPs, making the ports only being source of entropy. We've got 198k
states there. And here are results:

glebius at think:~/pf/hashtest:|>./hashtest -m ../node01.apps.keys 
Stat overflow: 144507 -> 99
Stat overflow: 53514 -> 99
Stat overflow: 517 -> 99
0 collisions 32761 hits
1 collisions 1 hits
2 collisions 1 hits
18 collisions 1 hits
44 collisions 1 hits
>99 collisions 3 hits
Read 198603 keys, found 362 keys in hash
Execution time 6164622 nsec

Yes, 144k collisions. Simply a linear search.

Jenkins does good:
glebius at think:~/pf/hashtest:|>./hashtest -j ../node01.apps.keys 
0 collisions 69 hits
1 collisions 465 hits
2 collisions 1393 hits
3 collisions 2829 hits
4 collisions 4205 hits
5 collisions 5231 hits
6 collisions 5405 hits
7 collisions 4613 hits
8 collisions 3360 hits
9 collisions 2371 hits
10 collisions 1357 hits
11 collisions 774 hits
12 collisions 387 hits
13 collisions 177 hits
14 collisions 76 hits
15 collisions 42 hits
16 collisions 11 hits
17 collisions 3 hits
Read 198603 keys, found 198603 keys in hash
Execution time 18564948 nsec

-- 
Totus tuus, Glebius.