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

[Raimar Falke <hawk@xxxxxxxxxxxxxxxxxxxxxxx>]

On Thu, Oct 18, 2001 at 02:07:24PM -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.
> 
> This seems like a good idea.
> 
> Once new topologies are added, though, we will probably no longer want
> to make it a macro.  At that point we'll be back to the same problem,
> since the function call overhead is the main slowdown.

Yes but this slowdown isn't for noniso-rectangle:

#define IS_NORMAL_MAP_POS2(x,y) map.shape==NONISO_RECTANGLE ? 1 \
      : map.shape==ISO_RECTANGLE ? is_normal_map_pos2_for_iso_rect(x,y):...

        Raimar

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