Re: Extensible hashing and RCU

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

On Sat, Feb 17, 2007 at 04:13:02PM +0300, Evgeniy Polyakov (johnpol@2ka.mipt.ru) wrote:
> > >I noticed in an LCA talk mention that apprently extensible hashing
> > >with RCU access is an unsolved problem.  Here's an idea for solving it.
> > >....
> > 
> > Yes, I have been playing around with the same idea for
> > doing dynamic resizing of the TCP hashtable.
> > 
> > Did a prototype "toy" implementation, and I have a
> > "half-finished" patch which resizes the TCP hashtable
> > at runtime. Hmmm, your mail may be the impetus to get
> > me to finally finish this thing....
> 
> Why anyone do not want to use trie - for socket-like loads it has
> exactly constant search/insert/delete time and scales as hell.

Ok, I've ran an analysis of linked lists and trie traversals and found 
that (at least on x86) optimized one list traversal is about 4 (!) 
times faster than one bit lookup in trie traversal (or actually one
lookup in binary tree-like structure) - that is because of the fact 
that trie traversal needs to have more instructions per lookup, and at 
least one additional branch which can not be predicted.

Tests with rdtsc shows that one bit lookup in trie (actually it is any
lookup in binary tree structures) is about 3-4 times slower than one
lookup in linked list.

Since hash table usually has upto 4 elements in each hash entry,
competing binary tree/trie stucture must get an entry in one lookup,
which is essentially impossible with usual tree/trie implementations.

Things dramatically change when linked list became too long, but it
should not happend with proper resizing of the hash table, wildcards
implementation also introduce additional requirements, which can not be
easily solved in hash tables.

So I get my words about tree/trie implementation instead of hash table 
for socket lookup back.

Interested reader can find more details on tests, asm outputs and
conclusions at:
http://tservice.net.ru/~s0mbre/blog/2007/03/01#2007_03_01

-- 
	Evgeniy Polyakov