[Freeciv-Dev] Re: {gen,spec,sort}list stuff

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Aug 28, 2001 at 12:15:23AM -0400, Justin Moore wrote:
> 
>    In my quest to speed up the list stuff I've been able to categorize the
> different kind of lists and have outlined a plan for migrating things
> over.  But first off, in genlist.h is there any particular reason that the
> TYPED_LIST_ITERATE* macros do an ITERATE_{PREV,NEXT} at the beginning of
> the loop instead of at the end?  In many places in the code it's manually
> done at the end, so there are potential inconsistancies.  The macros
> (essentially) do this:
> 
> while(ITERATOR_PTR(X)) {
>   ITERATOR_NEXT(X);
>   /* Do stuff */
> }

No. It does:

  for(; ITERATOR_PTR(myiter);) {
    var=(atype *)ITERATOR_PTR(myiter);
    ITERATOR_NEXT(myiter);
    /* Do stuff */
  }

So the loop body (if it doesn't look at myiter) will see in the first
pass the first element.

> but many parts of the code do this (manually):
> 
> while(ITERATOR_PTR(X)) {
>   /* Do stuff */
>   ITERATOR_NEXT(X);
> }
> 
>    Anyway, the various lists within the code fall into a few categories:
> 
> 1. Lists that rely heavily on iterators and do nasty things in the middle
>      of iterating such as remove elements from the list (often based on
>      the contents of the iterator).
> 2. Lists that occasionally remove items during iteration, but for the most
>      part are constant.
> 3. Lists for which it is preferable for them to be non-sorted.
> 4. Lists that are initialized at the start of the game and then only
>      searched or the contents updated.
> 
>    Examples of these are:
> 1. Unit lists, private copies of the map, etc
> 2. Connection lists
> 3. Those mentioned in previous e-mails (order in which units are examined,
>      order in which map tiles are looked at by the AI, etc)
> 4. List of diplomatic relations
> 
>    The new genlist API that I've worked on is backwards compatible with
> the old one, and I think it's correct.  I've run a few all-AI games with
> the old and new modules and seen identical results.  

> The underlying data structure for all lists is now a dynamically
> resizeable array, but iterator data structure operations are now
> painfully slow for a few reasons.

Which reasons?

> I've created new macros -- SERIAL_TYPED_LIST_ITERATE* -- that work
> for iterations in which no data is modified.  These would be very
> good for packet_lsend.c and other type 2 lists.

What is the purpose of SERIAL_TYPED_LIST_ITERATE? What are the
differences to a "normal" iteration?

>    "So what's the plan?" you may ask?  In a nutshell:
> 
> - Add SERIAL_TYPED_LIST_ITERATE* macros as serial_{conn,unit,etc}_iterate
>     macros and replace as many simple iteration loops with them as I can.
> - Migrate all the category 4 lists and iterations over to the serial
>     iterators as possible.  Potentially move them over to sortlists later.
> - Beat my head against a wall for all the category 1 lists.
> 
>    I'm not sure of the side-effects of some functions that are calling
> from within city_list_iterate blocks (for example), so this may take a
> while to finish.
> 
> Questions?  Comments?  Flames?

It looks like unit and city lists are in category 1. You plan to do
this category later. However I would assume that these lists would
yield the largest performance gain since they are heavily used.

It looks like you also merge the IMHO independent problems of "is the
list sorted" and "are iterations read only or do they change the
list".

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 Make a software that is foolproof, and only fools will want to use it.