[gnugo-devel] do_remove_string() and update_liberties()

[Paul Pogonyshev]

here is yet one more speed optimization in board.c.

- do_remove_string() now does some job of update_liberties()
  (speed optimization)

i have also patched up a thin place in do_play_move() which went in
with Arend's fix of a bug in one of my previous speed optimization
patches.  it was an open doors for bugs in incremental board code and
i spent half an hour trying to understand why correct code caused
assertion failures.

profile results on nngs.tst:

before:
  1.32    603.44    12.80 45442922     0.00     0.00  update_liberties
  0.52    814.84     5.07 173278879     0.00     0.00  popgo
  0.28    877.36     2.74 20327540     0.00     0.00  do_remove_string
-----------------------------------------------
                2.74   16.84 20327540/20327540     do_play_move [65]
[126]    2.0    2.74   16.84 20327540         do_remove_string [126]
               12.80    0.00 45442162/45442922     update_liberties [149]
                2.73    0.00 45442162/137484513     remove_neighbor [170]
                1.31    0.00 30206150/203500012     hashdata_invert_stone [166]
-----------------------------------------------


after:
  0.50    801.82     4.77 173065842     0.00     0.00  popgo
  0.49    806.50     4.68 20272467     0.00     0.00  do_remove_string
  0.24    883.94     2.33  7029309     0.00     0.00  update_liberties
-----------------------------------------------
                4.68    6.06 20272467/20272467     do_play_move [73]
[155]    1.1    4.68    6.06 20272467         do_remove_string [155]
                2.63    0.00 45327566/137097312     remove_neighbor [169]
                2.33    0.00 7028533/7029309     update_liberties [236]
                1.10    0.00 30091969/203172794     hashdata_invert_stone [173]
-----------------------------------------------

total runtime per gprof:
before: 971.18
after:  955.55

note that the number of calls to different functions has changed
somewhat.  that is because liberties in board structures are now
often listed in different order.  this also explains why speed up
in total time seems to be larger than 0.9%.

i'm running regressions now.  there are no changes in the first 3 batches.

Paul


Index: engine/board.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/board.c,v
retrieving revision 1.77
diff -u -p -r1.77 board.c
--- engine/board.c      26 Jun 2003 20:24:03 -0000      1.77
+++ engine/board.c      29 Jun 2003 21:12:36 -0000
@@ -3892,6 +3892,7 @@ do_remove_string(int s)
 {
   int pos;
   int k;
+  int size = string[s].size;
 
   /* Traverse the stones of the string, by following the cyclic chain. */
   pos = FIRST_STONE(s);
@@ -3904,22 +3905,61 @@ do_remove_string(int s)
   } while (!BACK_TO_FIRST_STONE(s, pos));
 
   /* The neighboring strings have obtained some new liberties and lost
-   * a neighbor.
+   * a neighbor.  For speed reasons we handle two most common cases
+   * when string size is 1 or 2 stones here instead of calling
+   * update_liberties().
    */
-  for (k = 0; k < string[s].neighbors; k++) {
-    remove_neighbor(string[s].neighborlist[k], s);
-    update_liberties(string[s].neighborlist[k]);
+  if (size == 1) {
+    for (k = 0; k < string[s].neighbors; k++) {
+      int neighbor = string[s].neighborlist[k];
+
+      remove_neighbor(neighbor, s);
+      PUSH_VALUE(string[neighbor].liberties);
+
+      if (string[neighbor].liberties < MAX_LIBERTIES)
+       string[neighbor].libs[string[neighbor].liberties] = pos;
+      string[neighbor].liberties++;
+    }
+  }
+  else if (size == 2) {
+    int other = OTHER_COLOR(string[s].color);
+    int pos2 = NEXT_STONE(pos);
+
+    for (k = 0; k < string[s].neighbors; k++) {
+      int neighbor = string[s].neighborlist[k];      
+
+      remove_neighbor(neighbor, s);
+      PUSH_VALUE(string[neighbor].liberties);
+
+      if (NEIGHBOR_OF_STRING(pos, neighbor, other)) {
+       if (string[neighbor].liberties < MAX_LIBERTIES)
+         string[neighbor].libs[string[neighbor].liberties] = pos;
+       string[neighbor].liberties++;
+      }
+
+      if (NEIGHBOR_OF_STRING(pos2, neighbor, other)) {
+       if (string[neighbor].liberties < MAX_LIBERTIES)
+         string[neighbor].libs[string[neighbor].liberties] = pos2;
+       string[neighbor].liberties++;
+      }
+    }
+  }
+  else {
+    for (k = 0; k < string[s].neighbors; k++) {
+      remove_neighbor(string[s].neighborlist[k], s);
+      update_liberties(string[s].neighborlist[k]);
+    }
   }
 
   /* Update the number of captured stones. These are assumed to
    * already have been pushed.
    */
   if (string[s].color == WHITE)
-    white_captured += string[s].size;
+    white_captured += size;
   else
-    black_captured += string[s].size;
-    
-  return string[s].size;
+    black_captured += size;
+
+  return size;
 }
 
 
@@ -4350,8 +4390,12 @@ do_play_move(int pos, int color)
   /* Clear string mark. */
   string_mark++;
 
-  /* Put down the stone. */
+  /* Put down the stone.  We also set its string number to -1 for a while
+   * so that NEIGHBOR_OF_STRING() and friends don't get confused with the
+   * stone.
+   */
   DO_ADD_STONE(pos, color);
+  string_number[pos] = -1;
 
   /* Look in all directions. Count the number of neighbor strings of the same
    * color, remove captured strings and remove `pos' as liberty for opponent