On Tue, Feb 20, 2007 at 12:25:23PM +0300, Evgeniy Polyakov ([EMAIL PROTECTED])
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
-
To unsubscribe from this list: send the line "unsubscribe netdev" in
the body of a message to [EMAIL PROTECTED]
More majordomo info at http://vger.kernel.org/majordomo-info.html
