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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Aug 28, 2001 at 10:27:28AM -0400, Justin Moore wrote:
> 
> > > 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.
> 
>    Yes, I know.  Ok, I left out the variable assignment; I assumed people
> knew the assignment happened along with the ITERATOR_PTR call.  I was just
> using the 'while' construct to visually demonstrate my point about where
> the iterator is advanced.  

> There are places where the iterator is used or passed as a variable
> to another function.  When this is done inside of a macro-based loop
> it might not yield the right results.

Now I see. I consider this broken or at least very ugly.

> In a bit I'm going to change the macro declaration and see what kind
> of effect (if any) it has on a game.  If the code is robust enough
> and correct, it shouldn't matter.  But we'll see. :)
> 
> > > 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?
> 
>    With a doubly-linked list you can remove a list element in front of or
> behind the current element without messing up the iterator.  Providing
> that the pointers 'next' and 'prev' are still correct, the iterators work
> fine.

IMHO such iteration aren't nice. As pointed you these can be
avoided. IMHO this can be preparatory work for the latter replacement
with an array.

>    With an array, I found that I needed to check on each iteration to make
> sure that the data hadn't essentially moved from under me in the process
> of iterating.  A simple index counter won't work.  What I came up with was
> an iterator that stores both an index counter and a pointer to the data
> that index counter *should* point to.  On PREV/NEXT iteration, the
> iterator checks if the list is still valid (itr_data ?= array[itr_index]).
> If so, do the iteration.  If not, find the new index of the data we have
> stored in our iterator, update the counter, then iterate.
> 
>    The second is that short of writing a seven or eight-deep nested (()?:)
> construct, the next and prev iterators have to be functions now.  

> Since ITERATOR_NEXT is often used in the declaration of a for loop,

Can these instances be replaced?

> it has to be one statement, so new scope declarations (or even
> variable declarations) are a no-no.
> 
> > > 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?
> 
>    The serial iteration macros simply iterate through a list, storing the
> current value in the variable name you give it.  They do not use the slow
> iterators, and therefore do no bounds or correctness checking at each
> step.  On the upside, they're very fast.  "Normal" iteration now uses the
> iterator functions and is slower, but can tolerate data being removed from
> the list during iteration.  And (as long as it doesn't become another
> 'is_normalised'-type discussion) I'm up to suggestions for a better name.

Read-only, const(ant), immutable.

> > > - 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.
> 
>    I actually changed my mind about this after I wrote the e-mail. :) I
> found a lot of places where the code was iterating over the cities just
> adding information up (population, light bulbs, etc).  A side-effect of
> having the iterators as functions is that they now show up in a profile.
> After my serialize campaign for the city iterators (by creating a
> serial_city_list_iterate macro), combined with a similar campaign for
> connection lists (ALL of packet_lsend.c can be modified) I was able to cut
> the number of calls to the slower macros in half.  I'm sure there are
> plenty of places where units could be changed over, too.
> 
>    Comparing profiles from the same game (same randseed and mapseed) with
> the current genlist and my new genlist with a few serialized iterations, I
> found (conservatively) a 3-4% speedup overall, even with the old iterators
> as functions.  I still want to double-check the correctness of my
> implementation, but I'm (cross my fingers) pretty confident that it's
> right.  If so, I'm guessing the overall speedup for the server alone would
> be around 8-10%.

This looks like a nice promise.

> > 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".
> 
>    Not really.  I just noted which lists could be potential candidates for
> sorting later.  Right now I'm solely focusing on "what is the best way to
> iterate through this list?" and will worry about the other later.

What do you think about tagging iterations which modify the list
during the iterations. Since I consider the non-changing (serial) case
the normal one I would like to reverse the terminology here. There
would then be two subtasks:
 - replace as much as possible/all calls of changing_city_list_iterate
 to city_list_iterate
 - make a replacement for the normal city_list_iterate and profile it

        Raimar
-- 
 email: rf13@xxxxxxxxxxxxxxxxx
  (On the statement print "42 monkeys"+"1 snake"): BTW, both perl and Python
  get this wrong. Perl gives 43 and Python gives "42 monkeys1 snake", when 
  the answer is clearly "41 monkeys and 1 fat snake".  
    -- Jim Fulton, 10 Aug 1999