Re: Binary tree thoughts...

From: Sammy (samedi@DHC.NET)
Date: 01/07/98

On Tue, 6 Jan 1998, Mark A. Heilpern wrote:

> Chris Jacobson raised an interesting performance question
> the other day - about using binary trees instead of linear
> searches. His example was for the command list, and it is
> probably agree'd that this would be bad because it would
> ruin fine control over command precedence.

If you really want to speed up command lookup without the precedence
drawbacks, just narrow the search by switching on the first letter of the

> However, I wonder how much time in the mud is spent in
> converting vnum's to rnums, which is done by the
> real_[room|obj|mobile]() functions, also using a linear search.
> I haven't profiled my mud (am doing so right now...) but was
> wondering if anyone has profile data that would indicate this
> would or would not be a useful effort?

This is a very useful effort, since I've seen very real performance
problems caused by proto lookups (on a loaded sparc 10).  It wouldn't
require much effort, since you could just copy the stock real_* functions.
I also added a single-vnum cache when I needed to speed up zone resets.
This may sound strange, but on that sparc 10, a certain zone took about a
minute or two to reset on a bad day, which was reduced to 15-20 seconds
with the cache.

> Any other linear searches you can think of in the code that might
> (or might not) benefit from a binary tree?

The player table would greatly benefit from a hash table or binary tree.
A big mud does thousands of strcmp's every time someone connects and
enters a name.


     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | |

This archive was generated by hypermail 2b30 : 12/15/00 PST