[Freeciv-Dev] Re: Profiling Civserver again

[Jason Dorje Short <jshort@xxxxxxxxxxxxx>]

Vasco Alexandre Da Silva Costa wrote:
> 
> On Wed, 25 Jul 2001, Jason Dorje Short wrote:
> > Gregory Berkolaiko wrote:
> > > and that's it.
> > > Of course people might want to do some more profiling (sorry, cannot do it
> > > myself, I am away), but I am 95% sure that the above will be almost as
> > > fast as Trent's algorithm.
> 
> Probably. I guess the way to find out is to profile both approaches and
> find out. The problem with this is that in order for it to be accurate
> both games must run exactly alike. I guess we can run both and see the
> average overhead per function call. That would be a reasonable measure.

Overhead per function call appears to still have a large variation
(mostly due to the length of the game, I think - early on the search
cannot go to its full depth of 74 turns of movement).  The value I've
been looking at is time per map node spent in the function.  The number
of map nodes (in total) can be found from the number of times
get_from_mapqueue() is called.  This divides into the total time spent
in the function - including time spent in called functions.

I've done five runs.  The values are as follows:

original code - one run - 1.5 us per map node
"better" code (my first patch) - 1.4, 1.3, and 1.4 us per map node
"best" code - one run - 1.2 us per map node

Thus, I believe this new code will reduce the CPU usage of that function
by around 20% (with a large margin of error), reducing CPU costs by 4%
overall for AI-intensive games.  This means practically the whole
estimated cost of normalize_map_pos may have been eliminated (although
this seems impossible, a good part of the overhead for calling a
function is probably counted within the calling function).  More testing
could find better numbers here, but I doubt it's worth the time.

Also, use of this iteration macro elsewhere will speed things up there,
cutting out at least some of the ~100 million normalize_map_pos() calls
that account for another 1% of CPU usage.

Finally, under this (attached) patch each of the iterations will be
cleaner.

> The thing is that according to Amhdal's law after applying
> either of the patches the main bottleneck will move on to be elsewhere.

Yes, but that could be a good thing.  As long as we can find
bottlenecks, we can find places to focus our efforts at improvement.

jason

Index: common/map.h
===================================================================
RCS file: /home/freeciv/CVS/freeciv/common/map.h,v
retrieving revision 1.79
diff -u -r1.79 map.h
--- common/map.h        2001/07/01 20:54:00     1.79
+++ common/map.h        2001/07/26 06:39:13
@@ -364,6 +364,27 @@
   }                                                                           \
 }
 
+/* Iterate through all tiles adjacent to a tile.  itr_x and itr_y are as
+ * in adjc_iterate; itr_dir is the directional value (see DIR_D[XY]). */
+/* This assumes that center_x and center_y are normalized. --JDS */
+#define adjc_iterate_dir(center_x, center_y, itr_x, itr_y, itr_dir)           \
+{                                                                             \
+  int itr_x, itr_y, itr_dir;                                                  \
+  int border = (!center_y || !center_x ||                                     \
+               (center_y == map.ysize-1) || (center_x == map.xsize-1));       \
+  for (itr_dir = 0; itr_dir < 8; itr_dir++) {                                 \
+    itr_y = center_y + DIR_DY[itr_dir];                                       \
+    itr_x = center_x + DIR_DX[itr_dir];                                       \
+    if (border) {                                                             \
+      if (itr_y < 0 || itr_y > map.ysize) continue;                           \
+      if (itr_x < 0) itr_x += map.xsize;                                      \
+      else if (itr_x >= map.xsize) itr_x -= map.xsize;                        \
+    }
+
+#define adjc_iterate_dir_end                                                  \
+  }                                                                           \
+}
+
 /* iterating y, x for cache efficiency */
 #define whole_map_iterate(WMI_x_itr, WMI_y_itr)                               \
 {                                                                             \
Index: server/gotohand.c
===================================================================
RCS file: /home/freeciv/CVS/freeciv/server/gotohand.c,v
retrieving revision 1.99
diff -u -r1.99 gotohand.c
--- server/gotohand.c   2001/06/29 19:39:06     1.99
+++ server/gotohand.c   2001/07/26 06:39:14
@@ -273,7 +273,7 @@
 void really_generate_warmap(struct city *pcity, struct unit *punit,
                            enum unit_move_type move_type)
 {
-  int x, y, move_cost, dir, x1, y1;
+  int x, y, move_cost;
   int orig_x, orig_y;
   int igter;
   int maxcost = THRESHOLD * 6 + 2; /* should be big enough without being TOO 
big */
@@ -307,12 +307,7 @@
 
   while (get_from_mapqueue(&x, &y)) {
     ptile = map_get_tile(x, y);
-    for (dir = 0; dir < 8; dir++) {
-      x1 = x + DIR_DX[dir];
-      y1 = y + DIR_DY[dir];
-      if (!normalize_map_pos(&x1, &y1))
-       continue;
-
+    adjc_iterate_dir(x, y, x1, y1, dir) {
       switch (move_type) {
       case LAND_MOVING:
        if (warmap.cost[x1][y1] <= warmap.cost[x][y])
@@ -363,7 +358,7 @@
        freelog(LOG_FATAL, "Bad/unimplemented move_type in 
really_generate_warmap().");
        abort();
       }
-    } /* end for */
+    } adjc_iterate_dir_end;
   }
 
   freelog(LOG_DEBUG, "Generated warmap for (%d,%d).",