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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Tue, Sep 18, 2001 at 12:37:12AM -0400, Justin Moore wrote:
> 
>    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 question is: are these converted iterators the "high volume"
ones?! You have to find iterations which are used a lot.

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

Functions calls can cost you a percent or two. But are function calls
really needed for unchecked access?

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

Before you stop this please post the code.

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

These were just suggestions.

> I think these names are slightly misleading because you can actually
> modify the contents of the list, just not the list itself.

Ack.

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "I was dead ... but I'm better now."
    -- Capitain Sheridan in Babylon 5