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

[Justin Moore <justin@xxxxxxxxxxx>]

> >    A sorted list may not be necessary, but for data with infrequent
> > inserts and frequent searches it is much faster.
>
> Yes. But please show me these "frequent searches".

From gprof-current.txt on civserver:

  1.27    320.44     7.67 120559219     0.00     0.00  find_genlist_position
  0.88    375.77     5.32 120553959     0.00     0.00  genlist_iterator_init
  0.02    591.46     0.14   687196     0.00     0.00  genlist_insert
  0.01    598.71     0.06  2113021     0.00     0.00  genlist_size
  0.00    602.92     0.01    52739     0.00     0.00  genlist_unlink
  0.00    603.16     0.01    16889     0.00     0.00  genlist_unlink_all
  0.00    603.58     0.00    21431     0.00     0.00  genlist_init
  0.00    603.58     0.00     5260     0.00     0.00  genlist_get

   There are ~688K inserts into (up to) ~21K lists, and ~121M searches on
those lists based on how often iterators are initialized.  Searches
outnumber inserts by ~200:1.  And searches on a sortlist are not only
algorithmically faster, but architectually faster.

> I would like to see this too. Maybe you can just rename genlist.[ch]
> to old_genlist.[ch] and change the interface of your sortlist to match
> the one of the old_genlist.

   I was thinking more along the lines of having both genlists and
sortlists.  That way if you wanted a genlist for something like storing
move order, you could, and if you wanted a sortlist for something more
generic you could.

   I won't be able to get this done anytime today (I'm moving to another
state :)) but I'll see if I can get it done during the weekend.

-jdm

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