Re: [PATCH] HTB O(1) class lookup

[Andi Kleen <ak@suse.de>]

On Monday 05 February 2007 11:16, Jarek Poplawski wrote:

> 
> Strange - it seems you gave only arguments against this
> analysis...

For a naturally clustered key space (as is common in this case) the two 
level structure is likely more cache efficient than a generic hash function. 
That is because the hash will likely spread out the natural clusters and then require
more cache lines to access them because there will be less sharing.

Ok in theory a very tuned for this case hash function might have similar 
properties, but normally people don't put that much care into 
designing hashes and just use some generic one.

> > And the worst memory consumption case considered by Patrick should
> > be relatively unlikely.
> 
> Anyway, such approach, that most users do something
> this (reasonable) way, doesn't look like good
> programming practice.

In the unlikely worst case they will get half a MB of tables. Hardly a 
show stopper. 

> I wonder, why not try, at least for a while, to do this
> a compile (menuconfig) option with a comment:
> recommended for a large number of classes. After hash
> optimization and some testing, final decisions could be
> made.

There are already far too many obscure CONFIGs. Don't add more.

-Andi