Which uses of AVLs need optimzation? A better speedup in some cases should be to replace them with hash tables, splay trees, skip lists or something.
Maybe there is a package out there which has the same interface to several such data structures, so we easily can plug in different ones for different uses and profile the result. (I don't know when the AVLs are used for their worst-case behaviour and when they are just used because AVL is the structure liblutil supports. Or if there is any point in using hash tables with balanced trees for chaining at hash collisions.) If some cases _really_ need optimization, another variant for mostly-constant tables could be to support hash functions loaded as modules: Allow the admin to produce the data, generate a perfect or near-perfect hash function for the keys, then load it and the data:-) -- Hallvard
