[gnugo-devel] paul_3_13.8

[Paul Pogonyshev]

this is another matchpat patch, unrelated to the previous
ones. it removes (some) unnecessary patval entries from
the pattern databases. see comments in the patch.

no regression changes.

overall speedup is around 1% on nngs.tst. also, the size
of executable is 115 kb down. there is some potential to
improve further.

Paul


Index: patterns/mkpat.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/mkpat.c,v
retrieving revision 1.96
diff -u -p -r1.96 mkpat.c
--- patterns/mkpat.c    9 Dec 2002 23:04:17 -0000       1.96
+++ patterns/mkpat.c    15 Dec 2002 20:34:01 -0000
@@ -588,7 +588,7 @@ compute_grids(void)
 {
 #if GRID_OPT
   /*                              element: .  X  O  x  o  ,  a  ! */
-  static const unsigned int and_mask[] = { 3, 3, 3, 1, 2, 3, 3, 1 };
+  static const unsigned int and_mask[] = { 3, 3, 3, 1, 2, 3, 3, 3 };
   static const unsigned int val_mask[] = { 0, 2, 1, 0, 0, 0, 0, 0 };
 
   int ll;  /* iterate over rotations */
@@ -1528,35 +1528,73 @@ static void
 write_elements(FILE *outfile, char *name)
 {
   int node;
+  int used_nodes = 0;
 
   assert(ci != -1 && cj != -1);
 
   /* sort the elements so that least-likely elements are tested first. */
   gg_sort(elements, el, sizeof(struct patval_b), compare_elements);
 
-  fprintf(outfile, "static struct patval %s%d[] = {\n", name, patno);
+  fprintf(outfile, "static struct patval %s%d[] = {", name, patno);
 
-  /* This may happen for fullboard patterns. */
-  if (el == 0) {
-    fprintf(outfile, "  {0,-1}}; /* Dummy element, not used. */\n\n");
-    return;
-  }
-  
-  for (node = 0;node < el; node++) {
-    assert(elements[node].x >= mini && elements[node].y >= minj);
-    if (!(elements[node].x <= maxi && elements[node].y <= maxj)) {
+  for (node = 0; node < el; node++) {
+    int x = elements[node].x;
+    int y = elements[node].y;
+    int att = elements[node].att;
+
+    assert(x >= mini && y >= minj);
+    if (!(x <= maxi && y <= maxj)) {
       fprintf(stderr, 
              "%s(%d) : error : Maximum number of elements exceeded in %s.\n",
              current_file, current_line_number, name);
       fatal_errors++;
     }
 
-    fprintf(outfile, "  {%d,%d}%s",
-           OFFSET(elements[node].x - ci, elements[node].y - cj),
-           elements[node].att,
-            node < el-1 ?  ((node + 1) % 4 ? ",\t" : ",\n")  : "};\n\n");
+#if GRID_OPT == 1
+    /* If we do grid optimization, we can avoid matching 9 pattern elements
+     * around its anchor (the 9 elements are the intersection of 16 grid
+     * elements for all possible transformations).
+     */
+    if (!dfa_generate && ci-1 <= x && x <= ci+1 && cj-1 <= y && y <= cj+1) {
+      /* Unfortunately, callback function might need these elements. We
+       * can only safely discard dots here.
+       *
+       * FIXME: Implement a smarter, pattern class/database based,
+       *       filtering of unneeded elements. It will speed up
+       *       pattern matching and reduce database sizes somewhat.
+       *       E.g. it seems that no databases but aa_attackpat.db
+       *       can have opponent stones in goal etc.
+       */
+      if (att == ATT_dot)
+       continue;
+    }
+#endif /* GRID_OPT == 1 */
+
+    /* DFA pattern matcher doesn't itself need these elements at all. But
+     * they are needed for goal checking and callback functions (same as
+     * above).
+     */
+    if (dfa_generate && att == ATT_dot)
+      continue;
+
+    if (used_nodes)
+      fprintf(outfile, ",");
+    fprintf(outfile, used_nodes % 4 ? "\t" : "\n  ");
+    used_nodes++;
+
+    fprintf(outfile, "{%d,%d}", OFFSET(x - ci, y - cj), att);
   }
 
+  /* This may happen for fullboard patterns or if we have discarded all
+   * the elements as unneeded by the matcher.
+   */
+  if (!used_nodes)
+    fprintf(outfile, "{0,-1}}; /* Dummy element, not used. */\n\n");
+  else
+    fprintf(outfile, "\n};\n\n");
+
+  pattern[patno].patlen = used_nodes;
+
 #if EXPERIMENTAL_READING
   if (tree_output)
     tree_push_pattern();
@@ -2383,9 +2421,9 @@ main(int argc, char *argv[])
        if (state == 2 || state == 3) {
          finish_pattern(line);
          
-         write_elements(output_FILE, argv[gg_optind]);
          if (dfa_generate)
            write_to_dfa(patno);
+         write_elements(output_FILE, argv[gg_optind]);
          state = 4;
        }
        else {