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

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

jason

? rc
? old
? topology
? mydiff
? mydiff2
? corecleanup_08.ReadMe
? jasongame-middle3
? topology.c
? client/mapview_common.c
? client/mapview_common.h
Index: common/game.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/game.c,v
retrieving revision 1.111
diff -u -r1.111 game.c
--- common/game.c       2001/10/12 19:48:30     1.111
+++ common/game.c       2001/10/19 12:00:56
@@ -130,13 +130,16 @@
          for (y = 0; y < map.ysize; y++)
            {
              printf ("%d ", y % 10);
-             for (x = 0; x < map.xsize; x++)
-               {
+             for (x = 0; x < map.xsize; x++) {
+               if (is_normal_map_pos2(x, y)) {
                  printf ("%c",
                          (pcmap->claims[map_inx(x,y)].know & (1u << p)) ?
                          'X' :
                          '-');
+               } else {
+                 printf (" ");
                }
+             }
              printf (" %d\n", y % 10);
            }
 
@@ -149,13 +152,16 @@
          for (y = 0; y < map.ysize; y++)
            {
              printf ("%d ", y % 10);
-             for (x = 0; x < map.xsize; x++)
-               {
+             for (x = 0; x < map.xsize; x++) {
+               if (is_normal_map_pos2(x, y)) {
                  printf ("%c",
                          (pcmap->claims[map_inx(x,y)].cities & (1u << p)) ?
                          'O' :
                          '-');
+               } else {
+                 printf (" ");
                }
+             }
              printf (" %d\n", y % 10);
            }
        }
@@ -172,10 +178,13 @@
   for (y = 0; y < map.ysize; y++)
     {
       printf ("%d ", y % 10);
-      for (x = 0; x < map.xsize; x++)
-       {
+      for (x = 0; x < map.xsize; x++) {
+       if (is_normal_map_pos2(x, y)) {
          printf ("%X", pcmap->claims[map_inx(x,y)].whom);
+       } else {
+         printf (" ");
        }
+      }
       printf (" %d\n", y % 10);
     }
 
@@ -188,10 +197,13 @@
   for (y = 0; y < map.ysize; y++)
     {
       printf ("%d ", y % 10);
-      for (x = 0; x < map.xsize; x++)
-       {
+      for (x = 0; x < map.xsize; x++) {
+       if (is_normal_map_pos2(x, y)) {
          printf ("%c", when_char (pcmap->claims[map_inx(x,y)].when));
+       } else {
+         printf (" ");
        }
+      }
       printf (" %d\n", y % 10);
     }
 }
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.100
diff -u -r1.100 map.h
--- common/map.h        2001/10/19 08:12:52     1.100
+++ common/map.h        2001/10/19 12:00:57
@@ -274,6 +274,11 @@
 enum known_type tile_is_known(int x, int y);
 int is_real_tile(int x, int y);
 int is_normal_map_pos(int x, int y);
+/* Determines whether the position is normal given that it's in
+   the range 0<=x<map.xsize and 0<=y<map.ysize.  It's primarily a
+   faster version of is_normal_map_pos since such checks are pretty
+   common. */
+#define is_normal_map_pos2(x, y) (1)
 /*
  * A "border position" is any one that has adjacent positions that are
  * not normal/proper.
@@ -472,9 +477,11 @@
 {                                                                             \
   int WMI_x_itr, WMI_y_itr;                                                   \
   for (WMI_y_itr = 0; WMI_y_itr < map.ysize; WMI_y_itr++)                     \
-    for (WMI_x_itr = 0; WMI_x_itr < map.xsize; WMI_x_itr++)
+    for (WMI_x_itr = 0; WMI_x_itr < map.xsize; WMI_x_itr++)                   \
+      if (is_normal_map_pos2(WMI_x_itr, WMI_y_itr)) {
 
 #define whole_map_iterate_end                                                 \
+      }                                                                       \
 }
 
 /*
Index: server/gamelog.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/gamelog.c,v
retrieving revision 1.14
diff -u -r1.14 gamelog.c
--- server/gamelog.c    2001/01/13 13:43:38     1.14
+++ server/gamelog.c    2001/10/19 12:00:57
@@ -91,7 +91,11 @@
 
   for (y=0;y<map.ysize;y++) {
     for (x=0;x<map.xsize;x++) {
+      if (is_normal_map_pos2(x, y)) {
       hline[x] = (map_get_terrain(x,y)==T_OCEAN) ? ' ' : '.';
+      } else {
+       hline[x] = '#';
+      }
     }
     gamelog(GAMELOG_MAP,"%s",hline);
   }
Index: server/maphand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/maphand.c,v
retrieving revision 1.87
diff -u -r1.87 maphand.c
--- server/maphand.c    2001/10/11 12:37:06     1.87
+++ server/maphand.c    2001/10/19 12:00:58
@@ -301,13 +301,17 @@
       if (pplayer) {
        for (x=0; x<map.xsize; x++) {
          if (map_get_known(x, y, pplayer)) {
+           if (is_normal_map_pos2(x, y)) {
            send_NODRAW_tiles(pplayer, &pconn->self, x, y, 0);
            send_tile_info_always(pplayer, &pconn->self, x, y);
+           }
          }
        }
       } else {
        for (x=0; x<map.xsize; x++) {
+         if (is_normal_map_pos2(x, y)) {
          send_tile_info_always(pplayer, &pconn->self, x, y);
+         }
        }
       }
     } conn_list_iterate_end;
Index: server/savegame.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/savegame.c,v
retrieving revision 1.36
diff -u -r1.36 savegame.c
--- server/savegame.c   2001/10/17 13:16:45     1.36
+++ server/savegame.c   2001/10/19 12:00:59
@@ -68,7 +68,7 @@
                                                         \
   for (y = 0; y < map.ysize; y++) {                     \
     for (x = 0; x < map.xsize; x++) {                   \
-      if (is_normal_map_pos(x, y)) {                    \
+      if (is_normal_map_pos2(x, y)) {                   \
        line[x] = get_xy_char;                          \
         if(!isprint(line[x] & 0x7f)) {                  \
           freelog(LOG_FATAL, "Trying to write invalid"  \
@@ -127,7 +127,7 @@
     }                                                         \
     for(x = 0; x < map.xsize; x++) {                          \
       char ch = line[x];                                      \
-      if (is_normal_map_pos(x, y)) {                          \
+      if (is_normal_map_pos2(x, y)) {                         \
        set_xy_char;                                          \
       } else {                                                \
        assert(ch == '#');                                    \