Re: Extensible hashing and RCU

[Andi Kleen <andi@firstfloor.org>]

Eric Dumazet <dada1@cosmosbay.com> writes:
> 
> So are you speaking of one memory cache miss per lookup ?

Actually two: if the trie'ing allows RCUing you would save
the spinlock cache line too. This would increase the 
break-even budget for the trie.

> If not, you loose.

It all depends on if the higher levels on the trie are small
enough to be kept in cache. Even with two cache misses it might
still break even, but have better scalability.

Another advantage would be to eliminate the need for large memory
blocks, which cause problems too e.g. on NUMA. It certainly would
save quite some memory if the tree levels are allocated on demand
only. However breaking it up might also cost more TLB misses, 
but those could be eliminated by preallocating the tree in
the same way as the hash today. Don't know if it's needed or not.

I guess someone needs to code it up and try it.

-Andi