Re: [gnugo-devel] yet another one speed optimization

[Paul Pogonyshev]

i wrote:
> Arend wrote:
> > > [a patch]
> >
> > This might be a good time to kill DFA_SORT. It is superceeded by the
> > newer sorting algorithms in owl.c in my opinion (I don't think anyone
> > has ever used this since it has been turned off by default).
>
> i don't have any objections of course. just wanted to keep everything
> in working state.

ok, here is a variation which kills DFA_SORT. otherwise it is identical
to the original one, which still hasn't appeared on the page, btw.

Paul


Index: engine/matchpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/engine/matchpat.c,v
retrieving revision 1.51
diff -u -p -r1.51 matchpat.c
--- engine/matchpat.c   14 Jan 2003 20:50:33 -0000      1.51
+++ engine/matchpat.c   28 Jan 2003 23:47:24 -0000
@@ -772,10 +772,6 @@ tree_initialize_pointers(struct tree_nod
 /* DFA matcher:                                                           */
 /**************************************************************************/
 
-/* If DFA_SORT, all matched patterns are sorted and checked 
- * in the same order as the standard scheme */
-#define DFA_SORT 0
-
 /* Set this to show the dfa board in action */
 /* #define DFA_TRACE 1 */
 
@@ -790,11 +786,8 @@ extern const int convert[3][4];
 
 /* Forward declarations. */
 static void dfa_prepare_for_match(int color);
-static int scan_for_patterns(dfa_rt_t *pdfa, int l, int dfa_pos,
+static int scan_for_patterns(dfa_rt_t *pdfa, int l, int *dfa_pos,
                             int *pat_list);
-#if DFA_SORT
-static int compare_int(const void *a, const void *b);
-#endif
 static void do_dfa_matchpat(dfa_rt_t *pdfa,
                            int anchor, matchpat_callback_fn_ptr callback,
                            int color, struct pattern *database,
@@ -900,7 +893,7 @@ dump_dfa_board(int m, int n)
  * Return the number of patterns found.
  */
 static int
-scan_for_patterns(dfa_rt_t *pdfa, int l, int dfa_pos, int *pat_list)
+scan_for_patterns(dfa_rt_t *pdfa, int l, int *dfa_pos, int *pat_list)
 {
   int delta;
   int state = 1; /* initial state */
@@ -911,39 +904,23 @@ scan_for_patterns(dfa_rt_t *pdfa, int l,
     /* collect patterns indexes */
     int att = pdfa->states[state].att;
     while (att != 0) {
-      if (pdfa->pre_rotated)
-        pat_list[id] = pdfa->indexes[att].val;
-      else
-        pat_list[id] = l + 8 * (int)(pdfa->indexes[att].val);
+      pat_list[id] = pdfa->indexes[att].val;
       id++;
       att = pdfa->indexes[att].next;
     }
       
     /* go to next state */
-    delta = pdfa->states[state].next[dfa_p[dfa_pos + spiral[row][l]]];
+    delta = pdfa->states[state].next[dfa_pos[spiral[row][l]]];
     state += delta;
     row++;
   } while (delta != 0); /* while not on error state */
 
-  ASSERT1(row < MAX_ORDER, dfa_pos);
+  gg_assert(row < MAX_ORDER);
   return id;
 }
 
 
-#if DFA_SORT
-/* used to sort patterns */
-static int
-compare_int(const void *a, const void *b)
-{
-  const int *da = (const int *) a;
-  const int *db = (const int *) b;
-     
-  return (*da > *db) - (*da < *db);
-}
-#endif
-
-
-/* perform pattern matching with dfa filtering */
+/* Perform pattern matching with dfa filtering. */
 static void 
 do_dfa_matchpat(dfa_rt_t *pdfa,
                int anchor, matchpat_callback_fn_ptr callback,
@@ -951,49 +928,43 @@ do_dfa_matchpat(dfa_rt_t *pdfa,
                void *callback_data, char goal[BOARDMAX],
                 int anchor_in_goal)
 {
+  int k = 0;
   int ll;      /* Iterate over transformations (rotations or reflections)  */
-  int matched; /* index in database[] of the matched pattern */
-
-  int reorder[DFA_MAX_MATCHED];
-  int *preorder = reorder;
-  int maxr = 0, k;
-  int dfa_pos = DFA_POS(I(anchor), J(anchor)) + DFA_OFFSET;
+  int patterns[DFA_MAX_MATCHED];
+  int *ll_patterns = patterns;
+  int num_matched = 0;
+  int num_transformations = (pdfa->pre_rotated ? 1 : 8);
+  int transformation_end[8];
+  int *dfa_pos = dfa_p + DFA_POS(I(anchor), J(anchor)) + DFA_OFFSET;
 
   /* Basic sanity checks. */
   ASSERT_ON_BOARD1(anchor);
 
-  /* Geometrical pattern matching */
-  maxr = 0;
-
-  /* one scan by transformation */
-  for (ll = 0; ll != 8; ll++) {
-    maxr += scan_for_patterns(pdfa, ll, dfa_pos, preorder);
-    preorder = reorder + maxr;
-    if (pdfa->pre_rotated)
-      break;
+  /* One scan by transformation */
+  for (ll = 0; ll < num_transformations; ll++) {
+    int ll_matched = scan_for_patterns(pdfa, ll, dfa_pos,
+                                      patterns + num_matched);
+    
+    ll_patterns += ll_matched;
+    num_matched += ll_matched;
+    transformation_end[ll] = num_matched;
   }
 
-  ASSERT1(maxr < DFA_MAX_MATCHED, anchor);
+  ASSERT1(num_matched <= DFA_MAX_MATCHED, anchor);
 
-  /* Sorting patterns keep the same order as 
-   * standard pattern matching algorithm */
-#if DFA_SORT
-  gg_sort(reorder, maxr, sizeof(int), compare_int);
-#endif /* DFA_SORT */
-
-
-  /* Constraints and other tests */
-
-  for (k = 0; k != maxr ; k++) {
-    matched = reorder[k] / 8;
-    ll = reorder[k] % 8;
+  /* Constraints and other tests. */
+  for (ll = 0; ll < num_transformations; ll++) {
+    while (k < transformation_end[ll]) {
+      int matched = patterns[k];
 
 #if PROFILE_PATTERNS
-    database[matched].dfa_hits++;
+      database[matched].dfa_hits++;
 #endif
     
-    check_pattern_light(anchor, callback, color, database+matched, 
-                       ll, callback_data, goal, anchor_in_goal);
+      check_pattern_light(anchor, callback, color, database + matched,
+                         ll, callback_data, goal, anchor_in_goal);
+      k++;
+    }
   }
 }