Subject: bug#15191: closed (Re: bug#15191: faster DFA.C state merge)

From: [email-masked] (GNU bug Tracking System)
Date: Sat, 17 May 2014 03:26:02 +0000

Your bug report

#15191: faster DFA.C state merge

which was filed against the grep package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to [email-masked].

-- 
15191: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=15191
GNU Bug Tracking System
Contact [email-masked] with problems

Subject: Re: bug#15191: faster DFA.C state merge
From: Paul Eggert <[email-masked]>
To: Norihiro Tanaka <[email-masked]>, [email-masked]
Cc: Ivan Yanikov <[email-masked]>
Date: Fri, 16 May 2014 20:24:54 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

Norihiro Tanaka wrote:
> If my rewriting of the patch is right, it causes slowdown rather by
> building heap.

Thanks for checking it.  I'll close this bug report, since it seems to 
have been fixed in a different way.

Subject: Re: faster DFA.C state merge
From: Ivan Yanikov <[email-masked]>
To: Paul Eggert <[email-masked]>
Cc: [email-masked]
Date: Mon, 26 Aug 2013 05:26:11 +0400
List-Id: <debbugs-submit.debbugs.gnu.org>

I have polished the patch (
     faster code for simple cases of merging 2 or 1 sets,
     fixes of code style, like fancy 2+2 indentation,
     important fix: memory leaks under valgrind - I improperly returned array from a function )

New patch available on URL https://gist.github.com/dobrokot/6337339 and included as attach

 > One thing that'd help would be a test case that illustrates the need for the patch.

Not sure how to properly to send test-case, and how to reference grep compiled old/new binary. I had put it on URL http://dobrokot.ru/dump/slow_dfa_merge.2013-08-26.tar.gz
I can send it in a attach for a "history", if binary/large attaches are allowed in maillists.
Real regex contains sensitive private data, and it's huge. So I had little obfuscated it and reduce to kilobytes. The runtime difference is not so great as in real example (1 to 100), but still large 
( 2-3 times faster ).

Times for new/old version: 2.3sec / 8.7sec

 > I assume you're willing to assign copyright to the FSF for the change?  (I can send you copies of the paperwork, if so.)

You mean, I should somewhere explicitly state, that I am agree with GPL and give FSF rights to distribute and use the code from patch?
If so, I am surely agree with the license, and (proudly) give the permission to use/distribute code from my patch :)

Or you mean some modification of authorship lines in the AUTHORS/THANKS and beginning of dfa.c, which should contain my name now ?

Which paperwork do you mean? Real paper which I should sign with pen and ink?

Thanks for attention, Ivan Yanikov.

On 25.08.2013 11:02, Paul Eggert wrote:
> Ivan Yanikov wrote:
>> How I can properly send/commit it for review?
> You've already done that, sort of, with the pointers
> to the patch.  One thing that'd help would be a test
> case that illustrates the need for the patch.  Also,
> I assume you're willing to assign copyright to the
> FSF for the change?  (I can send you copies of the
> paperwork, if so.)
>

Index: dfa.c
===================================================================
--- dfa.c	(revision grep-2.14-faster-dfa)
+++ dfa.c	(revision grep-2.14)
@@ -1992,6 +1992,133 @@
       s->elems[i] = s->elems[i + 1];
 }
 
+/* Merge implementation of sorted sets, then number of sets smore than 2.
+   Priority queue aka 'heap' data structure used to select maximum of
+   many elements */
+
+typedef struct {
+  position p;
+  size_t set_index; /* Remember which set this element was taken from */
+} heap_elem;
+
+
+static void
+heap_add (heap_elem *heap, size_t *heap_size, heap_elem e)
+{
+  size_t i = *heap_size;
+  while (i)
+    {
+      size_t parent = (i-1) / 2;
+      if (e.p.index < heap[parent].p.index)
+        break;
+
+      heap[i] = heap[parent];
+      i = parent;
+    }
+  heap[i] = e;
+  *heap_size += 1;
+}
+
+static void
+heap_remove_top_and_add (heap_elem *heap, size_t heap_size, heap_elem e)
+{
+  size_t i = 0;
+  size_t lchild  = 2*i + 1;
+  size_t n = heap_size;
+  while (lchild < n)
+    {
+      size_t rchild = lchild + 1;
+      size_t nextchild = lchild;
+      if (rchild < n && heap[lchild].p.index < heap[rchild].p.index)
+        nextchild = rchild;
+      if (e.p.index >= heap[nextchild].p.index)
+        break;
+      heap[i] = heap[nextchild];
+      i = nextchild;
+      lchild = 2*i + 1;
+    }
+  heap[i] = e;
+}
+
+
+static void
+heap_remove_top (heap_elem *heap, size_t *heap_size)
+{
+  *heap_size -= 1;
+  if (*heap_size == 0)
+    return;
+  heap_remove_top_and_add (heap, *heap_size, heap[*heap_size]);
+}
+
+static void
+heap_merge_many_sets (position_set *sets, size_t n, position_set *result)
+{
+  size_t heap_size = 0;
+  position_set r; /* faster access to local variables */
+  heap_elem *heap = XNMALLOC (n, heap_elem);
+  size_t *ids = XNMALLOC (n, size_t);
+  size_t sum_of_sizes = 0;
+  size_t i;
+
+  for (i = 0; i < n; ++i)
+    {
+      sum_of_sizes += sets[i].nelem;
+      /* special value for "end of set", to reduce
+         dependent memory reads */
+      ids[i] = ~(size_t)0;
+      if (sets[i].nelem)
+        {
+          heap_elem e = { sets[i].elems[0], i };
+          heap_add (heap, &heap_size, e);
+          if (sets[i].nelem > 1)
+            ids[i] = 1;
+        }
+    }
+
+  REALLOC_IF_NECESSARY(result->elems, result->alloc, sum_of_sizes);
+  r = *result;
+  r.nelem = 0;
+
+  while (heap_size)
+    {
+      heap_elem e = heap[0];
+      if (r.nelem && r.elems[r.nelem-1].index == e.p.index)
+        r.elems[r.nelem-1].constraint |= e.p.constraint;
+      else
+        r.elems[r.nelem++] = e.p;
+      i = e.set_index;
+      if (ids[i] != ~(size_t)0)
+        {
+          heap_elem e2 = { sets[i].elems[ids[i]], i };
+          heap_remove_top_and_add (heap, heap_size, e2);
+          ++ids[i];
+          if (ids[i] == sets[i].nelem)
+            ids[i] = ~(size_t)0;
+        }
+      else
+        {
+          heap_remove_top (heap, &heap_size);
+        }
+    }
+  *result = r;
+  free (ids);
+  free (heap);
+}
+
+static void
+merge_many_sets (position_set *sets, size_t n, position_set *result)
+{
+  /* optimized solutions for special/trivial cases */
+  if (n == 0)
+    result->nelem = 0;
+  else if (n == 1)
+    copy (&sets[0], result);
+  else if (n == 2)
+    merge (&sets[0], &sets[1], result);
+  else
+    heap_merge_many_sets(sets, n, result);
+}
+
 /* Find the index of the state corresponding to the given position set with
    the given preceding context, or create a new state if there is no such
    state.  Context tells whether we got here on a newline or letter. */
