Re: speedups (was: Re: [gnugo-devel] Timing data)

[Gunnar Farneback]

Arend wrote:
> My intention was just to single out patterns whose constraint does not
> contain any call to a reading function.

There's still the problem of maintaining this for new and revised
patterns. 

> As the owl_safe_move gets cached and is very likely to get used
> again, I'd guess that a single call to a reading functions will on
> average make the constraint more expensive than owl_safe_move.

Agreed.

> I agree that all your suggestions could make a lot of sense; however, I
> don't know whether there is a good way to guess the constraint complexity.
> attack(*) could have very different expected time consumption, depending
> on the pattern.

The good way is to do profiling and try to estimate average values.
However, this doesn't have to be all that accurate to be useful. I
think something like this would be good enough:

cost    functions
   1    Anything only requiring a table lookup, like lib(),
        owl_escape_value() etc.
   5    Approxlib calls, e.g. olib() and xlib()
 100    Basic reading, e.g. [ox]play_attack(), [ox]defend_against()
 300    Complex reading, e.g. [ox]play_defend_both()
 500    Extra complex reading, e.g. [ox]play_break_through()
1000    Connection reading, e.g. [ox]play_connect

(It might be better to use float values and normalize basic reading at
1.0.)

> push_owl(...)
> {
>   owl_stack_pointer++;
>   owl_stack[owl_stack_pointer] = owl_stack[owl_stack_pointer];
> }
> 
> (no save here) and
> 
> static void
> pop_owl(...)
> {
>   (...)
>   owl_stack_pointer--;
> }
> 
> (No need to copy anything here.)

Ok, this is a reasonable and straightforward optimization.

> Then "owl" can be replaced by "&owl_stack[owl_stack_pointer]" everywhere
> in do_owl_attack/defend.

But this is kind of unwieldy. It can be solved by a macro

#define OWL &owl_stack[owl_stack_pointer]

of course but a simpler approach might be to pass a pointer to owl to
push_owl() and pop_owl() and let them update it, i.e. something like

> static void
> pop_owl(struct local_owl_data **owl)
> {
>   (...)
>   owl_stack_pointer--;
>   *owl = &owl_stack[owl_stack_pointer];
> }

With either approach it's necessary to also revise the initialization
of the owl data in the external callers of do_owl_attack() and
do_owl_defend().

Incidentally we should have written an init_owl() function long ago
since there's lot of duplicated code. Fixed by the patch below.

- new function init_owl() in owl.c

/Gunnar

Index: engine/owl.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/owl.c,v
retrieving revision 1.66
diff -u -r1.66 owl.c
--- engine/owl.c        24 Feb 2002 17:40:10 -0000      1.66
+++ engine/owl.c        26 Feb 2002 13:57:05 -0000
@@ -249,6 +249,9 @@
 static int matches_found;
 static char found_matches[BOARDMAX];
 
+static void init_owl(struct local_owl_data *owl, int target1, int target2,
+                    int move);
+
 static struct local_owl_data *owl_stack = NULL;
 static int owl_stack_size = 0;
 static int owl_stack_pointer = 0;
@@ -284,16 +287,14 @@
   owl_phase = owl;
   count_variations = 1;
   TRACE("owl_analyze_semeai: %1m vs. %1m\n", apos, bpos);
-  owla.lunches_are_current = 0;
-  owlb.lunches_are_current = 0;
   if (owl) {
-    owl_mark_dragon(apos, NO_MOVE, &owla);
-    owl_mark_dragon(bpos, NO_MOVE, &owlb);
-    compute_owl_escape_values(&owla);
-    compute_owl_escape_values(&owlb);
+    init_owl(&owla, apos, NO_MOVE, NO_MOVE);
+    init_owl(&owlb, bpos, NO_MOVE, NO_MOVE);
     owl_make_domains(&owla, &owlb);
   }
   else {
+    owla.local_owl_node_counter        = 0;
+    owlb.local_owl_node_counter        = 0;
     owl_mark_worm(apos, NO_MOVE, &owla);
     owl_mark_worm(bpos, NO_MOVE, &owlb);
   }
@@ -1118,11 +1119,9 @@
 
   if (debug & DEBUG_OWL_PERFORMANCE)
     start = gg_cputime();
-  owl.local_owl_node_counter = 0;
+  
   TRACE("owl_attack %1m\n", target);
-  owl.lunches_are_current = 0;
-  owl_mark_dragon(target, NO_MOVE, &owl);
-  compute_owl_escape_values(&owl);
+  init_owl(&owl, target, NO_MOVE, NO_MOVE);
   owl_make_domains(&owl, NULL);
   result = do_owl_attack(target, &move, &owl, EMPTY, 0);
   tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
@@ -1639,13 +1638,10 @@
   if (debug & DEBUG_OWL_PERFORMANCE)
     start = gg_cputime();
   
-  owl.local_owl_node_counter = 0;
   gg_assert(stackp == 0);
   TRACE("owl_threaten_attack %1m\n", target);
-  owl.lunches_are_current = 0;
-  owl_mark_dragon(target, NO_MOVE, &owl);
+  init_owl(&owl, target, NO_MOVE, NO_MOVE);
   memcpy(saved_boundary, owl.boundary, sizeof(saved_boundary));
-  compute_owl_escape_values(&owl);
   owl_make_domains(&owl, NULL);
 #if PATTERN_CHECK_ON_DEMAND
   owl_shapes(&shape_patterns, moves, other, &owl, &owl_attackpat_db);
@@ -1767,11 +1763,8 @@
   if (debug & DEBUG_OWL_PERFORMANCE)
     start = gg_cputime();
 
