Simon Lodal wrote: > 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.
I agree that the current fixed sized hashes (additionally quite small by default) are a big problem with many classes, for all of HTB/HFSC/CBQ. But I think your approach is a bit wasteful, with unfortunately chosen classids 128 classes are enough to reach the maximum memory usage of ~512kb (with 4k pages and 8 byte pointers). I have a patch for HFSC which introduces dynamic resizing of the class hash. I have planned to generalize it (similar to tcf_hashinfo) and convert HTB and CBQ as well, which as a nice side effect will allow to get rid of some duplicated code, like hash walking. If you give me a few days I'll try to finish and post it. _______________________________________________ LARTC mailing list LARTC@mailman.ds9a.nl http://mailman.ds9a.nl/cgi-bin/mailman/listinfo/lartc
