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