Subject: bug#17377: closed (Re: bug#17377: [PATCH] dfa: optimization of memory allocation)

From: [email-masked] (GNU bug Tracking System)
Date: Wed, 30 Apr 2014 19:25:03 +0000

Your bug report

#17377: [PATCH] dfa: optimization of memory allocation

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].

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

Subject: Re: bug#17377: [PATCH] dfa: optimization of memory allocation
From: Paul Eggert <[email-masked]>
To: Norihiro Tanaka <[email-masked]>, [email-masked]
Date: Wed, 30 Apr 2014 12:24:15 -0700
List-Id: <debbugs-submit.debbugs.gnu.org>

Thanks, I installed that.

Subject: [PATCH] dfa: optimization of memory allocation
From: Norihiro Tanaka <[email-masked]>
To: [email-masked]
Date: Thu, 01 May 2014 00:07:37 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

Previously, I fixed it in dfamust().  Now fix them in epsclosure() and
dfastate().

I tested it with below, running vmstat.

  $ echo a | env LC_ALL=C src/grep -f /usr/share/dict/linux.words

Norihiro
From 01b8adb4470d9e7fe0dd8c3b8bf8622fd0875841 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Wed, 30 Apr 2014 16:53:44 +0900
Subject: [PATCH] dfa: optimization of memory allocation

* src/dfa.c (epsclosure): get the value of `visited' from the argument.
(dfaanalyze): Define and allocate variable `visited'.
(dfastate): Use not `insert' but `merge' to insert of positions for
state 0 of DFA.
---
 src/dfa.c | 28 ++++++++++++++++------------
 1 file changed, 16 insertions(+), 12 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 362de2c..d532b81 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -2129,13 +2129,11 @@ state_index (struct dfa *d, position_set const *s, int context)
    constraint.  Repeat exhaustively until no funny positions are left.
    S->elems must be large enough to hold the result.  */
 static void
-epsclosure (position_set * s, struct dfa const *d)
+epsclosure (position_set * s, struct dfa const *d, char *visited)
 {
   size_t i, j;
   position p, old;
-
-  /* Array of booleans, large enough to use char, not int.  */
-  char *visited = xzalloc (d->tindex);
+  bool initialized = false;
 
   for (i = 0; i < s->nelem; ++i)
     if (d->tokens[s->elems[i].index] >= NOTCHAR
@@ -2144,6 +2142,11 @@ epsclosure (position_set * s, struct dfa const *d)
         && d->tokens[s->elems[i].index] != MBCSET
         && d->tokens[s->elems[i].index] < CSET)
       {
+        if (!initialized)
+          {
+            memset (visited, 0, d->tindex * sizeof (*visited));
+            initialized = true;
+          }
         old = s->elems[i];
         p.constraint = old.constraint;
         delete (s->elems[i], s);
@@ -2184,8 +2187,6 @@ epsclosure (position_set * s, struct dfa const *d)
         /* Force rescan to start at the beginning.  */
         i = -1;
       }
-
-  free (visited);
 }
 
 /* Returns the set of contexts for which there is at least one
@@ -2312,6 +2313,7 @@ dfaanalyze (struct dfa *d, int searchflag)
   int separate_contexts;        /* Context wanted by some position.  */
   size_t i, j;
   position *pos;
+  char *visited = xnmalloc (d->tindex, sizeof *visited);
 
 #ifdef DEBUG
   fprintf (stderr, "dfaanalyze:\n");
@@ -2470,7 +2472,7 @@ dfaanalyze (struct dfa *d, int searchflag)
         putc ('\n', stderr);
 #endif
         copy (&d->follows[i], &merged);
-        epsclosure (&merged, d);
+        epsclosure (&merged, d, visited);
         copy (&merged, &d->follows[i]);
       }
 
@@ -2479,7 +2481,7 @@ dfaanalyze (struct dfa *d, int searchflag)
   merged.nelem = 0;
   for (i = 0; i < stk[-1].nfirstpos; ++i)
     insert (firstpos[i], &merged);
-  epsclosure (&merged, d);
+  epsclosure (&merged, d, visited);
 
   /* Build the initial state.  */
   separate_contexts = state_separate_contexts (&merged);
@@ -2490,6 +2492,7 @@ dfaanalyze (struct dfa *d, int searchflag)
   free (posalloc);
   free (stkalloc);
   free (merged.elems);
+  free (visited);
 }

@@ -2733,10 +2736,11 @@ dfastate (state_num s, struct dfa *d, state_num trans[])
 
       /* If we are building a searching matcher, throw in the positions
          of state 0 as well.  */
-      if (d->searchflag
-          && (!d->multibyte || !next_isnt_1st_byte))
-        for (j = 0; j < d->states[0].elems.nelem; ++j)
-          insert (d->states[0].elems.elems[j], &follows);
+      if (d->searchflag && (!d->multibyte || !next_isnt_1st_byte))
+        {
+          merge (&d->states[0].elems, &follows, &tmp);
+          copy (&tmp, &follows);
+        }
 
       /* Find out if the new state will want any context information.  */
       possible_contexts = charclass_context (labels[i]);
-- 
1.9.2