@@ -2482,13 +2609,16 @@
   charclass leftovers;          /* Stuff in the label that didn't match. */
   int leftoversf;               /* True if leftovers is nonempty. */
   position_set follows;         /* Union of the follows of some group. */
-  position_set tmp;             /* Temporary space for merging sets. */
+  position_set follows_tmp;     /* Temporary space for merging sets. */
   int possible_contexts;        /* Contexts that this group can match. */
   int separate_contexts;        /* Context that new state wants to know. */
   state_num state;              /* New state. */
   state_num state_newline;      /* New state on a newline transition. */
   state_num state_letter;       /* New state on a letter transition. */
   int next_isnt_1st_byte = 0;   /* Flag if we can't add state0.  */
+  position_set *sets = 0;       /* Temporary array of sets, to pass many sets to merge function */
+  size_t sets_n = 0;            /* Sets array size */
+  size_t sets_alloc = 0;        /* Sets array capacity   */
   size_t i, j, k;
 
   MALLOC (grps, NOTCHAR);
@@ -2607,7 +2737,7 @@
     }
 
   alloc_position_set (&follows, d->nleaves);
-  alloc_position_set (&tmp, d->nleaves);
+  alloc_position_set (&follows_tmp, d->nleaves);
 
   /* If we are a searching matcher, the default transition is to a state
      containing the positions of state 0, otherwise the default transition
@@ -2637,13 +2767,12 @@
 
   for (i = 0; i < ngrps; ++i)
     {
-      follows.nelem = 0;
-
-      /* Find the union of the follows of the positions of the group.
-         This is a hideously inefficient loop.  Fix it someday. */
+      /* Find the union of the follows of the positions of the group.  */
+      sets_n = grps[i].nelem;
+      REALLOC_IF_NECESSARY(sets, sets_alloc, sets_n);
       for (j = 0; j < grps[i].nelem; ++j)
-        for (k = 0; k < d->follows[grps[i].elems[j]].nelem; ++k)
-          insert (d->follows[grps[i].elems[j]].elems[k], &follows);
+        sets[j] = d->follows[grps[i].elems[j]];
+      merge_many_sets (sets, sets_n, &follows_tmp);
 
       if (d->mb_cur_max > 1)
         {
@@ -2666,9 +2795,9 @@
              <mb A>, so we cannot add state[0].  */
 
           next_isnt_1st_byte = 0;
-          for (j = 0; j < follows.nelem; ++j)
+          for (j = 0; j < follows_tmp.nelem; ++j)
             {
-              if (!(d->multibyte_prop[follows.elems[j].index] & 1))
+              if (!(d->multibyte_prop[follows_tmp.elems[j].index] & 1))
                 {
                   next_isnt_1st_byte = 1;
                   break;
@@ -2680,8 +2809,7 @@
          of state 0 as well. */
       if (d->searchflag
           && (!MBS_SUPPORT || (d->mb_cur_max == 1 || !next_isnt_1st_byte)))
-        for (j = 0; j < d->states[0].elems.nelem; ++j)
-          insert (d->states[0].elems.elems[j], &follows);
+        merge (&follows_tmp, &d->states[0].elems, &follows);
 
       /* Find out if the new state will want any context information. */
       possible_contexts = charclass_context (labels[i]);
@@ -2720,7 +2848,8 @@
   for (i = 0; i < ngrps; ++i)
     free (grps[i].elems);
   free (follows.elems);
-  free (tmp.elems);
+  free (sets);
+  free (follows_tmp.elems);
   free (grps);
   free (labels);
 }