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

[Jason Dorje Short <vze2zq63@xxxxxxxxxxx>]

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.

jason