On 01-02-2007 12:30, Andi Kleen wrote: > Simon Lodal <simonl@xxxxxxxxxx> writes: >> Memory is generally not an issue, but CPU is, and you can not beat the CPU >> efficiency of plain array lookup (always faster, and constant time). Probably for some old (or embedded) lean boxes used for small network routers, with memory hungry iptables - memory could be an issue. > Actually that's not true when the array doesn't fit in cache. > > The cost of going out to memory over caches is so large (factor 100 and more) > that often algorithms with smaller cache footprint can easily beat > algorithms that execute much less instructions if it has less cache misses. > That is because not all instructions have the same cost; anything > in core is very fast but going out to memory is very slow. > > That said I think I agree with your analysis that a two level > array is probably the right data structure for this and likely > not less cache efficient than the hash table. Strange - it seems you gave only arguments against this analysis... > 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. 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. Regards, Jarek P. _______________________________________________ LARTC mailing list LARTC@xxxxxxxxxxxxxxx http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
