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

[Théophile Ranquet]

2012/12/21 Akim Demaille <address@hidden>:
> Le 21 déc. 2012 à 02:32, Yuri <address@hidden> a écrit :
>
>> Hello,
>
> Hi Yuri,

Hi Yuri, hi all,

>> 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?
>
> Because it segfaults in some situations, and because it does
> not use our bitset routines, although it looks like it would
> be useful.

FWIW, I have adapted it to use our bitsets. Concerning the segfaults,
they occured on cases such as the following:

%token A 'a'
%%
exp: 'b'

where pack_vector () returned -6, but since nstates was only equal to
5, the subtraction resulted in the setting of bit -1. I have prevented
this by making sure to modify the bitset only when the result of this
substraction is positive. TBH, I am still not very familiar with these
bits of Bison's code, so I couldn't come up with a more elegant
solution, sorry.

>> It fixes the algorithmic bottleneck in bison that I am sure someone else 
>> will hit it sooner or later.

Back when you first submitted this, you said:

>I am attaching the testcase, that runs in 11 sec with my patch, and in
> maybe 50X that without.

I suppose you meant "about fifty seconds", and not "50 times that",
right? This is what I observed before and after applying your changes:

$ ./_build/tests/bison sample.y --trace=time

Execution times (seconds)
 reader                :   0,11 ( 0%) usr   0,01 (33%) sys   0,00 ( 0%) wall
 LR(0)                 :   0,11 ( 0%) usr   0,00 ( 0%) sys   0,00 ( 0%) wall
 LALR(1)               :   0,07 ( 0%) usr   0,00 ( 0%) sys   0,00 ( 0%) wall
 conflicts             :   0,01 ( 0%) usr   0,00 ( 0%) sys   0,00 ( 0%) wall
 parser action tables  :  58,67 (99%) usr   0,00 ( 0%) sys  59,00 (100%) wall
 outputing parser      :   0,21 ( 0%) usr   0,00 ( 0%) sys   0,00 ( 0%) wall
 running m4            :   0,23 ( 0%) usr   0,01 (33%) sys   0,00 ( 0%) wall
 freeing               :   0,02 ( 0%) usr   0,01 (33%) sys   0,00 ( 0%) wall
 TOTAL                 :  59,43             0,03            59,00

$ ./_build/tests/bison sample.y --trace=time

Execution times (seconds)
 reader                :   0,11 ( 1%) usr   0,00 ( 0%) sys   0,00 ( 0%) wall
 LR(0)                 :   0,11 ( 1%) usr   0,00 ( 0%) sys   1,00 ( 8%) wall
 LALR(1)               :   0,07 ( 1%) usr   0,00 ( 0%) sys   0,00 ( 0%) wall
 conflicts             :   0,02 ( 0%) usr   0,00 ( 0%) sys   0,00 ( 0%) wall
 parser action tables  :  10,31 (93%) usr   0,00 ( 0%) sys  11,00 (92%) wall
 outputing parser      :   0,22 ( 2%) usr   0,00 ( 0%) sys   0,00 ( 0%) wall
 running m4            :   0,24 ( 2%) usr   0,02 (100%) sys   0,00 ( 0%) wall
 freeing               :   0,03 ( 0%) usr   0,00 ( 0%) sys   0,00 ( 0%) wall
 TOTAL                 :  11,11             0,02            12,00

FYI, this is what it now looks like:

diff --git a/lib/bitset.h b/lib/bitset.h
index fbc7b77..e49d48e 100644
--- a/lib/bitset.h
+++ b/lib/bitset.h
@@ -180,7 +180,7 @@ bitset_test (bitset bset, bitset_bindex bitno)
 #define bitset_size(SRC) BITSET_SIZE_ (SRC)

 /* Change size of bitset.  */
-extern void bitset_resize (bitset, bitset_bindex);
+#define bitset_resize(DST, SIZE) BITSET_RESIZE_ (DST, SIZE)

 /* Return number of bits set in bitset SRC.  */
 #define bitset_count(SRC) BITSET_COUNT_ (SRC)
diff --git a/src/tables.c b/src/tables.c
index eb827b7..a98e130 100644
--- a/src/tables.c
+++ b/src/tables.c
@@ -21,6 +21,7 @@
 #include <config.h>
 #include "system.h"

+#include <bitset.h>
 #include <bitsetv.h>

 #include "complain.h"
@@ -110,7 +111,9 @@ base_number *base = NULL;
    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;
+/* Bitset representing an integer set in the range
+   -nstates..table_size (as an upper bound) */
+static bitset pos_set = NULL;

 static unsigned int *conflrow;
 unsigned int *conflict_table;
@@ -157,12 +160,14 @@ table_grow (int desired)
   conflict_table = xnrealloc (conflict_table, table_size,
                              sizeof *conflict_table);
   check = xnrealloc (check, table_size, sizeof *check);
+  bitset_resize (pos_set, table_size + nstates);

   for (/* Nothing. */; old_size < table_size; ++old_size)
     {
       table[old_size] = 0;
       conflict_table[old_size] = 0;
       check[old_size] = -1;
+      bitset_reset(pos_set, nstates + old_size);
     }
 }

@@ -702,9 +707,8 @@ pack_vector (vector_number vector)
            ok = false;
        }

-      for (k = 0; ok && k < vector; k++)
-       if (pos[k] == j)
-         ok = false;
+      if (ok && (bitset_test (pos_set, nstates + j)))
+        ok = false;

       if (ok)
        {
@@ -763,7 +767,8 @@ pack_table (void)
   int i;

   base = xnmalloc (nvectors, sizeof *base);
-  pos = xnmalloc (nentries, sizeof *pos);
+  pos_set = bitset_create (table_size + nstates, BITSET_FRUGAL);
+  bitset_zero (pos_set);
   table = xcalloc (table_size, sizeof *table);
   conflict_table = xcalloc (table_size, sizeof *conflict_table);
   check = xnmalloc (table_size, sizeof *check);
@@ -789,7 +794,9 @@ pack_table (void)
        /* Action of I were already coded for S.  */
        place = base[s];

-      pos[i] = place;
+      /* Place now belongs to pos set. */
+      if (nstates + place >= 0)
+        bitset_set (pos_set, nstates + place);
       base[order[i]] = place;
     }

@@ -797,7 +804,7 @@ pack_table (void)
   base_ninf = table_ninf_remap (base, nvectors, BASE_MINIMUM);
   table_ninf = table_ninf_remap (table, high + 1, ACTION_NUMBER_MINIMUM);

-  free (pos);
+  bitset_free (pos_set);
 }



@@ -825,6 +832,7 @@ tables_generate (void)
   conflict_tos = xcalloc (nvectors, sizeof *conflict_tos);
   tally = xcalloc (nvectors, sizeof *tally);
   width = xnmalloc (nvectors, sizeof *width);
+  pos_set = bitset_create (table_size + nstates, BITSET_FRUGAL);

   token_actions ();


We will probably install this soon.