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

[Justin Moore <justin@xxxxxxxxxxx>]

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

   I rearranged the placement of the iterators and it broke things.  I'm
digging through coredumps trying to find it, but IMHO there's something
pretty broken here.  Not surprising, given the comment near the top of
genlist.h about iterators and placement of said macros. :) The code is
actually quite all right with the current element being removed from under
it.  How odd.

> >    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 my patches, ATM everything is still an array under the hood.  It
just incorporates all the cruft associated with the current set of
ITERATOR_* macros.  I'm open to suggestions on how to cleanly remove
elements from an array without screwing over iterators.  One possibility
that comes to mind is to have an associated array of boolean values which
marks the entry as valid or not.  That way "unlinking" will invalidate the
data, and a sync_list() call will do all the appropriate actual removals.

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

  Yes, but they're pretty much all over the place:

harmony:~/compile/freeciv$ grep -c "ITERATOR_NEXT(myiter)[,)]" \
> `find -name '*.[hc]'` | grep -v :0
./client/gui-gtk/citydlg.c:4
./client/gui-gtk/diplodlg.c:4
./client/gui-gtk/repodlgs.c:1
./client/gui-gtk/spaceshipdlg.c:2
./client/gui-mui/citydlg.c:4
./client/gui-mui/diplodlg.c:3
./client/gui-mui/spaceshipdlg.c:1
./client/gui-xaw/citydlg.c:5
./client/gui-xaw/diplodlg.c:4
./client/gui-xaw/repodlgs.c:1
./client/gui-xaw/spaceshipdlg.c:2
./common/diptreaty.c:2
./common/genlist.c:2
./common/city.c:2
./common/unit.c:1
./common/genlist.h:1
./server/diplhand.c:5
harmony:~/compile/freeciv$

  It'll be a good number of patches.

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

   What about stable_*?  The data in the array is r/w, it's just the
number (and placement) of elements that can't be changed.

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

   Indeed.  I figured some numbers might get people's attention. :)

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

   I'll see what I can do.  I'll be busy on and off for the next week, so
I won't be able to dig into this as much as I had hoped.  Plus this whole
"it's-ok-for-my-current-data-to-disappear" mindset is frustrating. ;p

-jdm

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