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

[Justin Moore <justin@xxxxxxxxxxx>]

   I'm back.  Long two weeks ...

> > > If I would accept the new version now there would be an improvement
> > > loss. IMHO you should prepare the main code using patches so that the
> > > introduction of the new version will yield an immediate performance
> > > gain.
> >
> >    The sequence of patches in that case would be:
> >
> > 1. Define the STABLE_* iterators to be the current (slow) iterators.
> > 2. Define stable_*_list_iterate to use the new (slow) STABLE_* iterators.
> > 3. Find all the places that will use the new iterators and change them
> >     to the stable_*list_iterate macros.
> > 4. Submit the genlist.[ch] patch.
> >
> >    This will result in an immediate performance gain, but is it worth
> > patching genlist.h first (in step 1), then essentially overwrite the patch
> > in step 4?  I can do this, too, it just seems to have unnecessary steps.
> > I saw it as:
> >
> > 1. Submit genlist.[ch] patch.
> > 2. Change header files to use the stable_*_list_iterate functions.
> > 3. Submit patches for places the use the new iterators.
>
> When and how should I judge what performance this would have? This is
> only possible after step 3. This means you have to submit the
> genlist.[ch] patch and the patch to 3. at the same time so than I can
> judge.
>
> Since I think in the long term the stable iterators should be the norm
> what about this:
>  1. identify all non stable iterators and change them to use another
>  name
>  2. submit a patch to 1.
>  3. submit new genlist.[ch] patch
>
> I can judge easily and even if there is no performance gain (I would
> expect a gain) we have a differentiation between modifying and
> non-modifying iterations.

   I've saved you some of the trouble.  I made the changes myself and ran
the tests.  The results were ... odd.  And somewhat disappointing.  I ran
the test (same codebase) on three different machines.

CPU/Mem      DLL(s)    Array(s)  Speedup(%)
486-66/32     7382      7259       ~2
PII-300/128   579.1     579.2     none
AMD-1200/900  236.7     246.8      ~4

   These were all-AI games with the same .civserverrc on each.  Each was
done with a 'make clean && make' at the top-level to ensure a complete
switch from one to the other.  Each version was run ten times, the high
and low times thrown out, then an average of each.  Approximately 80% of
the old style iterators were converted to the array lists.

   The performance gain is there (kind of), but nowhere near my initial
promises.  I think part of the problem may be due to the fact that the
ITERATOR_* calls are now function calls, but that wouldn't explain the
paltry difference.  I guess gcc just manages to optimize most of the
pointer chasing.

> >    Yes.  Inserting into position '-1' is defined to be inserting into the
> > end of the list.  It is used in several places.
>
> Ok than what about
>
> > > +  if(pos == -1) {
> > > +    pos = pgenlist->nelements;
> > > +  }>
> > > +  if((pos < 0) || (pos > pgenlist->nelements)) {
>       assert(0);
> > > +  }
>
> > > It looks like this branch:
> > > +        if(cp == -1) {
> > > +          iter->curr_data = NULL;  /* Our data disappeared!! */
> > > +          return NULL;
> > > +        } else {
> > > +          iter->curr_pos = cp;
> > > +          iter->curr_data = list->data[cp];
> > > +          return iter->curr_data;
> > > +        }
> > > and this one
> > > +      if(cp == -1) {
> > > +        iter->curr_data = NULL;
> > > +        iter->curr_pos = -1;
> > > +        return NULL;
> > > +      } else {
> > > +        iter->curr_pos = cp;
> > > +        iter->curr_data = list->data[cp];
> > > +        return iter->curr_data;
> > > +      }
> > > are the same/almost the same. Can they be merged?
> > >
> > > It looks like some of the code of genlist_iterator_ptr,
> > > genlist_iterator_next and genlist_iterator_prev can be merged. What
> > > about a "ensure_valid_position" method?
> >
> >    Macros? *shrug* I'll take a look at it.
>
> This can also be a method.

   I just collapsed some of it to make the code cleaner.  Code is
available if there's still any interest in these patches.

> > > IMHO the names STABLE and SAFE should be changed. STABLE means the
> > > list can be used if the iteration won't change something. SAFE means
> > > something other. SAFE should be MODIFYING or so.
> >
> >    I selected SAFE to indicate it was "safe" to mess with it (remove one
> > or more elements from the list, insert stuff into the list, etc).
> > MODIFYING just seems a bit ... unnecessarily verbose. ;p
>
> What about ro (read-only) and rw (read-write)?

   If I submit the patch, I could always just leave the naming up to you.
I think these names are slightly misleading because you can actually
modify the contents of the list, just not the list itself.

-jdm

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