Re: Extensible hashing and RCU

[Eric Dumazet <dada1@cosmosbay.com>]

On Tuesday 20 February 2007 20:06, Evgeniy Polyakov wrote:

> > I added to my 'simulator_plugged_on_real_server' the average cost
> > calculation, relative to number of cache line per lookup.
> >
> > ehash_size=2^20
> > xor hash :
> > 386290 sockets, Avg lookup cost=3.2604 cache lines/lookup
> > 393667 sockets, Avg lookup cost=3.30579 cache lines/lookup
> > 400777 sockets, Avg lookup cost=3.3493 cache lines/lookup
> > 404720 sockets, Avg lookup cost=3.36705 cache lines/lookup
> > 406671 sockets, Avg lookup cost=3.37677 cache lines/lookup
> > jenkin hash:
> > 386290 sockets, Avg lookup cost=2.36763 cache lines/lookup
> > 393667 sockets, Avg lookup cost=2.37533 cache lines/lookup
> > 400777 sockets, Avg lookup cost=2.38211 cache lines/lookup
> > 404720 sockets, Avg lookup cost=2.38582 cache lines/lookup
> > 406671 sockets, Avg lookup cost=2.38679 cache lines/lookup
> >
> > (you can see that when number of sockets increase, the xor hash becomes
> > worst)
> >
> > So the jenkin hash function CPU cost is balanced by the fact its
> > distribution is better. In the end you are faster.
>
> Very strange test - it shows that jenkins distribution for your setup is
> better than xor one, although for the true random data they are roughly
> the same, and jenkins one has more instructions.
>
> But _you_ have shown that with true random data of 2^16 ports jenkins
> distribution is _worse_ than xor without any gain to buy.

I shown your test was bogus. All your claims are just bogus.
I claim your 'true random data' is a joke. rand() in your program is a pure 
joke.

Given 48 bits of input, you *can* find a lot of addr/port to hit one 
particular cache line if XOR function is used. With jhash, without knowing 
the 32bits random secret, you *cant*.

Again, you dont take into account the chain length.

If all chains were of length <= 1, then yes, xor would be faster. In real 
life, we *know* chain length can be larger, especially in DOS situations.