Re: Extensible hashing and RCU

[Eric Dumazet <dada1@cosmosbay.com>]

On Tuesday 20 February 2007 18:05, Evgeniy Polyakov wrote:
> On Tue, Feb 20, 2007 at 07:59:07PM +0300, Evgeniy Polyakov 
(johnpol@2ka.mipt.ru) wrote:
> > I've attached source code and running script.
> > $ ./run.sh
>
> Yep, of course.

Your test program is just bogus. artefacts come from your 'random' generator.

You just increment a counter, assuming the key you search is not in the table 
yet.

But obviously with only a variation of sport (16 bits), you have a maximum of 
65536 values. No need to feed 100*2^20 values are most of them are dups.

Now if you change your program to do a real lookups with the 2^16 possible 
values of sport you'll see :

jhash function :
1 61578
2 1916
3 42

that is : 61578 chains of length 1
1916 chains of length 2
42 chains of length 3

(for reference, with HASH_FOLD, about same results :
1 61692
2 1856
3 44

Pretty good results... for the gain jhash gives us.

Of course, XOR hash gives a 'perfect' 65536 chains of length 1.