Fwd: [patch] Fix of the CPU bottleneck in pack_vector

[Yuri]

Hello,

I reported this issue with the testcase and patch in Jan 2012.
Now I see that you didn't apply it as of 2.7 (Dec 2012).
Why didn't you apply it? It fixes the algorithmic bottleneck in bison 
that I am sure someone else will hit it sooner or later.

Also why there is no bug tracking page for bison? How can people 
meaningfully track issues without the bug tracker?

Thanks,
Yuri


-------- Original Message --------
Subject:        [patch] Fix of the CPU bottleneck in pack_vector
Date:   Fri, 13 Jan 2012 16:31:34 -0800
From:   Yuri <y...@rawbw.com>
To:     bison-patc...@gnu.org



Hi bison maintainers,

The attached patch fixes the CPU problem that these lines in pack_vector
function caused in certain testcases:
       for (k = 0; ok && k < vector; k++)
         if (pos[k] == j)
           ok = false;

In the version 2.5, pos array essentially represents the integer set
with unique integers placed into it in the random order.
In the above code section, pos is linearly scrolled through every time
some j is tested for the set membership, and this was 98.5% CPU in
certain testcases.

What this patch does:
it replaces pos integer array with pos_set boolean array. pos_set
represents the same integer set as pos did, but in a way of membership
bit indexed by the integer.
Such that set insertion and membership testing operations are done in
one quick step at the expense of a little more memory allocated. Before
insertion was quick, but membership testing was slow and caused the CPU
bottleneck.

I believe this patch will speed any sizable test case up.

Please let me know if you find any problem with the patch.

Thanks,
Yuri



--- src/tables.c.orig   2012-01-13 16:04:30.000000000 -0800
+++ src/tables.c        2012-01-13 16:08:40.000000000 -0800
@@ -111,7 +111,9 @@
    computation equals to BASE_MINIMUM, later mapped to BASE_NINF to
    keep parser tables small.  */
 base_number base_ninf = 0;
-static base_number *pos = NULL;
+static char *pos_set = NULL;
+/* Boolean vector representing an integer set in the range
+   -nstates..table_size (as an upper bound) */
 
 static unsigned int *conflrow;
 unsigned int *conflict_table;
@@ -158,12 +160,14 @@
   conflict_table = xnrealloc (conflict_table, table_size,
                              sizeof *conflict_table);
   check = xnrealloc (check, table_size, sizeof *check);
+  pos_set = xnrealloc (pos_set, nstates+table_size, sizeof *pos_set);
 
   for (/* Nothing. */; old_size < table_size; ++old_size)
     {
       table[old_size] = 0;
       conflict_table[old_size] = 0;
       check[old_size] = -1;
+      pos_set[nstates+old_size] = 0;
     }
 }
 
@@ -703,9 +707,8 @@
            ok = false;
        }
 
-      for (k = 0; ok && k < vector; k++)
-       if (pos[k] == j)
-         ok = false;
+      if (ok && pos_set[nstates+j])
+       ok = false;
 
       if (ok)
        {
@@ -764,7 +767,7 @@
   int i;
 
   base = xnmalloc (nvectors, sizeof *base);
-  pos = xnmalloc (nentries, sizeof *pos);
+  pos_set = xcalloc (nstates+table_size, sizeof *pos_set);
   table = xcalloc (table_size, sizeof *table);
   conflict_table = xcalloc (table_size, sizeof *conflict_table);
   check = xnmalloc (table_size, sizeof *check);
@@ -790,7 +793,7 @@
        /* Action of I were already coded for S.  */
        place = base[s];
 
-      pos[i] = place;
+      pos_set[nstates+place] = 1; /*place now belongs to pos set*/
       base[order[i]] = place;
     }
 
@@ -798,7 +801,7 @@
   base_ninf = table_ninf_remap (base, nvectors, BASE_MINIMUM);
   table_ninf = table_ninf_remap (table, high + 1, ACTION_NUMBER_MINIMUM);
 
-  free (pos);
+  free (pos_set);
 }