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

[Akim Demaille]

Hi Théophile, Hi Yuri

> Le 23 janv. 2014 à 23:25, Yuri <address@hidden> a écrit :
> 
> On 12/26/2012 09:27, Théophile Ranquet wrote:
>>>> 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:
> 
> Sorry for my late response. This is what happens when issues are tracked via 
> the mailing list.
> 
> No, I meant exactly "50 times faster", this is what I observed.
> 
> So is this bottleneck fix checked in now?

_Now_ it is :)

The patch follows your initial idea, but is sufficiently rewritten to free us 
from the need to have the disclaimers signed.  So I'm installing the following 
version.

Cheers!

commit af1c6f973a60a51c609903713ff8f7fce0887025
Author: Theophile Ranquet <address@hidden>
Date:   Tue Nov 13 10:38:49 2012 +0000

   tables: use bitsets for a performance boost

   Suggested by Yuri at
   <http://lists.gnu.org/archive/html/bison-patches/2012-01/msg00000.html>.

   The improvement is marginal for most grammars, but notable for large
   grammars (e.g., PosgreSQL's postgre.y), and very large for the
   sample.y grammar submitted by Yuri in
   http://lists.gnu.org/archive/html/bison-patches/2012-01/msg00012.html.
   Measured with --trace=time -fsyntax-only.

   parser action tables    postgre.y     sample.y
   Before                 0,129 (44%)  37,095 (99%)
   After                  0,117 (42%)   5,046 (93%)

   * src/tables.c (pos): Replace this set of integer coded as an unsorted
   array or integers with...
   (pos_set): this bitset.

diff --git a/src/tables.c b/src/tables.c
index bea64ead..39434e77 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 *conflrow;
unsigned *conflict_table;
@@ -150,20 +153,23 @@ table_grow (int desired)
    table_size *= 2;

  if (trace_flag & trace_resource)
-    fprintf (stderr, "growing table and check from: %d to %d\n",
+    fprintf (stderr, "growing tables from %d to %d\n",
             old_size, table_size);

  table = xnrealloc (table, table_size, sizeof *table);
+  memset (table + old_size, 0,
+          sizeof *table * (table_size - old_size));
+
  conflict_table = xnrealloc (conflict_table, table_size,
                              sizeof *conflict_table);
+  memset (conflict_table + old_size, 0,
+          sizeof *conflict_table * (table_size - old_size));
+
  check = xnrealloc (check, table_size, sizeof *check);
+  for (int i = old_size; i < table_size; ++i)
+    check[i] = -1;

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


@@ -659,10 +665,8 @@ pack_vector (vector_number vector)
              ok = false;
          }

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

      if (ok)
@@ -720,7 +724,7 @@ static void
pack_table (void)
{
  base = xnmalloc (nvectors, sizeof *base);
-  pos = xnmalloc (nentries, sizeof *pos);
+  pos_set = bitset_create (table_size + nstates, BITSET_FRUGAL);
  table = xcalloc (table_size, sizeof *table);
  conflict_table = xcalloc (table_size, sizeof *conflict_table);
  check = xnmalloc (table_size, sizeof *check);
@@ -746,7 +750,12 @@ pack_table (void)
        /* Action of I were already coded for S.  */
        place = base[s];

-      pos[i] = place;
+      /* Store PLACE into POS_SET.  PLACE might not belong to the set
+         of possible values for instance with useless tokens.  It
+         would be more satisfying to eliminate the need for this
+         'if'.  */
+      if (0 <= nstates + place)
+        bitset_set (pos_set, nstates + place);
      base[order[i]] = place;
    }

@@ -754,7 +763,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);
}