[Date Prev][Date Next] [Chronological] [Thread] [Top]

Re: Threaded AVL routines



Hallvard B Furuseth wrote:
Which uses of AVLs need optimzation?

At the moment I'm focusing on hdb_dn2idl, which gets very slow in a number of situations because it's doing inefficient searches of the EntryInfo or IDL caches. My thought was that these searches could be replaced by inorder traversals, with some other small tweaks. Just looking for any other possibilities short of the IDL redesign I posted about before.


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:-)
That might be feasible for schema-related lookups, but I don't think it will work out for data or DIT-related lookups.

splay trees might be useful for schema-related lookups as well, because it's pretty typical for an installation to load up far more schema elements than are actually used. But in general I think they have a pretty high search cost....

--
 -- Howard Chu
 Chief Architect, Symas Corp.  http://www.symas.com
 Director, Highland Sun        http://highlandsun.com/hyc
 OpenLDAP Core Team            http://www.openldap.org/project/