[LARTC] [PATCH] HTB O(1) class lookup

[Simon Lodal]

This patch changes HTB's class storage from hash+lists to a two-level linear 
array, so it can do constant time (O(1)) class lookup by classid. It improves 
scalability for large number of classes.

Without the patch, ~14k htb classes can starve a Xeon-3.2 at only 15kpps, 
using most of it's cycles traversing lists in htb_find(). The patch 
eliminates this problem, and has a measurable impact even with a few hundred 
classes.

Previously, scalability could be improved by increasing HTB_HSIZE, modify the 
hash function, and recompile, but this patch works for everyone without 
recompile and scales better too.

The patch is for 2.6.20-rc6, I have older ones for 2.6.18 and 2.6.19 if anyone 
is interested.

Signed-off-by: Simon Lodal <simonl at parknet.dk>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: htb_O(1)_class_lookup.diff
Type: text/x-diff
Size: 11212 bytes
Desc: not available
Url : http://mailman.ds9a.nl/pipermail/lartc/attachments/20070201/475f8a30/htb_O1_class_lookup.bin