[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
https://www.kanga.nu/lists/listinfo/mud-dev



More information about the MUD-Dev mailing list