[Freeciv-Dev] Re: [RFC] square_dxy_iterate

[Jason Short <vze2zq63@xxxxxxxxxxx>]

Raimar Falke wrote:
> On Fri, Feb 22, 2002 at 06:04:45PM -0500, Jason Short wrote:
>
> > Raimar Falke wrote:
> >
> > > > From the profile of an autogame (with disabled CHECK_MAP_POS):
> > > Flat profile:
> > >
> > >
> > > 80695222/2379222=33.916 calls of normalize_map_pos for each call of
> > > invasion_funct. It turns out that square_dxy_iterate is the
> > > problem. And the second one (is_terrain_near_tile) uses adjc_iterate.
> > >
> > > Are there any is_border patches or similar handy which solve this?
> > Ross's corecleanups (kindof) extend the IS_BORDER_POS check to check for 
> > arbitrary (map_dist) distances from the border.  Under the current 
> > topology this is easy; under others it will be less so (but still 
> > doable, plus our definition that IS_BORDER_POS(..)=>FALSE means the 
> > position may or may not be on the border gives us a good default 
> > option).  I'll put together a patch sometime this weekend, I suppose - 
> > it should be quite short.
> Ok.
See attached patch.

I've changed IS_BORDER_MAP_POS to take a distance argument as well. 
This is similar to what Ross's changes do (it uses a more robust check 
for IS_BORDER than is currently used), except I've unified it into one 
macro call, rather than have a
#define IS_BORDER_MAP_POS(x, y) _IS_BORDER_MAP_POS(x, y, 1)

