[Freeciv-Dev] Re: [PATCH] Small improvement at genlist and maphand

[Justin Moore <justin@xxxxxxxxxxx>]

> The 3% doesn't convince me but this one:
> -----------------------------------------------
>                 0.00    0.00     632/8136906     genlist_get [566]
>                 0.34    0.00 8136274/8136906     genlist_iterator_init [42]
> [77]     1.6    0.34    0.00 8136906         find_genlist_position [77]
> -----------------------------------------------
>
> And a lot if not all calls to genlist_iterator_init have a position of
> 0 or -1.  So I would vote for a genlist_iterator_init_from_head and a
> genlist_iterator_init_from_tail.

  The concept of a generic list is a good one, but the implementation is
somewhat poor.  A doubly-linked list runs linearly for essentially every
operation: insertion, deletion, searching, etc.  Plus you need an
iterator.  Attached is code to implement a nearly-identical generic sorted
list function.  Insertion and deletion have an upper bound of O(n), but
tend to gravitate more towards O(lg_2 n).  Searching and iterating are
faster, too.

   I haven't looked over all the cases where the genlist is used, but are
there any cases where data HAS to be in the order it was inserted into the
list?  If not, we could start replacing instances of genlist with sortlist
and see how much that speeds things up.  On an architectual level, there
aren't as many pointer references that could potentially have the CPU
waiting for main memory to get back to it.

   I also welcome people to check over my code to make sure I don't have
any off-by-one errors.  I just wrote this up over the last half-hour, and
I'd hate to have missed some weird insert/deletion case in my haste. :)

-jdm

Department of Computer Science, Duke University, Durham, NC 27708-0129
Email:  justin@xxxxxxxxxxx

sortlist.h
Description: header and macros

sortlist.c
Description: functions