[Freeciv-Dev] Re: PATCH: map iteration (PR#1018)

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Fri, Oct 19, 2001 at 08:11:47AM -0400, Jason Dorje Short wrote:
> Raimar Falke wrote:
> > 
> > On Wed, Oct 17, 2001 at 11:12:34PM -0700, jdorje@xxxxxxxxxxxxxxxxxxxxx 
> > wrote:
> > > There are a lot of places in the code that have loops like
> > >
> > >   for (y=0; y<map.ysize; y++) {
> > >     for (x=0; x<map.xsize; x++) {
> > >       ...
> > >     }
> > >     ...
> > >   }
> > >
> > > These loops will generally not work under a general topology, since they
> > > are intended to loop over only normal, real positions and for many
> > > topologies that will not happen.
> > >
> > > The easy solution is to do an is_normal_map_pos check, as in:
> > >
> > >   for (y=0; y<map.ysize; y++) {
> > >     for (x=0; x<map.xsize; x++) {
> > >       if (is_normal_map_pos(x, y)) {
> > >         ...
> > >       } else {
> > >       <possibly some extra handling>
> > >       }
> > >     }
> > >     ...
> > >   }
> > >
> > > The cleanest example of this is in whole_map_iterate, where the
> > > is_normal_map_pos check can just be added directly.
> > >
> > >
> > > The obvious question with this is efficiency, since we're adding a lot
> > > of extra is_normal_map_pos calls.  I ran a profile of an autogame under
> > > CVS and the patch, and found an increase in is_normal_map_pos calls by 3
> > > million.  By comparison, normalize_map_pos is called 50 million times in
> > > this game.  Of course, since is_normal_map_pos is a frontend to
> > > normalize_map_pos it's a lot slower than it could be.  I anticipate a
> > > 2-4% increase in execution time.
> > >
> > > Aside from the efficiency controversy I'm sure we'll have, this is
> > > pretty boring stuff.
> > 
> > The question is how we can make this faster. What do you think about
> > another method like is_normal_map_pos but this method is called only
> > with map position which are inside the xsize*ysize map.
> > 
> > int is_normal_map_pos2(int x, int y)
> > {
> >   // assert(0<=x<map.size && 0<=y<map.ysize);
> >   return 1;
> > }
> > 
> > int is_normal_map_pos(int x, int y)
> > {
> >   if(x<0||x>=map.xsize || y<0||y>=map.ysize)
> >         return 0;
> >   return is_normal_map_pos2(x,y);
> > }
> > 
> > Make is_normal_map_pos2 a macro and use it in the cases you have
> > touched with your patch and we have no performance impact for the
> > current map.
> 
> New patch attached.  It introduces the is_normal_map_pos2 macro (note
> the lower case; I'm not sure about that), and uses it in place of
> is_normal_map_pos where appropriate (including in the code originally
> changed for this patch plus some savegame.c stuff).

Mhh is_normal_map_pos2 wasn't intended to be the final name. Any
suggestions?

        Raimar

-- 
 email: rf13@xxxxxxxxxxxxxxxxx
 "When C++ is your hammer, everything looks like a thumb."
    -- Steven M. Haflich