[gnugo-devel] DFA micro optimization

[Arend Bayer]

A couple of micro-optimization of the DFA code:
1. Diffent ordering of states (allow backward jumps, empty intersection means
        go exactly one forward)
2. Similarly optimize ordering of attributes
3. exchange order of next[] and att field in struct state_rt -- seems to gain
        a little due to better alignment

Altogether it gains about 1% on an owl heavy test run. (Close to 10% saved
off the scan_for_pat().)

- dfa micro optimizations

Index: engine/matchpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/matchpat.c,v
retrieving revision 1.65
diff -u -p -r1.65 matchpat.c
--- engine/matchpat.c   22 Aug 2004 23:00:04 -0000      1.65
+++ engine/matchpat.c   11 Sep 2004 16:04:34 -0000
@@ -773,6 +773,8 @@ static const int convert[3][4] = {
   {EMPTY, WHITE, BLACK, OUT_BOARD},    /* WHITE */
   {EMPTY, BLACK, WHITE, OUT_BOARD}     /* BLACK */
 };
+#define EXPECTED_COLOR(player_c, position_c)           \
+               (convert[player_c][position_c])
 
 /* Forward declarations. */
 static void dfa_prepare_for_match(int color);
@@ -906,7 +908,6 @@ scan_for_patterns(dfa_rt_t *pdfa, int l,
     row++;
   } while (delta != 0); /* while not on error state */
 
-  gg_assert(row < DFA_MAX_ORDER);
   return id;
 }
 
Index: patterns/dfa.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.c,v
retrieving revision 1.37
diff -u -p -r1.37 dfa.c
--- patterns/dfa.c      8 Jun 2004 05:52:25 -0000       1.37
+++ patterns/dfa.c      11 Sep 2004 16:04:34 -0000
@@ -113,20 +113,24 @@ member_att(dfa_t *pdfa, int att, int val
 static int
 union_att(dfa_t *pdfa, dfa_t *pdfa1, int att1, dfa_t *pdfa2, int att2)
 {
-  int att;
-  int att_aux;
+  int att_aux = -12345;
+  int att = 0;
+  int save1 = att1;
+  int save2 = att2;
 
+  if (att1 == 0 && att2 == 0)
+    return 0;
   /* copy att1 in att */
-  att = 0;
   while (att1 != 0) {
     pdfa->last_index++;
     if (pdfa->last_index >= pdfa->max_indexes)
       resize_dfa(pdfa, pdfa->max_states, pdfa->max_indexes + DFA_RESIZE_STEP);
     att_aux = pdfa->last_index;
+    if (!att)
+      att = att_aux;
     
     pdfa->indexes[att_aux].val = pdfa1->indexes[att1].val;
-    pdfa->indexes[att_aux].next = att;
-    att = att_aux;
+    pdfa->indexes[att_aux].next = att_aux + 1;
     att1 = pdfa1->indexes[att1].next;
   }
 
@@ -137,13 +141,22 @@ union_att(dfa_t *pdfa, dfa_t *pdfa1, int
       if (pdfa->last_index >= pdfa->max_indexes)
        resize_dfa(pdfa, pdfa->max_states, pdfa->max_indexes + DFA_RESIZE_STEP);
       att_aux = pdfa->last_index;
+      if (!att)
+       att = att_aux;
 
       pdfa->indexes[att_aux].val = pdfa2->indexes[att2].val;
-      pdfa->indexes[att_aux].next = att;
-      att = att_aux;
+      pdfa->indexes[att_aux].next = att_aux + 1;
     }
     att2 = pdfa2->indexes[att2].next;
   }
+  assert(att_aux != -12345);
+  pdfa->indexes[att_aux].next = 0;
+  if (0 && save1 != 0 && save2 != 0) {
+    fprintf(stderr, "Made union of %d and %d at %d.\n", save1, save2, att);
+    dump_dfa(stderr, pdfa);
+    dump_dfa(stderr, pdfa1);
+    dump_dfa(stderr, pdfa2);
+  }
 
   return att;
 }
@@ -205,7 +218,7 @@ compactify_att(dfa_t *pdfa)
     for (k = 0; k <= pdfa->last_state; k++)
       pdfa->states[k].att = map[pdfa->states[k].att];
 
-    if (0)
+    if (1)
       fprintf(stderr, "compactified: %d attributes left of %d\n",
              last, save_last);
 
@@ -416,8 +429,8 @@ print_c_dfa(FILE *of, const char *name, 
     exit(EXIT_FAILURE);
   }
 
