[gnugo-devel] do_play_move speedup

[Evan Berggren Daniel]

This patch speeds up do_play_move by about 15% on my machine.  Inlining
the function cause ~5% speedup, and the rest is from taking more care with
conditionals and doing some precomputation.  Anyway, this is the result of
my initial experiments with the profiler.  Hope it helps.

Some of it looks like random variation, but I think there is a real
speedup as well.

Regression delta should be zero, of course.

Thanks

Evan Daniel

Original profile (nngs2.tst, PentiumII, compiled with CFALGS='-g -pg -O2')

  %   cumulative   self              self     total
 time   seconds   seconds    calls  Ks/call  Ks/call  name
  8.66    121.56   121.56 186396832     0.00     0.00  scan_for_patterns
  5.10    193.21    71.65 138732020     0.00     0.00  fastlib
  4.11    250.99    57.78   225220     0.00     0.00
compute_primary_domains
  3.86    305.14    54.15 55561860     0.00     0.00  do_play_move
  3.52    354.54    49.40 120323957     0.00     0.00  check_pattern_light
  3.51    403.79    49.25 33859068     0.00     0.00  order_moves
  3.25    449.39    45.60 77034189     0.00     0.00
incremental_order_moves
  2.98    491.19    41.80 55556242     0.00     0.00  undo_trymove
  2.54    526.91    35.72 230063283     0.00     0.00  neighbor_of_string
  2.26    558.60    31.69 149552506     0.00     0.00  approxlib


New profile:

  %   cumulative   self              self     total
 time   seconds   seconds    calls  Ks/call  Ks/call  name
  8.61    119.93   119.93 186396832     0.00     0.00  scan_for_patterns
  4.78    186.61    66.68 138732020     0.00     0.00  fastlib
  4.16    244.56    57.95   225220     0.00     0.00
compute_primary_domains
  3.57    294.31    49.75 33859068     0.00     0.00  order_moves
  3.44    342.29    47.98 120323957     0.00     0.00  check_pattern_light
  3.30    388.24    45.95 55561853     0.00     0.00  do_play_move
  3.13    431.86    43.62 77034189     0.00     0.00
incremental_order_moves
  2.87    471.89    40.03 55556235     0.00     0.00  undo_trymove
  2.56    507.63    35.74 230063283     0.00     0.00  neighbor_of_string
  2.51    542.54    34.91 149552506     0.00     0.00  approxlib

Index: board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.49
diff -u -d -r1.49 board.c
--- board.c     10 Sep 2002 20:06:01 -0000      1.49
+++ board.c     22 Sep 2002 20:05:14 -0000
@@ -273,7 +273,7 @@
 static int propagate_string(int stone, int str);
 static void find_liberties_and_neighbors(int s);
 static int do_remove_string(int s);
-static void do_play_move(int pos, int color);
+inline static void do_play_move(int pos, int color);
 static int slow_approxlib(int pos, int color, int maxlib, int *libs);
 static int incremental_sloppy_self_atari(int pos, int color);

@@ -3720,7 +3720,7 @@
 /* Play a move without legality checking. Suicide is allowed.
  */

