Re: Extensible hashing and RCU

[Evgeniy Polyakov <johnpol@2ka.mipt.ru>]

On Mon, Feb 19, 2007 at 07:13:07PM +0100, Eric Dumazet (dada1@cosmosbay.com) wrote:
> On Monday 19 February 2007 16:14, Eric Dumazet wrote:
> >
> > Because O(1) is different of O(log(N)) ?
> > if N = 2^20, it certainly makes a difference.
> > Yes, 1% of chains might have a length > 10, but yet 99% of the lookups are
> > touching less than 4 cache lines.
> > With a binary tree, log(2^20) is 20. or maybe not ? If you tell me it's 4,
> > I will be very pleased.
> >
> 
> Here is the tcp ehash chain length distribution on a real server :
> ehash_addr=0xffff810476000000
> ehash_size=1048576
> 333835 used chains, 3365 used twchains
> Distribution of sockets/chain length
> [chain length]:number of sockets
> [1]:221019 37.4645%
> [2]:56590 56.6495%
> [3]:21250 67.4556%
> [4]:12534 75.9541%
> [5]:8677 83.3082%
> [6]:5862 89.2701%
> [7]:3640 93.5892%
> [8]:2219 96.5983%
> [9]:1083 98.2505%
> [10]:539 99.1642%
> [11]:244 99.6191%
> [12]:112 99.8469%
> [13]:39 99.9329%
> [14]:16 99.9708%
> [15]:6 99.9861%
> [16]:3 99.9942%
> [17]:2 100%
> total : 589942 sockets
>
> So even with a lazy hash function, 89 % of lookups are satisfied with less 
> than 6 compares.

This is only 2^19 sockets.

What you miss is the fact, that upper layers of the tree are always in the
cache. So its access cost nothing compared to every time new entry in
the hash table.

And there is _no_ O(1) - O(1) is just a hash entry selection, then you
need to add the whole chain path, which can be long enough.
For example for the length 9 you have 1000 entries - it is exactly size
of the tree - sum of all entries upto and including 2^9.
One third of the table is accessible within 17 lookups (hash chain
length is 1), but given into account size of the entry - let's say it 
is equal to
32+32+32 - size of the key
32+32+32 - size of the left/right/parent pointer
so 192 bytes per entry - given into acount that 1/4 of the 1-2 MB cache is
filled with it, we get about 1300 top-level entries in the hash, so
about _10_ first lookups are in the cache _always_ due to nature of the
tree lookup.

-- 
	Evgeniy Polyakov