Re: [gnugo-devel] engine/influence.c

[Arend Bayer]

A couple of things regarding the loop unrolling bug:

Dave wrote:

> Arend Bayer <address@hidden> writes:
>
> > On 6 Sep 2002, Dave Denholm wrote:
> > > <address@hidden> writes:
> > > > Here are the test results after defining
> > > > #define EXPLICIT_LOOP_UNROLLING 0
> > > > in influence.c. Test results are current, so the unexpected results are
> > > > ALL due to this change.
I went through those unexpected results, and I do think the behaviour
w/ the fix is better than without.

> > * unfortunately, a big slowdown:
> > Running on safety.tst (which contains only early game positions):
> >
> > Profile of cvs:
> >  time   seconds   seconds    calls  ms/call  ms/call  name
> >  10.57      7.82     7.82    21833     0.36     0.36  accumulate_influence
> >
> > Profile with this change:
> >  22.31     17.24    17.24    23074     0.75     0.75  accumulate_influence
> >
> > In other words, we should do s.th. about the performance.
>
> Hmm - well, I'll try to resurrect the speedups I made when I thought
> accumulate_influence was important. Mainly just a case of getting
> rid of the divisions from the inner loop.

It should be noted that accumulate_influence gets _very_ time critical
in low level, because the work it does is pretty much constant.

> It is not yet ready for inclusion, but I'd better send it in case
> someone else gets a chance to polish / test it before me. (Just when I
> thought I'd get a chance to do some gnugo development, another rush
> has turned up at work :-(  )

I've applied the patch by hand to CVS -- I had to remove the hard-coding
of DIAGONAL_DAMPING and also added one other micro-speedup (now we test
first whether the permeability is 0.0 before we even start the inner
loop). It's a good improvement over the simple bugfix, but still
a lot worse than CVS:

 time   seconds   seconds    calls  ms/call  ms/call  name
 17.03     13.64    13.64    24374     0.56     0.56 accumulate_influence

In my opinion 10% is already too much time for this function.

One thing to note is that around two third of the cases where we add a
point to the queue we are already below INFLUENCE_CUTOFF. For this case,
the inner could be simplified a lot, so we could add a separate queue for
these cases that will get handled by a second loop.

On the other hand I wonder why we even bother spreading this very low
influence. The effect on territorial valuation is negligeable; so the
only thing that gets affected is whose_territory(). I doubt that this is
wort the effort, it is only used by exaclty 12 patterns.

Arend

Index: engine/influence.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/influence.c,v
retrieving revision 1.60
diff -u -d -r1.60 influence.c
--- engine/influence.c  10 Sep 2002 15:05:42 -0000      1.60
+++ engine/influence.c  20 Sep 2002 21:17:56 -0000
@@ -99,32 +99,42 @@
 #define EXPLICIT_LOOP_UNROLLING 1

 #if EXPLICIT_LOOP_UNROLLING
+/* In addition to the parameters, this macro expects
+ *  m,n = original source of influence
+ *  i,j = point influence is being spread from
+ *  current_strength combines strength and damping factor
+ *  b is 1/(square of distance from m,n to i,j) ; or halved
+ *    for diagonals
+ *
+ *  arg_i is i + arg_di ; arg_j is j + arg_dj
+ *  arg_d is 1 for diagonal movement
+ *
+ */

-#define code1(arg_di, arg_dj, arg_i, arg_j, arg_d) \
+
+#define code1(arg_di, arg_dj, arg_i, arg_j, arg_d) do { \
       if (q->p[arg_i][arg_j] == EMPTY \
          && ((arg_di)*(i-m) + (arg_dj)*(j-n) > 0 \
              || queue_start == 1)) { \
-       permeability = permeability_array[i][j]; \
-       if (arg_d) \
+       float contribution; \
+       float permeability = permeability_array[i][j]; \
+       if (arg_d) { \
          permeability *= gg_max(permeability_array[arg_i][j], \
                                 permeability_array[i][arg_j]); \
-       if (permeability == 0.0) \
-         continue; \
-       damping = (arg_d) ? diagonal_attenuation : attenuation; \
-       if (i == m && j == n) \
-         cos2phi = 1.0; \
-       else { \
-         float a = (arg_di)*(i-m) + (arg_dj)*(j-n); \
-         float c = (arg_di)*(arg_di) + (arg_dj)*(arg_dj); \
-         gg_assert(a > 0.0); \
-         cos2phi = (a*a) / (b*c); \
+         if (permeability == 0.0) \
+           continue; \
+       } \
+       contribution = current_strength * permeability; \
+       if (queue_start != 1) { \
+         int a = (arg_di)*(i-m) + (arg_dj)*(j-n); \
+         contribution *= (a*a) * b; /* contribution *= cos(phi) */ \
        } \
-       contribution = cos2phi * permeability * current_strength / damping; \
        if (contribution <= INFLUENCE_CUTOFF) { \
           if (permeability < 1.0 || q->w[arg_i][arg_j] != 0.0) \
            continue; \
-          else \
+          else { \
             contribution = 1.01 * INFLUENCE_CUTOFF; \
+         } \
        } \
        if (q->w[arg_i][arg_j] == 0.0) { \
          q->queuei[queue_end] = (arg_i); \
@@ -132,9 +142,10 @@
          queue_end++; \
        } \
        q->w[arg_i][arg_j] += contribution; \
-      }
+      } } while (0)
 #endif

