Doing some profiling, I noticed that it seems that we spend a fair bit
of time in list_search() on the children of an object while creating and
destroying objects.
There is a good chance for optimization here if we make a change so that
the children list is guaranteed to be sorted by object number. This
isn't that big a change at all. Currently, assuming that objects never
change parents, it will already be sorted. So, the only change would be
that when you change parents, the object isn't added to the end of the
children list, but inserted into the correct position to keep the list
sorted. (Well, it would also have some impact on DB compilation as
well.) If that change was made, then we could use a binary search and
eliminate a lot of computation that isn't strictly necessary. I'll be
doing this modification today, but would like to hear thoughts and
feedback on it. I'm hoping that I'm not missing any obvious problems
with it.
On a side note, I've re-written many parts of lookup.c, including making
it not use DBM any longer but using Berkeley DB. I'm not terribly
inclined to make it optionally support DBM, so if there are objections
to this, I'd like to hear them (along with reasoning). (Offers to make
it work with DBM are welcome and I'd consider patches that did that.)
- Bruce
|