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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Aug 28, 2001 at 02:52:13PM -0400, Justin Moore wrote:
> 
> > > 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.

You could clean up such things with the current genlist implementation.

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

As pointed you: restarting the loop.

> One possibility that comes to mind is to have an associated array of
> boolean values which marks the entry as valid or not.

Complicated.

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

Compare this to 'grep -Irc _iterate .|grep -v _end|grep -v ":0"'.

>   It'll be a good number of patches.

If these instances transform to normal _iterate macros: go.

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

??

        Raimar
-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "That's fundamental game play!  My main enemy is *ALWAYS* fighting 
  a 4-front war.  I make sure of it!"
    -- Tony Stuckey, freeciv-dev