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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Aug 21, 2001 at 12:47:16AM -0400, Justin Moore wrote:
> 
> > 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.

From the same profile:
  1.75      9.29     0.40  8136906     0.00     0.00  find_genlist_position
  1.53     10.36     0.35  8136274     0.00     0.00  genlist_iterator_init
  0.00     22.86     0.00   189229     0.00     0.00  genlist_size
  0.00     22.86     0.00    93733     0.00     0.00  genlist_insert
  0.00     22.86     0.00     5573     0.00     0.00  genlist_init
  0.00     22.86     0.00     1367     0.00     0.00  genlist_unlink_all
  0.00     22.86     0.00     1292     0.00     0.00  genlist_unlink
  0.00     22.86     0.00      632     0.00     0.00  genlist_get

It looks like there are 8136906 genlist iterations at runtime. There
are only 93733 inserts. For the core iteration I would assume your
sortlist is faster.

> struct sortlist_link {
>   void *dataptr;
> };
>
> struct sortlist {
>   int capacity;
>   int num_links;
>   struct sortlist_link *data;
> };

Why not just:?

> struct sortlist {
>   int capacity;
>   int num_links;
>   void *data;
> };

If you remove the extra indirection and the sorting we have a
dynamically sized array. What do you think about this?

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

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "I was dead ... but I'm better now."
    -- Capitain Sheridan in Babylon 5