Re: [gnugo-devel] DFA micro optimization

[Paul Pogonyshev]

I wrote:

> Arend wrote:
>
> > A couple of micro-optimization of the DFA code:
> > 1. Diffent ordering of states (allow backward jumps, empty intersection
> > means go exactly one forward)
>
> I have that feeling it will break DFA iterational optimizer,
> not sure why though (some vague memory).  Can you check if
> it still works after your patch?

I remembered what I was worrying about:
dfa_calculate_max_matched_patterns() assumes that all jumps
are forward jumps.  The patch below generalizes it for
arbitrary order of states.  Please merge it with your DFA
optimizations.  They shouldn't go into 3.6 anyway, right?

Paul


--- dfa.c       08 Jun 2004 15:51:40 -0200      1.37
+++ dfa.c       13 Sep 2004 01:18:32 -0200      
@@ -887,39 +887,53 @@ dfa_shuffle(dfa_t *pdfa)
 /* Calculate the maximal number of patterns matched at one point for
  * one transformation.  Multiplying this number by 8 gives an upper
  * bound for the total number of matched patterns for all
- * transformation.  The DFA must be shuffled before calling this
- * function (to ensure that all jumps go forward).
+ * transformation.
  */
 int
 dfa_calculate_max_matched_patterns(dfa_t *pdfa)
 {
   int total_max = 0;
   int *state_max = calloc(pdfa->last_state + 1, sizeof(int));
-  int k;
-
-  for (k = 1; k <= pdfa->last_state; k++) {
-    int i;
+  char *queued = calloc(pdfa->last_state + 1, sizeof(char));
+  int *queue = malloc(pdfa->last_state * sizeof(int));
+  int queue_start = 0;
+  int queue_end = 1;
+
+  queue[0] = 1;
+  while (queue_start < queue_end) {
+    int state = queue[queue_start++];
+    int k;
 
     /* Increment maximal number of matched patterns for each pattern
-     * matched at state `k'.
+     * matched at current `state'.
      */
-    for (i = pdfa->states[k].att; i; i = pdfa->indexes[i].next)
-      state_max[k]++;
+    for (k = pdfa->states[state].att; k; k = pdfa->indexes[k].next)
+      state_max[state]++;
+
+    if (total_max < state_max[state])
+      total_max = state_max[state];
 
-    if (total_max < state_max[k])
-      total_max = state_max[k];
+    for (k = 0; k < 4; k++) {
+      int next = pdfa->states[state].next[k];
 
-    for (i = 0; i < 4; i++) {
-      int next = pdfa->states[k].next[i];
       if (next != 0) {
-       assert(next > k);
+       if (!queued[next]) {
+         queue[queue_end++] = next;
+         queued[next] = 1;
+       }
 
-       if (state_max[next] < state_max[k])
-         state_max[next] = state_max[k];
+       if (state_max[next] < state_max[state])
+         state_max[next] = state_max[state];
       }
     }
   }
 
+  assert(queue_end == pdfa->last_state);
+
+  free(state_max);
+  free(queued);
+  free(queue);
+
   return total_max;
 }