-static void
+inline static void
 do_play_move(int pos, int color)
 {
   int other = OTHER_COLOR(color);
@@ -3728,34 +3728,41 @@
   int neighbor_allies = 0;
   int have_liberties = 0;
   int s = -1;
+  int south = SOUTH(pos);
+  int west = WEST(pos);
+  int north = NORTH(pos);
+  int east = EAST(pos);

   if (!strings_initialized)
     init_board();

   /* Remove captured stones and check for suicide.*/
-  if (board[SOUTH(pos)] == other && LIBERTIES(SOUTH(pos)) == 1)
-    captured_stones += do_remove_string(string_number[SOUTH(pos)]);
-  else if (LIBERTY(SOUTH(pos)) || (board[SOUTH(pos)] == color
-                                  && LIBERTIES(SOUTH(pos)) > 1))
-    have_liberties = 1;
+  if (board[south] == other && LIBERTIES(south) == 1)
+    captured_stones += do_remove_string(string_number[south]);

-  if (board[WEST(pos)] == other && LIBERTIES(WEST(pos)) == 1)
-    captured_stones += do_remove_string(string_number[WEST(pos)]);
-  else if (LIBERTY(WEST(pos)) || (board[WEST(pos)] == color
-                                 && LIBERTIES(WEST(pos)) > 1))
-    have_liberties = 1;
+  if (board[west] == other && LIBERTIES(west) == 1)
+    captured_stones += do_remove_string(string_number[west]);

-  if (board[NORTH(pos)] == other && LIBERTIES(NORTH(pos)) == 1)
-    captured_stones += do_remove_string(string_number[NORTH(pos)]);
-  else if (LIBERTY(NORTH(pos)) || (board[NORTH(pos)] == color
-                                  && LIBERTIES(NORTH(pos)) > 1))
-    have_liberties = 1;
+  if (board[north] == other && LIBERTIES(north) == 1)
+    captured_stones += do_remove_string(string_number[north]);
+
+  if (board[east] == other && LIBERTIES(east) == 1)
+    captured_stones += do_remove_string(string_number[east]);
+
+
+  if (captured_stones == 0) {
+    if (LIBERTY(south) || (board[south] == color && LIBERTIES(south) > 1))
+      have_liberties = 1;
+    else if (LIBERTY(west) || (board[west] == color && LIBERTIES(west) > 1))
+      have_liberties = 1;
+    else if (LIBERTY(north) || (board[north] == color && LIBERTIES(north) > 1))
+      have_liberties = 1;
+    else if (LIBERTY(east) ||(board[east] == color && LIBERTIES(east) > 1))
+      have_liberties = 1;
+  } else {
+      have_liberties = 1;
+  }

-  if (board[EAST(pos)] == other && LIBERTIES(EAST(pos)) == 1)
-    captured_stones += do_remove_string(string_number[EAST(pos)]);
-  else if (LIBERTY(EAST(pos)) || (board[EAST(pos)] == color
-                                 && LIBERTIES(EAST(pos)) > 1))
-    have_liberties = 1;

   /* No captures and no liberties -> suicide. */
   if (have_liberties == 0 && captured_stones == 0) {
@@ -3771,47 +3778,47 @@
    */
   string_mark++;

-  if (board[SOUTH(pos)] == color && UNMARKED_STRING(SOUTH(pos))) {
+  if (board[south] == color && UNMARKED_STRING(south)) {
     neighbor_allies++;
-    s = string_number[SOUTH(pos)];
-    MARK_STRING(SOUTH(pos));
+    s = string_number[south];
+    MARK_STRING(south);
   }
-  else if (board[SOUTH(pos)] == other && UNMARKED_STRING(SOUTH(pos))) {
-    remove_liberty(string_number[SOUTH(pos)], pos);
-    MARK_STRING(SOUTH(pos));
+  else if (board[south] == other && UNMARKED_STRING(south)) {
+    remove_liberty(string_number[south], pos);
+    MARK_STRING(south);
   }

-  if (board[WEST(pos)] == color && UNMARKED_STRING(WEST(pos))) {
+  if (board[west] == color && UNMARKED_STRING(west)) {
     neighbor_allies++;
-    s = string_number[WEST(pos)];
-    MARK_STRING(WEST(pos));
+    s = string_number[west];
+    MARK_STRING(west);
   }
-  else if (board[WEST(pos)] == other && UNMARKED_STRING(WEST(pos))) {
-    remove_liberty(string_number[WEST(pos)], pos);
-    MARK_STRING(WEST(pos));
+  else if (board[west] == other && UNMARKED_STRING(west)) {
+    remove_liberty(string_number[west], pos);
+    MARK_STRING(west);
   }

-  if (board[NORTH(pos)] == color && UNMARKED_STRING(NORTH(pos))) {
+  if (board[north] == color && UNMARKED_STRING(north)) {
     neighbor_allies++;
-    s = string_number[NORTH(pos)];
-    MARK_STRING(NORTH(pos));
+    s = string_number[north];
+    MARK_STRING(north);
   }
-  else if (board[NORTH(pos)] == other && UNMARKED_STRING(NORTH(pos))) {
-    remove_liberty(string_number[NORTH(pos)], pos);
-    MARK_STRING(NORTH(pos));
+  else if (board[north] == other && UNMARKED_STRING(north)) {
+    remove_liberty(string_number[north], pos);
+    MARK_STRING(north);
   }

-  if (board[EAST(pos)] == color && UNMARKED_STRING(EAST(pos))) {
+  if (board[east] == color && UNMARKED_STRING(east)) {
     neighbor_allies++;
-    s = string_number[EAST(pos)];
+    s = string_number[east];
 #if 0
-    MARK_STRING(EAST(pos));
+    MARK_STRING(east);
 #endif
   }
-  else if (board[EAST(pos)] == other && UNMARKED_STRING(EAST(pos))) {
-    remove_liberty(string_number[EAST(pos)], pos);
+  else if (board[east] == other && UNMARKED_STRING(east)) {
+    remove_liberty(string_number[east], pos);
 #if 0
-    MARK_STRING(EAST(pos));
+    MARK_STRING(east);
 #endif
   }