[MUD-Dev] Re: TECH: Distributed Muds

Derek Snider derek at idirect.com
Wed Apr 25 13:02:11 New Zealand Standard Time 2001

> Brian Hook wrote:
> At 11:10 AM 4/21/01 -0600, Chris Gray wrote:
>> That only happens if you have such large linked lists. I've seen
>> discussion here in the last month or two about having global lists
>> containing all of the objects in the world.
> I hope I'm not insulting anyone by stating what may or may not be
> obvious, but linear searches in linked lists are very, very bad.  I
> would assume that even a really badly designed implementation would
> use a data structure far more amenable to searches like a binary
> tree of some sort.
> The only time I would think that a pure linear traversal would be
> necessary is if you had to touch all items, e.g. for storage to
> disk.

All muds in the DikuMUD family traverse the global object list every
"tick" (roughly once per minute) to update the state of all objects.

This includes things like executing a random program associated with
the object (ie: every so often the object does some random thing), as
well as decay timers (objects that "rot").

A special list could be set up for objects that rot, and objects with
programs to avoid traversing the entire global object list.

On a side note, from tests I have done a program can traverse a linked
list of 1,000,000 links in 0.16 seconds on a PII 333Mhz machine
running a mud, webserver, ftp server, etc (90% idle).

Of course the list elements were tiny, but it wasn't to test how well
the virtual memory worked.

MUD-Dev mailing list
MUD-Dev at kanga.nu

More information about the MUD-Dev mailing list