+
 static void
 accumulate_influence(struct influence_data *q, int m, int n, int color)
 {
@@ -143,19 +154,14 @@
 #if !EXPLICIT_LOOP_UNROLLING
   int d;
 #endif
-  float damping;
   float b;
-  float current_strength;
-  float cos2phi;
-  float permeability;
-  float contribution;
-  float attenuation;
-  float diagonal_attenuation;
+  float inv_attenuation;
+  float inv_diagonal_damping;
   float (*permeability_array)[MAX_BOARD];

-  /* Clear the queue. */
+  /* Clear the queue. Entry 0 is implicitly (m, n). */
   int queue_start = 0;
-  int queue_end = 0;
+  int queue_end = 1;

   if (0)
     gprintf("Accumulating influence for %s at %m\n",
@@ -163,40 +169,48 @@

   /* Attenuation only depends on the influence origin. */
   if (color == WHITE)
-    attenuation = q->white_attenuation[m][n];
+    inv_attenuation = 1.0 / q->white_attenuation[m][n];
   else
-    attenuation = q->black_attenuation[m][n];
+    inv_attenuation = 1.0 / q->black_attenuation[m][n];
+
   if (q->is_territorial_influence)
-    diagonal_attenuation = attenuation * TERR_DIAGONAL_DAMPING;
+    inv_diagonal_damping = 1.0 / TERR_DIAGONAL_DAMPING;
   else
-    diagonal_attenuation = attenuation * DIAGONAL_DAMPING;
+    inv_diagonal_damping = 1.0 / DIAGONAL_DAMPING;

   if (color == WHITE)
     permeability_array = q->white_permeability;
   else
     permeability_array = q->black_permeability;
+
+  /* We put the original source into slot 0.  */
+  q->queuei[0] = m;
+  q->queuej[0] = n;

-  /* Put the influence origin on the stack. */
   if (color == WHITE)
     q->w[m][n] = q->white_strength[m][n];
   else
     q->w[m][n] = q->black_strength[m][n];
-  q->queuei[queue_end] = m;
-  q->queuej[queue_end] = n;
-  queue_end++;
+

   /* Spread influence until the stack is empty. */
   while (queue_start < queue_end) {
+    float current_strength;

-    /* Pick first element in queue. */
     i = q->queuei[queue_start];
     j = q->queuej[queue_start];
-    b = (i-m)*(i-m) + (j-n)*(j-n);
+    queue_start++;
+    if (permeability_array[i][j] == 0.0)
+      continue;
     if (0)
       gprintf("Picked %m from queue. w=%f start=%d end=%d\n",
              i, j, q->w[i][j], queue_start, queue_end);
-    current_strength = q->w[i][j];
-    queue_start++;
+    if (queue_start == 1)
+      b = 1.0;
+    else
+      b = 1.0 / ((i-m)*(i-m) + (j-n)*(j-n));
+
+    current_strength = q->w[i][j] * inv_attenuation;

 #if !EXPLICIT_LOOP_UNROLLING
     /* Try to spread influence in each of the eight directions. */
@@ -214,52 +228,45 @@
          && (di*(i-m) + dj*(j-n) > 0
              || queue_start == 1)) {

+       float contribution;
+       float permeability = permeability_array[i][j];
+       float dfactor;
+       float inv_damping;
+
        /* Now compute the damping of the influence.
         * First we have the permeability at the point we are
         * spreading from. For diagonal movement we also take the
         * permeability of the vertices we are "passing by" into
         * account.
         */
-       permeability = permeability_array[i][j];
-       if (d > 3) /* diagonal movement */
+       if (d > 3) { /* diagonal movement */
          permeability *= gg_max(permeability_array[i+di][j],
-                                permeability_array[i][j+dj]);
+                                        permeability_array[i][j+dj]);
+         inv_damping = inv_diagonal_damping;
+         dfactor = 0.5;
+       }
+       else {
+         inv_damping = 1.0;
+         dfactor = 1.0;
+       }

        if (permeability == 0.0)
          continue;
-
-       /* Then we have the distance dependent damping. */
-       damping = 1.0;
-       switch (d) {
-       case 0: /* south */
-       case 1: /* west */
-       case 2: /* north */
-       case 3: /* east */
-         damping = attenuation;
-         break;
-       case 4: /* southwest */
-       case 5: /* northwest */
-       case 6: /* northeast */
-       case 7: /* southeast */
-         damping = diagonal_attenuation;
-         break;
-       }
-
+
+       contribution = permeability * current_strength * inv_diagonal_damping;
+
        /* Finally direction dependent damping. */
-       if (i == m && j == n)
-         cos2phi = 1.0;
-       else {
-         float a = di*(i-m) + dj*(j-n);
-         float c = di*di + dj*dj;
-         gg_assert(a > 0.0);
-         cos2phi = (a*a) / (b*c);
+       if (i != m || j != n) {
+         int a = di*(i-m) + dj*(j-n);
+         gg_assert(a > 0);
+         contribution *= (a*a) * b * dfactor;
        }

-       contribution = cos2phi * permeability * current_strength / damping;
-
        /* Stop spreading influence if the contribution becomes too low. */
        if (contribution <= INFLUENCE_CUTOFF) {
-          if (permeability < 1.0 || q->w[i+di][j+dj] != 0.0)
+          if (permeability_array[i][j] < 1.0
+             || (d > 3 && diagonal_permeability < 1.0)
+             || q->w[i+di][j+dj] != 0.0)
            continue;
           else
             contribution = 1.01 * INFLUENCE_CUTOFF;
@@ -280,23 +287,27 @@
       }
     }
 #else
-    if (i > 0)
-      code1(-1, 0, i-1, j, 0);
     if (i < board_size-1)
       code1(1, 0, i+1, j, 0);
     if (j > 0)
       code1(0, -1, i, j-1, 0);
+    if (i > 0)
+      code1(-1, 0, i-1, j, 0);
     if (j < board_size-1)
       code1(0, 1, i, j+1, 0);
-    if (i > 0 && j > 0)
-      code1(-1, -1, i-1, j-1, 1);
+
+    /* Update factors for diagonal movement. */
+    b *= 0.5;
+    current_strength *= inv_diagonal_damping;
+
     if (i < board_size-1 && j > 0)
       code1(1, -1, i+1, j-1, 1);
-    if (i < board_size-1 && j < board_size-1)
-      code1(1, 1, i+1, j+1, 1);
+    if (i > 0 && j > 0)
+      code1(-1, -1, i-1, j-1, 1);
     if (i > 0 && j < board_size-1)
       code1(-1, 1, i-1, j+1, 1);
-
+    if (i < board_size-1 && j < board_size-1)
+      code1(1, 1, i+1, j+1, 1);
 #endif
   }

@@ -1038,7 +1049,7 @@
  * move for OTHER_COLOR(color) at (m, n). If these coordinates are -1
  * no move is made. In any case it's assumed that color is in turn to
  * move. (This affects the barrier patterns (class A, D) and intrusions
- * (class B).
+ * (class B)).
  */
 static void
 compute_influence(struct influence_data *q, int color, int m, int n,