[gnugo-devel] arend_3_3.6: shrink size of local_owl_data

[Arend Bayer]

 - reduce size of struct local_owl_data for speedup

This patch makes the following changes:
 * Only store eye spaces for the relevant color
 * Consequently, a couple of functions in owl.c and optics.c only take the
   relevant eye space information as argument. Also, make_domains only
   computes the eyes spaces for the relevant color (resp. it is called
   only once from owl_analyze_semeai).
 * Change a couple of fields from int to char where this is obviously
   sufficient.

I measured a speedup of 6% for this patch. I cannot say I expected it to
be this large, but at least I hoped for it. I see three reasons for the
speedup:
1. push_owl is faster
2. make_domains has to do less work
3. A bigger part of the owl data fits into the processor cache

I wouldn't underestimate No. 3.

As the patch is fairly big and mostly boring, I've put it up at
http://www.uni-bonn.de/~uzsxtn/arend_3_3.6.
Below is a small excerpt of the changes which should show what I did.

Arend

Btw, I hope I didn't break --life (and I think so).


Index: engine/liberty.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/liberty.h,v
retrieving revision 1.101
diff -u -r1.101 liberty.h
--- engine/liberty.h    21 May 2002 16:40:53 -0000      1.101
+++ engine/liberty.h    22 May 2002 16:30:17 -0000
@@ -413,9 +413,9 @@
 int owl_lively(int pos);
 int owl_escape_value(int pos);
 int owl_goal_dragon(int pos);
-int owl_eyespace(int apos, int bpos);
-int owl_big_eyespace(int apos, int bpos);
-int owl_proper_eye(int apos, int bpos);
+int owl_eyespace(int apos);
+int owl_big_eyespace(int apos);
+int owl_proper_eye(int apos);
 void owl_reasons(int color);

 void unconditional_life(int unconditional_territory[BOARDMAX], int color);
@@ -659,7 +659,7 @@

 struct half_eye_data {
   float value;      /* Topological eye value. */
-  int type;         /* HALF_EYE or FALSE_EYE; */
+  char type;         /* HALF_EYE or FALSE_EYE; */
   int num_attacks;  /* number of attacking points */
   int attack_point[4];  /* the move to attack a topological halfeye */
   int num_defends;      /* number of defending points */
@@ -804,8 +804,8 @@
   int esize;         /* size of the eyespace                                 */
   int msize;         /* number of marginal vertices                          */
   int origin;        /* The origin                                           */
-  int maxeye;        /* number of eyes if defender plays first               */
-  int mineye;        /* number of eyes if attacker plays first               */
+  char maxeye;       /* number of eyes if defender plays first               */
+  char mineye;       /* number of eyes if attacker plays first               */
   int attack_point;  /* vital point for attack                               */
   int defense_point; /* vital point for defense                              */

@@ -813,11 +813,11 @@
   /* ---------------------------------------------------------------- */
   /* The below fields are not. */

-  int marginal;             /* This vertex is marginal                    */
-  int type;                 /* Various characteristics of the eyespace    */
-  int neighbors;            /* number of neighbors in eyespace            */
-  int marginal_neighbors;   /* number of marginal neighbors               */
-  int cut;                  /* Opponent can cut at vertex.                */
+  char marginal;             /* This vertex is marginal                    */
+  char type;                 /* Various characteristics of the eyespace    */
+  char neighbors;            /* number of neighbors in eyespace            */
+  char marginal_neighbors;   /* number of marginal neighbors               */
+  char cut;                  /* Opponent can cut at vertex.                */
 };

 typedef struct eye_data row_of_eye_data[BOARDMAX];


Function definitions changed:

 int recognize_eye2(int pos, int *attack_point,
-                  int *defense_point, int *max, int *min,
+                  int *defense_point, char *max, char *min,
                   struct eye_data eye[BOARDMAX],
                   struct half_eye_data heye[BOARDMAX],
                     int add_moves, int color);

 int find_eye_dragons(int origin, struct eye_data eye[BOARDMAX], int eye_color,
                     int dragons[], int max_dragons);
 float topological_eye(int pos, int color,
-                     struct eye_data b_eye[BOARDMAX],
-                     struct eye_data w_eye[BOARDMAX],
+                     struct eye_data my_eye[BOARDMAX],
                      struct half_eye_data heye[BOARDMAX]);
 void add_false_eye(int pos, struct eye_data eye[BOARDMAX],
                   struct half_eye_data heye[BOARDMAX]);

(and similar for other functions)

Index: engine/optics.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/optics.c,v
retrieving revision 1.44
diff -u -r1.44 optics.c
--- engine/optics.c     16 May 2002 19:14:41 -0000      1.44
+++ engine/optics.c     22 May 2002 16:30:29 -0000

make_domains can now take NULL as argument for either color's eye space
and then disregards it as follows:

@@ -135,8 +134,10 @@
   /* Initialize eye data and compute the lively array. */
   for (pos = BOARDMIN; pos < BOARDMAX; pos++)
     if (ON_BOARD(pos)) {
-      clear_eye(&(b_eye[pos]));
-      clear_eye(&(w_eye[pos]));
+      if (b_eye)
+        clear_eye(&(b_eye[pos]));
+      if (w_eye)
+        clear_eye(&(w_eye[pos]));
       lively[pos] = is_lively(owl_call, pos);
     }


As an example, here is how owl_proper_eye changed (with corresponding
changes in mkpat.c and owl_*.db of course):

 int
-owl_proper_eye(int apos, int bpos)
+owl_proper_eye(int apos)
 {
-  ASSERT1(IS_STONE(board[bpos]), bpos);
   ASSERT_ON_BOARD1(apos);

-  if (board[bpos] == WHITE)
-    return (current_owl_data->white_eye[apos].color == WHITE_BORDER
-           && !current_owl_data->white_eye[apos].marginal);
-  else
-    return (current_owl_data->black_eye[apos].color == BLACK_BORDER
-           && !current_owl_data->black_eye[apos].marginal);
+  return (current_owl_data->my_eye[apos].color
+            == BORDER_COLOR(current_owl_data->color)
+         && !current_owl_data->my_eye[apos].marginal);
 }