I've also added IS_BORDER checks to all of the iterator macros (why 
not?).  I've taken the liberty of rewriting adjc_iterate in terms of 
square_iterate (which should give identical behavior, aside from the 
addition of the IS_BORDER check).
Since (just about) all of the iterators use a different internal 
notation, the changes may look a bit inconsistent.
In limited testing, this change caused about a 3% increase in server 
time efficiency (i.e. 3% decrease in running time [1]).  This is less 
than I expected (normalize_map_pos accounts for 4.5% of server runtime 
according to the profile, and that doesn't include all of the 
function-call overhead which will also be included in the calling 
function's time) - which probably means there are a lot of normalize 
calls left.
> > Another question to think about here is whether the algorithm of 
> > invasion_funct can be improved.
> Indead. See attached patch.
At a glance it looks like this will not even compile.  Finding pcity is 
the whole purpose for the iteration, so you can't short-circuit the loop 
by checking if the condition on pcity exists.
It _might_ be faster to exchange the square_dxy_iterate for a 
city_list_iterate within a players_iterate.  If the radius of the square 
is sufficiently large (and both of these other iterators are efficient) 
this could be faster - but I wouldn't count on it giving overall better 
results.
<random math>Note, if there are 33 normalize_map_pos calls on average 
then on average the square we're iterating over has size 33.  Without 
profiling, this means it should have an average [2] radius of (under) 
3...which means on an 80x50 map we'll end up hitting the border case 
(under) 6/80 + 6/50 = 2% of the time.  So in the _average_ case, calls 
to normalize_map_pos should drop by about a factor of 50.  But outliers 
will have a very large effect on this value, so it could be pretty 
inaccurate.<random math>
jason

[1] yes, I know 1.03 != 1/0.97, but...

? crash
? diff
? jason-game.gz
? t
? test-alt.pl
? test.pl
? topology
? data/README-isotrident
? data/isoengels
? data/isoengels.tilespec
? data/isotrident
? data/isotrident.tilespec
? data/lexxy
? data/lexxy.tilespec
? data/macroisotrident
? data/macroisotrident.tilespec
Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.121
diff -u -r1.121 map.h
--- common/map.h        2002/02/22 13:14:43     1.121
+++ common/map.h        2002/02/23 11:51:37
@@ -285,12 +285,13 @@
 #define regular_map_pos_is_normal(x, y) (TRUE)
 
 /*
- * A "border position" is any one that has adjacent positions that are
- * not normal/proper.
+ * A "border position" is any one that _may have_ positions within
+ * map distance dist that are non-normal.  To see its correctness,
+ * consider the case where dist is 1 or 0.
  */
-#define IS_BORDER_MAP_POS(x, y)              \
-  ((y) == 0 || (x) == 0 ||                   \
-   (y) == map.ysize-1 || (x) == map.xsize-1)
+#define IS_BORDER_MAP_POS(x, y, dist)                         \
+  ((x) < (dist) || (x) >= map.xsize - (dist)                  \
+   || (y) < (dist) || (y) >= map.ysize - (dist))
 
 bool normalize_map_pos(int *x, int *y);
 void nearest_real_pos(int *x, int *y);
@@ -378,6 +379,8 @@
   int MACRO_min_dx = -MACRO_max_dx - 1 + (map.xsize % 2);                     \
   bool MACRO_xcycle = TRUE;                                                   \
   bool MACRO_positive = FALSE;                                                \
+  bool MACRO_is_border = IS_BORDER_MAP_POS(ARG_start_x, ARG_start_y,          \
+                                           ARG_max_dist);                     \
   int MACRO_dxy = 0, MACRO_do_xy;                                             \
   CHECK_MAP_POS(ARG_start_x, ARG_start_y);                                    \
   while(MACRO_dxy <= (ARG_max_dist)) {                                        \
@@ -402,7 +405,7 @@
        if (MACRO_dx > MACRO_max_dx || MACRO_dx < MACRO_min_dx)               \
          continue;                                                           \
       }                                                                       \
-      if (!normalize_map_pos(&ARG_x_itr, &ARG_y_itr))                         \
+      if (MACRO_is_border && !normalize_map_pos(&ARG_x_itr, &ARG_y_itr))      \
        continue;
 
 #define iterate_outward_end                                                   \
@@ -428,11 +431,12 @@
                            dx_itr, dy_itr)                                    \
 {                                                                             \
   int dx_itr, dy_itr;                                                         \
+  bool _is_border = IS_BORDER_MAP_POS(center_x, center_y, radius);            \
   CHECK_MAP_POS((center_x), (center_y));                                      \
   for (dy_itr = -(radius); dy_itr <= (radius); dy_itr++) {                    \
     for (dx_itr = -(radius); dx_itr <= (radius); dx_itr++) {                  \
       int x_itr = dx_itr + (center_x), y_itr = dy_itr + (center_y);           \
-      if (normalize_map_pos(&x_itr, &y_itr)) {
+      if (!_is_border || normalize_map_pos(&x_itr, &y_itr)) {                 \
 
 #define square_dxy_iterate_end                                                \
       }                                                                       \
@@ -473,23 +477,12 @@
 /* Iterate through all tiles adjacent to a tile */
 #define adjc_iterate(RI_center_x, RI_center_y, RI_x_itr, RI_y_itr)            \
 {                                                                             \
-  int RI_x_itr, RI_y_itr;                                                     \
-  int RI_x_itr1, RI_y_itr1;                                                   \
-  CHECK_MAP_POS(RI_center_x, RI_center_y);                                    \
-  for (RI_y_itr1 = RI_center_y - 1;                                           \
-       RI_y_itr1 <= RI_center_y + 1; RI_y_itr1++) {                           \
-    for (RI_x_itr1 = RI_center_x - 1;                                         \
-        RI_x_itr1 <= RI_center_x + 1; RI_x_itr1++) {                         \
-      RI_x_itr = RI_x_itr1;                                                   \
-      RI_y_itr = RI_y_itr1;                                                   \
-      if (!normalize_map_pos(&RI_x_itr, &RI_y_itr))                           \
-        continue;                                                             \
-      if (RI_x_itr == RI_center_x && RI_y_itr == RI_center_y)                 \
-        continue; 
+  square_iterate(RI_center_x, RI_center_y, 1, RI_x_itr, RI_y_itr) {           \
+    if (RI_x_itr == RI_center_x && RI_y_itr == RI_center_y)                   \
+      continue;
 
 #define adjc_iterate_end                                                      \
-    }                                                                         \
-  }                                                                           \
+  } square_iterate_end;                                                       \
 }
 
 /* Iterate through all tiles adjacent to a tile.  dir_itr is the
@@ -502,7 +495,7 @@
   int MACRO_center_x = (center_x);                                            \
   int MACRO_center_y = (center_y);                                            \
   CHECK_MAP_POS(MACRO_center_x, MACRO_center_y);                              \
-  MACRO_border = IS_BORDER_MAP_POS(MACRO_center_x, MACRO_center_y);           \
+  MACRO_border = IS_BORDER_MAP_POS(MACRO_center_x, MACRO_center_y, 1);        \
   for (dir_itr = 0; dir_itr < 8; dir_itr++) {                                 \
     DIRSTEP(x_itr, y_itr, dir_itr);                                           \
     x_itr += MACRO_center_x;                                                  \
@@ -579,12 +572,14 @@
 {                                                      \
   int IAC_i;                                           \
   int IAC_x, IAC_y;                                    \
+  bool _is_border = IS_BORDER_MAP_POS(x, y, 1);        \
   CHECK_MAP_POS(x, y);                                 \
   for (IAC_i = 0; IAC_i < 4; IAC_i++) {                \
     IAC_x = x + CAR_DIR_DX[IAC_i];                     \
     IAC_y = y + CAR_DIR_DY[IAC_i];                     \
                                                        \
-    if (normalize_map_pos(&IAC_x, &IAC_y)) {
+    if (!_is_border                                    \
+        || normalize_map_pos(&IAC_x, &IAC_y)) {
 
 #define cartesian_adjacent_iterate_end                 \
     }                                                  \