Re: [1/1 take 2] Unified socket storage. (with small bench).

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

On Wed, May 09, 2007 at 03:02:00AM -0700, David Miller (davem@davemloft.net) wrote:
> From: Evgeniy Polyakov <johnpol@2ka.mipt.ru>
> Date: Wed, 9 May 2007 13:57:40 +0400
> 
> > That is only because we have very different way of working with udp.
> > In udp hash table we can have multiple sockets bound to different ip
> > addresses, but with the same port, so it will be placed into the same
> > hash chain. With trie each socket will have differnet key, since
> > addresses are different (or bound device number), so it automatically
> > fixes problem with broken hash for udp (which is a bit fixed with
> > extended hashing).
> 
> Yes it is power of trie.
> 
> So connection rates are interesting, but what about raw lookup
> performance?  Last time this topic came up you went into some
> cave when you looked at the trie lookup assembly and compared
> it to hash. :)

Sky was bluer and grass was greener that days...
We discussed raw trie with completely different lookup algo (32 bits
keys only, 32 checks per lookup), current implementation (and that one
in previous patchset) is a serious step further.

> It does make more memory references than hash by definition, and we
> need to figure out whether that matters enough or not.

Due to algorithm changes, on each new level we get upto 256 nodes which 
can store a pointer to data, so usual number of lookups should be 3 
(max 4) for the current key organization.
One of the worst cases is when the same source and destination address 
are used, but with different ports (like in shown example), in that case
upto 8 lookups can be performed.
We can even tune key organization to put fields known to be different
first (admin can setup some kind of a policy on bootup/runtime) or
perform non-destructive hashing (exchange bits in the key according to
some law, like change first bit and the last one), which will speedup 
lookup, but that looks more like a ugly mental exercises and should not
be considered in tests for now.

-- 
	Evgeniy Polyakov