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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Wed, Aug 22, 2001 at 12:25:37PM -0400, Justin Moore wrote:
> 
> > >    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.

These calls to find_genlist_position aren't searches. There are just
function calls. If you inline their usage in TYPED_LIST_ITERATE or
genlist_iterator_init you will see this.

> > 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.

The next IMHO would be to implement genlist_iterator_init_from_head
and genlist_iterator_init_from_tail. These are the functions Markus
used but with another name.

------
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.
------

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "USENET is *not* the non-clickable part of WWW!"