[gnugo-devel] dfa size reduction

[Paul Pogonyshev]

actually, it doesn't reduce the size of dfa, but the size of the list of 
attributes. i just noticed that there are _very_ many repeating pairs in
those lists and hacked in a new function named compactify_att() into dfa.c.
it calls itself recursively, removing all repetitions found.

this patch also fixes misleading comments by mkpat utility which printed the 
size of dfa in dfa.c (which used ints), not the size of dfa used by gnugo 
(with shorts). thus, all sizes were actually two times less they were 
displayed previously.

compactifying is almost instant, at least it printed debug messages instantly 
(the messages are commented out with if (0) in the patch, but you can see 
them below and valuate how _really_ effective the patch is :D

to ensure that i haven't broken anything, i ran the first batch (with owl.tst 
and atari_atari.tst) and got no changes (as it should have been).

- mkpat now displays the real size of dfa
- dfa attributes list is now compactified, leading to saved 30k

well, the gain is rather smallish, but it doesn't hurt either.


        BEFORE
---------------------------
dfa for aa_attackpat
size: 3 kB for 15 patterns(286 states)
---------------------------
dfa for owl_attackpat
size: 251 kB for 321 patterns(24494 states)
---------------------------
dfa for owl_vital_apat
size: 11 kB for 52 patterns(1126 states)
---------------------------
dfa for owl_defendpat
size: 351 kB for 424 patterns(33969 states)
---------------------------

        AFTER
---------------------------
compactified: 15 attributes left of 27
dfa for aa_attackpat
size: 2 kB for 15 patterns(286 states)
---------------------------
compactified: 1033 attributes left of 3187
compactified: 458 attributes left of 1033
compactified: 392 attributes left of 458
compactified: 387 attributes left of 392
compactified: 386 attributes left of 387
dfa for owl_attackpat
size: 240 kB for 321 patterns(24494 states)
---------------------------
compactified: 64 attributes left of 102
compactified: 57 attributes left of 64
compactified: 54 attributes left of 57
dfa for owl_vital_apat
size: 11 kB for 52 patterns(1126 states)
---------------------------
compactified: 1926 attributes left of 5111
compactified: 1013 attributes left of 1926
compactified: 541 attributes left of 1013
compactified: 511 attributes left of 541
compactified: 497 attributes left of 511
compactified: 494 attributes left of 497
dfa for owl_defendpat
size: 333 kB for 424 patterns(33969 states)
---------------------------


Paul


Index: dfa.c
===================================================================
RCS file: /cvsroot/gnugo/gnugo/patterns/dfa.c,v
retrieving revision 1.20
diff -u -p -r1.20 dfa.c
--- dfa.c       12 Nov 2002 16:21:56 -0000      1.20
+++ dfa.c       30 Nov 2002 00:04:09 -0000
@@ -228,14 +228,14 @@ buildSpiralOrder(int order[8][MAX_ORDER]
 static int
 member_att(dfa_t *pdfa, int att, int val)
 {
-  int res;
-
-  res = 0;
-  while (!res && att != 0) {
-    res = (pdfa->indexes[att].val == val);
+  while (att != 0) {
+    if (pdfa->indexes[att].val == val)
+      return 1;
+
     att = pdfa->indexes[att].next;
   }
-  return res;
+
+  return 0;
 }

 /*
@@ -283,6 +283,70 @@ union_att(dfa_t *pdfa, dfa_t *pdfa1, int
   return att;
 }

+
+/* Remove all attribute entry repetitions from a dfa.
+ */
+static void compactify_att(dfa_t *pdfa)
+{
+  int k;
+  int last = 0;
+  int save_last = pdfa->lastIndex;
+  int *map;
+  int *search_first;
+  int *search_next;
+  int size = (save_last + 1) * sizeof(int);
+
+  map = malloc(size);
+  map[0] = 0;
+  search_first = malloc(size);
+  memset(search_first, 0, size);
+  search_next = malloc(size);
+  memset(search_next, 0, size);
+
+  for (k = 1; k <= save_last; k++) {
+    int i = search_first[pdfa->indexes[k].val];
+
+    if (i) {
+      while (pdfa->indexes[i].next != pdfa->indexes[k].next) {
+       if (!search_next[i]) {
+         search_next[i] = ++last;
+         i = 0;
+         break;
+       }
+
+       i = search_next[i];
+      }
+    }
+    else
+      search_first[pdfa->indexes[k].val] = ++last;
+
+    if (i)
+      map[k] = i;
+    else {
+      map[k] = last;
+      pdfa->indexes[last] = pdfa->indexes[k];
+    }
+  }
+
+  pdfa->lastIndex = last;
+  for (k = 0; k <= pdfa->lastIndex; k++)
+    pdfa->indexes[k].next = map[pdfa->indexes[k].next];
+
+  for (k = 0; k <= pdfa->lastState; k++)
+    pdfa->states[k].att = map[pdfa->states[k].att];
+
+  free(map);
+  free(search_first);
+  free(search_next);
+
+  if (last < save_last) {
+    if (0)
+      fprintf(stderr, "compactified: %d attributes left of %d\n", last, 
save_last);
+    compactify_att(pdfa);
+  }
+}
+
+
 /**********************
  * manipulating dfa's *
  **********************/
@@ -297,10 +361,10 @@ dfa_size(dfa_t *pdfa)
 {
   int states_size, indexes_size;

-  states_size = (pdfa->lastState + 1) * sizeof(state_t);
-  indexes_size = (pdfa->lastIndex + 1) * sizeof(attrib_t);
+  states_size = (pdfa->lastState + 1) * sizeof(state_rt_t);
+  indexes_size = (pdfa->lastIndex + 1) * sizeof(attrib_rt_t);

-  return (states_size + indexes_size + sizeof(dfa_t)) / 1024;
+  return (states_size + indexes_size + sizeof(dfa_rt_t)) / 1024;
 }


@@ -337,7 +401,6 @@ resize_dfa(dfa_t *pdfa, int maxStates, i
   pdfa->maxStates = maxStates;
   pdfa->indexes = pBuf2;
   pdfa->maxIndexes = maxIndexes;
-
 }


@@ -861,6 +924,8 @@ dfa_finalize(dfa_t *pdfa)
     next_bin = aux_count;
   }
   copy_dfa(pdfa, &aux_dfa[last_bin % DFA_BINS]);
+
+  compactify_att(pdfa);
 }


@@ -1100,7 +1165,6 @@ pattern_2_string(struct pattern *pat, ch

   if (0 && dfa_verbose > 0)
     fprintf(stderr, "converted pattern %s into string: %s\n", pat->name, 
str);
-
 }