Subject: Re: Extensible hashing and RCU

From: Evgeniy Polyakov <[email-masked]>
Date: Tue, 20 Feb 2007 15:11:25 +0300

On Tue, Feb 20, 2007 at 12:25:23PM +0300, Evgeniy Polyakov ([email-masked]) wrote:
> 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

I just realized that it is in _BITS_, not in bytes, so typical trie/tree
entry is about 24 bytes - less than one cache line!

-- 
	Evgeniy Polyakov