Re: [CODE] Linked List, or Array Table? Fri, Mar 13, 1998 at 11:53:10AM -0000

From: Eric Green (ejg3@CORNELL.EDU)
Date: 03/13/98


On Fri, Mar 13, 1998 at 11:53:10AM -0000, Chris Jacobson wrote:
> This question is sort of directed to Eric Green, but input from others is
> more than welcome.
>
> In my quest to completely C++'ize my MUD, I have been looking at various
> systems for mass data storage/retreival, in particular, queues, arrays,
> hash tables, and linked lists.
>
> I noticed you use a Queue and Hash system in DG, which I found very
> useful, and an educational project to bring it from C to C++, as I got to
> learn more about Hash Tables (I'm starting to grasp their operation...
> its a bit abstract for my normally logical mind - hence my avoidance of
> templates also, but I'm learning :-)
>
> In FL, you use Array and Hash Tables, with Iterators, frequently -
> including in the character lists, descriptor lists, and more.  Did you do
> any profiling, to see if it was more efficient than the current method of
> linked lists?  I would assume it isn't faster, but is far safer, because
> it looks like it can be resilient to having items removed from the array,
> without interfering with higher-up iterations (example: a mob's death
> during it's mobile_activity, resulting in mob->next being the beginning
> of the purged_list, since I converted to the far-safer DG trash
> collection system... to avoid this, I use a stored prev mob, and a stored
> next mob, and if current->next != next, then next = prev->next)

The linked lists in FL would be less efficient for most operations than
Circle's linked lists.  FL's lists are doubly linked lists, so for a few
(rare) operations, FL's lists might be faster than Circle's singlely linked
lists.  Other than that, FL's list manipulations are all done through
functions, where in Circle it all occurs inline.  The function calls,
plus dealing with the extra prev pointer will cause extra overhead.
I've never done any profiling of FL to know any numbers related to these
lists.

If you are using C++, then you could use inline functions to bring the
performance of a list to about the same as Circle's, but with the extra
safety.

The list implementation on FL was done by David Berry, not myself (i wasn't
involved in the FL code until versions after the one available at my site).


Eric


     +------------------------------------------------------------+
     | Ensure that you have read the CircleMUD Mailing List FAQ:  |
     | http://democracy.queensu.ca/~fletcher/Circle/list-faq.html |
     +------------------------------------------------------------+



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