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

[Gleb Smirnoff]

On Mon, Oct 13, 2014 at 06:42:11PM +0200, Olivier Cochard-Labbé wrote:
O> > Author: gnn
O> > Date: Fri Oct 10 19:26:26 2014
O> > New Revision: 272906
O> > URL: https://svnweb.freebsd.org/changeset/base/272906
O> >
O> > Log:
O> >   Change the PF hash from Jenkins to Murmur3.  In forwarding tests
O> >   this showed a conservative 3% incrase in PPS.
O> 
O> It's not easy to measure 3% of difference ;-)

However, it is easy to estimate distribution of a hash function. Also
doing the calculation speed test along the way.

I've got very disappointing results with this murmur3 against jenkins.
I am running 87k states just taken from a live system against a 32k
state hash table (which is a default size).

Look at results at the end of email. Guess what -j and -m mean. I
want either proving me doing the test wrong, or backing the change
out ASAP.

The sources for the test attached. First you need to run dump2key
program to store output of 'pfctl -s states' in a binary format.
Then experiment with hashtest. Now dump2key would fail on a IPv6
state. You can either fix that or just filter out IPv6 states.

glebius at think:~/pf/hashtest:|>./hashtest -j ../offcarp1.keys 
0 collisions 2199 hits
1 collisions 6115 hits
2 collisions 8042 hits
3 collisions 7228 hits
4 collisions 4789 hits
5 collisions 2552 hits
6 collisions 1182 hits
7 collisions 466 hits
8 collisions 137 hits
9 collisions 44 hits
10 collisions 12 hits
11 collisions 2 hits
Read 87787 keys, found 87787 keys in hash
Hashes calculation time 8188957 nsec


glebius at think:~/pf/hashtest:|>./hashtest -m ../offcarp1.keys 
0 collisions 23979 hits
1 collisions 4118 hits
2 collisions 1707 hits
3 collisions 691 hits
4 collisions 411 hits
5 collisions 259 hits
6 collisions 231 hits
7 collisions 149 hits
8 collisions 131 hits
9 collisions 124 hits
10 collisions 88 hits
11 collisions 78 hits
12 collisions 58 hits
13 collisions 61 hits
14 collisions 45 hits
15 collisions 39 hits
16 collisions 31 hits
17 collisions 34 hits
18 collisions 28 hits
19 collisions 23 hits
20 collisions 20 hits
21 collisions 18 hits
22 collisions 20 hits
23 collisions 18 hits
24 collisions 10 hits
25 collisions 14 hits
26 collisions 13 hits
27 collisions 14 hits
28 collisions 12 hits
29 collisions 12 hits
30 collisions 13 hits
31 collisions 13 hits
32 collisions 6 hits
33 collisions 10 hits
34 collisions 8 hits
35 collisions 5 hits
36 collisions 9 hits
37 collisions 5 hits
38 collisions 9 hits
39 collisions 5 hits
40 collisions 7 hits
41 collisions 6 hits
42 collisions 11 hits
43 collisions 4 hits
44 collisions 6 hits
45 collisions 5 hits
46 collisions 10 hits
47 collisions 6 hits
48 collisions 3 hits
49 collisions 5 hits
50 collisions 4 hits
51 collisions 4 hits
52 collisions 6 hits
53 collisions 4 hits
54 collisions 7 hits
55 collisions 1 hits
56 collisions 9 hits
57 collisions 2 hits
58 collisions 3 hits
59 collisions 4 hits
60 collisions 2 hits
61 collisions 3 hits
62 collisions 3 hits
63 collisions 2 hits
64 collisions 3 hits
65 collisions 5 hits
67 collisions 2 hits
68 collisions 2 hits
69 collisions 3 hits
70 collisions 3 hits
71 collisions 1 hits
72 collisions 2 hits
73 collisions 1 hits
74 collisions 2 hits
75 collisions 2 hits
76 collisions 1 hits
77 collisions 1 hits
78 collisions 2 hits
79 collisions 2 hits
80 collisions 1 hits
81 collisions 2 hits
82 collisions 1 hits
83 collisions 1 hits
84 collisions 2 hits
85 collisions 3 hits
86 collisions 1 hits
87 collisions 2 hits
88 collisions 1 hits
89 collisions 1 hits
90 collisions 1 hits
91 collisions 2 hits
92 collisions 1 hits
93 collisions 1 hits
95 collisions 2 hits
96 collisions 1 hits
97 collisions 2 hits
98 collisions 1 hits
>99 collisions 74 hits
Read 87787 keys, found 47693 keys in hash
Hashes calculation time 2835154 nsec

-- 
Totus tuus, Glebius.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: pf-hash-testing.tar.bz2
Type: application/octet-stream
Size: 2009 bytes
Desc: not available
URL: <http://lists.freebsd.org/pipermail/svn-src-all/attachments/20141015/d8592fb2/attachment.obj>