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

[Justin Moore <justin@xxxxxxxxxxx>]

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

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

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

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

-jdm

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

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