-  assert(dfa_minmax_delta(pdfa, -1, 1) > 0);
-  if (dfa_minmax_delta(pdfa, -1, 0)  > 65535) {
+  assert(dfa_minmax_delta(pdfa, -1, 1) > -32768);
+  if (dfa_minmax_delta(pdfa, -1, 0)  > 32768) {
     fprintf(of, "#error too many states");
     fprintf(stderr, "Error: The dfa states are too disperse. Can't fit delta 
into a short.\n");
     exit(EXIT_FAILURE);
@@ -436,16 +449,15 @@ print_c_dfa(FILE *of, const char *name, 
          name, pdfa->last_state + 1);
   for (i = 0; i != pdfa->last_state + 1; i++) {
     int j;
-    fprintf(of, "{%d,", pdfa->states[i].att);
-    fprintf(of, "{");
+    fprintf(of, "{{");
     for (j = 0; j < 4; j++) {
       int n = pdfa->states[i].next[j];
-      assert((n == 0) || ((n - i > 0) && (n - i < 65535)));
+      assert((n == 0) || (abs(n - i) < 32768));
       fprintf(of, "%d", n ? n - i : 0);
       if (j != 3)
         fprintf(of, ",");
     }
-    fprintf(of, "}},%s", ((i+1)%3 ? "\t" : "\n"));
+    fprintf(of, "}, %d},%s", pdfa->states[i].att, ((i+1)%3 ? "\t" : "\n"));
   }
   fprintf(of, "};\n\n");
 
@@ -816,11 +828,11 @@ dfa_minmax_delta(dfa_t *pdfa, int next_i
   return ret;
 }
 
+#define DFA_ALIGN      2
 
 /*
  * Re-orders DFA into a canonical form, which does a half-hearted 
- * attempt to reduce the size of jumps for all states entries, and
- * guarantees the jumps are all forward-only.
+ * attempt to reduce the size of jumps for all states entries.
  */
 void
 dfa_shuffle(dfa_t *pdfa)
@@ -852,11 +864,13 @@ dfa_shuffle(dfa_t *pdfa)
     for (i = 0; i < q1p; i++) {
       for (j = 0; j < 4; j++) {
         int n = pdfa->states[queue1[i]].next[j];
-        if (n && !state_to[n]) {
+       /* next_new_state = DFA_ALIGN * ((next_new_state-1) / DFA_ALIGN) + 1;*/
+        while (n && !state_to[n]) {
           state_to[n] = next_new_state;
           state_from[next_new_state] = n;
           next_new_state++;
           queue2[q2p++] = n;
+         n = pdfa->states[n].next[0];
         }
       }
     }
@@ -912,7 +926,6 @@ dfa_calculate_max_matched_patterns(dfa_t
     for (i = 0; i < 4; i++) {
       int next = pdfa->states[k].next[i];
       if (next != 0) {
-       assert(next > k);
 
        if (state_max[next] < state_max[k])
          state_max[next] = state_max[k];
@@ -952,7 +965,6 @@ dfa_finalize(dfa_t *pdfa) 
   compactify_att(pdfa);
 }
 
-
 /*
  * Add a new string with attribute att_val into the dfa.
  * if the new size of the dfa respect some size conditions
Index: patterns/dfa.h
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.h,v
retrieving revision 1.28
diff -u -p -r1.28 dfa.h
--- patterns/dfa.h      8 Jun 2004 05:52:26 -0000       1.28
+++ patterns/dfa.h      11 Sep 2004 16:04:34 -0000
@@ -24,7 +24,7 @@
 #define _DFA_H_
 
 
-#define DFA_MAX_BOARD          21
+#define DFA_MAX_BOARD          MAX_BOARD
 #define DFA_MAX_ORDER          ((2 * DFA_MAX_BOARD - 1)        \
                                 * (2 * DFA_MAX_BOARD - 1))
 #define DFA_BASE               (3 * DFA_MAX_BOARD)
@@ -42,9 +42,6 @@
 /* Maximum pattern matched at one positions. */
 #define DFA_MAX_MATCHED                (8 * 24)
 
-/* Conversion macro. */
-#define EXPECTED_COLOR(player_c, position_c)   (convert[player_c][position_c])
-
 
 /* DFA spiral order. */
 extern int spiral[DFA_MAX_ORDER][8];
@@ -65,8 +62,8 @@ typedef struct attrib_rt
 /* DFA state. */
 typedef struct state_rt
 {
+  short next[4];
   short att;
-  unsigned short next[4];
 } state_rt_t;
 
 typedef struct dfa_rt
@@ -82,15 +79,6 @@ typedef struct dfa_rt
 } dfa_rt_t;
 
 
-#if 0
-/* Scan order. */
-typedef struct
-{
-  int i;
-  int j;
-} order_t;
-#endif
-
 
 #endif /* _DFA_H_ */