-  owl.local_owl_node_counter = 0;
   TRACE("owl_defend %1m\n", target);
-  owl.lunches_are_current = 0;
-  owl_mark_dragon(target, NO_MOVE, &owl);
-  compute_owl_escape_values(&owl);
+  init_owl(&owl, target, NO_MOVE, NO_MOVE);
   owl_make_domains(&owl, NULL);
   result = do_owl_defend(target, &move, &owl, EMPTY, 0);
   tactical_nodes = get_reading_node_counter() - reading_nodes_when_called;
@@ -2226,12 +2219,10 @@
 
   if (debug & DEBUG_OWL_PERFORMANCE)
     start = gg_cputime();
-  owl.local_owl_node_counter = 0;
+
   TRACE("owl_threaten_defense %1m\n", target);
-  owl.lunches_are_current = 0;
-  owl_mark_dragon(target, NO_MOVE, &owl);
+  init_owl(&owl, target, NO_MOVE, NO_MOVE);
   memcpy(saved_goal, owl.goal, sizeof(saved_goal));
-  compute_owl_escape_values(&owl);
   owl_make_domains(&owl, NULL);
 #if PATTERN_CHECK_ON_DEMAND
   owl_shapes(&shape_patterns, moves, color, &owl, &owl_defendpat_db);
@@ -3570,7 +3561,6 @@
   int origin;
   int acode;
   double start = 0;
-  owl.local_owl_node_counter = 0;
 
   if (debug & DEBUG_OWL_PERFORMANCE)
     start = gg_cputime();
@@ -3593,13 +3583,9 @@
       return 3 - result;
     }
     
-    owl.lunches_are_current = 0;
-    owl_mark_dragon(target, NO_MOVE, &owl);
-    owl_update_goal(move, 1, &owl);
-    compute_owl_escape_values(&owl);
+    init_owl(&owl, target, NO_MOVE, move);
     acode = do_owl_attack(target, NULL, &owl, EMPTY, 0);
     result = 3 - acode;
-    owl.lunches_are_current = 0;
     popgo();
   }
   else
@@ -3639,7 +3625,6 @@
   int origin;
   int defense = 0;
   double start = 0.;
-  owl.local_owl_node_counter = 0;
 
   if (debug & DEBUG_OWL_PERFORMANCE)
     start = gg_cputime();
@@ -3665,13 +3650,9 @@
        return 0;
     }
     
-    owl.lunches_are_current = 0;
-    owl_mark_dragon(target, NO_MOVE, &owl);
-    owl_update_goal(move, 1, &owl);
-    compute_owl_escape_values(&owl);
+    init_owl(&owl, target, NO_MOVE, move);
     if (!do_owl_attack(target, &defense, &owl, EMPTY, 0))
       result = WIN;
-    owl.lunches_are_current = 0;
     popgo();
   }
   else
@@ -3714,7 +3695,6 @@
   int origin;
   int dcode;
   double start = 0.;
-  owl.local_owl_node_counter = 0;
 
   if (debug & DEBUG_OWL_PERFORMANCE)
     start = gg_cputime();
@@ -3734,9 +3714,7 @@
    * some stones of the goal dragon from the board.
    */
 #if 1
-    owl.lunches_are_current = 0;
-    owl_mark_dragon(target, NO_MOVE, &owl);
-    compute_owl_escape_values(&owl);
+    init_owl(&owl, target, NO_MOVE, NO_MOVE);
 #endif
 
     if (trymove(move, other, "owl_does_attack", target, EMPTY, 0)) {
@@ -3748,6 +3726,7 @@
     }
 
 #if 0
+    owl.local_owl_node_counter = 0;
     owl.lunches_are_current = 0;
     owl_mark_dragon(target, NO_MOVE, &owl);
 #endif
@@ -3814,10 +3793,7 @@
                                  target2, &result, NULL, NULL, NULL))
     return result;
 
-  owl.local_owl_node_counter = 0;
-  owl.lunches_are_current = 0;
-  owl_mark_dragon(target1, target2, &owl);
-  compute_owl_escape_values(&owl);
+  init_owl(&owl, target1, target2, NO_MOVE);
 
   if (trymove(move, color, "owl_connection_defends", target1, EMPTY, 0)) {
     owl_update_goal(move, 1, &owl);
@@ -4182,6 +4158,7 @@
   
   if (liberties > MAX_SUBSTANTIAL_LIBS)
     return 0;
+  
   for (m = 0; m < board_size; m++)
     for (n = 0; n < board_size; n++)
       owl.goal[POS(m, n)] = 0;
@@ -4234,6 +4211,9 @@
       }
     }
   }
+  /* FIXME: We would want to use init_owl() here too, but it doesn't
+   * fit very well with the construction of the goal array above.
+   */
   compute_owl_escape_values(&owl);
   owl_mark_boundary(&owl);
   owl.lunches_are_current = 0;
@@ -4549,6 +4529,22 @@
 owl_escape_route(struct local_owl_data *owl)
 {
   return dragon_escape(owl->goal, owl->color, owl->escape_values);
+}
+
+
+/****************************
+ * Initialization of owl data
+ ****************************/
+
+static void
+init_owl(struct local_owl_data *owl, int target1, int target2, int move)
+{
+  owl->local_owl_node_counter = 0;
+  owl->lunches_are_current = 0;
+  owl_mark_dragon(target1, target2, owl);
+  if (move != NO_MOVE)
+    owl_update_goal(move, 1, owl);
+  compute_owl_escape_values(owl);
 }