Subject: [PATCH] grep: optimization of DFA by reuse of multi-byte buffers in non-UTF8 locales
From: Norihiro Tanaka <[email-masked]>
To: [email-masked]
Date: Sun, 23 Mar 2014 22:19:36 +0900
List-Id: <debbugs-submit.debbugs.gnu.org>

Package: grep
Tags: patch

dfaexec() allocates and deallocates many buffers in non-UTF8 locales, but
it's very inefficient.

If put them on struct dfa and reuse them, when use not regex but DFA for
ANYCHAR, it will speed up about 20-30% in non-UTF8 locales.

Norihiro
From e56992c4bfdb2e02a114b14c34780672a9c8cee9 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sun, 23 Mar 2014 20:14:33 +0900
Subject: [PATCH] grep: optimization of DFA by reuse of multi-byte buffers in
 non-UTF8 locales

* src/dfa.c (struct dfa): New members `mblen_buf', `nmblen_buf',
`inputwcs', `ninputwcs', `mb_follows' and `mb_match_lens'.
(SKIP_REMAINS_MB_IF_INITIAL_STATE): Use them instead of global variables.
(match_anychar): Use them instead of global variables.
(match_mb_charset): Use them instead of global variables.
(check_matching_with_multibyte_ops): Use it instead of new allocation.
(transit_state_consume_1char): Use them instead of global variables.
(transit_state): Use them instead of global variables.
(prepare_wc_buf): Use them instead of global variables.
(dfaexec): Initializations of new members.
(free_mbdata): Memory Deallocations for new members.
---
 src/dfa.c | 124 +++++++++++++++++++++++++++++++-------------------------------
 1 file changed, 63 insertions(+), 61 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index 5e60cd5..73e2432 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -424,6 +424,30 @@ struct dfa
   struct dfamust *musts;        /* List of strings, at least one of which
                                    is known to appear in any r.e. matching
                                    the dfa.  */
+  unsigned char *mblen_buf;     /* Correspond to the input buffer in dfaexec.
+                                   Each element stores the number of remaining
+                                   bytes of the corresponding multibyte
+                                   character in the input string.  A element's
+                                   value is 0 if the corresponding character is
+                                   single-byte.
+                                   e.g., input : 'a', <mb(0)>, <mb(1)>, <mb(2)>
+                                   mblen_buf   :  0,       3,       2,       1
+                                 */
+  size_t nmblen_buf;            /* Length of the mblen buffer currently
+                                   allocated.  */
+  wchar_t *inputwcs;            /* Wide character representation of the input
+                                   string in dfaexec.
+                                   The length of this array is the same as
+                                   the length of input string (char array).
+                                   inputstring[i] is a single-byte char,
+                                   or the first byte of a multibyte char;
+                                   inputwcs[i] is the codepoint.  */
+  size_t ninputwcs;             /* Length of the input wide characters
+                                   currently allocated.  */
+  position_set *mb_follows;     /* Follow set added by ANYCHAR and/or MBCSET
+                                   on demand.  */
+  int *mb_match_lens;           /* Array of length reduced by ANYCHAR and/or
+                                   MBCSET.  */
 };
 
 /* Some macros for user access to dfa internals.  */
@@ -806,22 +830,6 @@ static int cur_mb_len = 1;      /* Length of the multibyte representation of
 static mbstate_t mbs;           /* Mbstate for mbrlen.  */
 static wchar_t wctok;           /* Wide character representation of the current
                                    multibyte character.  */
-static unsigned char *mblen_buf;/* Correspond to the input buffer in dfaexec.
-                                   Each element stores the number of remaining
-                                   bytes of the corresponding multibyte
-                                   character in the input string.  A element's
-                                   value is 0 if the corresponding character is
-                                   single-byte.
-                                   e.g., input : 'a', <mb(0)>, <mb(1)>, <mb(2)>
-                                   mblen_buf   :  0,       3,       2,       1
-                                 */
-static wchar_t *inputwcs;       /* Wide character representation of the input
-                                   string in dfaexec.
-                                   The length of this array is the same as
-                                   the length of input string (char array).
-                                   inputstring[i] is a single-byte char,
-                                   or the first byte of a multibyte char;
-                                   inputwcs[i] is the codepoint.  */
 static unsigned char const *buf_begin;  /* reference to begin in dfaexec.  */
 static unsigned char const *buf_end;    /* reference to end in dfaexec.  */
 
@@ -2907,14 +2915,12 @@ build_state_zero (struct dfa *d)
 #define SKIP_REMAINS_MB_IF_INITIAL_STATE(s, p)		\
   if (s == 0)						\
     {							\
-      while (inputwcs[p - buf_begin] == 0		\
-            && mblen_buf[p - buf_begin] > 0		\
+      while (d->inputwcs[p - buf_begin] == 0		\
+            && d->mblen_buf[p - buf_begin] > 0		\
             && (unsigned char const *) p < buf_end)	\
         ++p;						\
       if ((char *) p >= end)				\
         {						\
-          free (mblen_buf);				\
-          free (inputwcs);				\
           *end = saved_end;				\
           return NULL;					\
         }						\
@@ -3008,8 +3014,8 @@ match_anychar (struct dfa *d, state_num s, position pos, size_t idx)
   wchar_t wc;
   int mbclen;
 
-  wc = inputwcs[idx];
-  mbclen = (mblen_buf[idx] == 0) ? 1 : mblen_buf[idx];
+  wc = d->inputwcs[idx];
+  mbclen = (d->mblen_buf[idx] == 0) ? 1 : d->mblen_buf[idx];
 
   /* Check syntax bits.  */
   if (wc == (wchar_t) eolbyte)
@@ -3050,7 +3056,7 @@ match_mb_charset (struct dfa *d, state_num s, position pos, size_t idx)
   int context;
   wchar_t wc;                   /* Current referring character.  */
 
-  wc = inputwcs[idx];
+  wc = d->inputwcs[idx];
 
   /* Check syntax bits.  */
   if (wc == (wchar_t) eolbyte)
@@ -3071,7 +3077,7 @@ match_mb_charset (struct dfa *d, state_num s, position pos, size_t idx)
   /* Assign the current referring operator to work_mbc.  */
   work_mbc = &(d->mbcsets[(d->multibyte_prop[pos.index]) >> 2]);
   match = !work_mbc->invert;
-  match_len = (mblen_buf[idx] == 0) ? 1 : mblen_buf[idx];
+  match_len = (d->mblen_buf[idx] == 0) ? 1 : d->mblen_buf[idx];
 
   /* Match in range 0-255?  */
   if (wc < NOTCHAR && work_mbc->cset != -1
@@ -3149,7 +3155,7 @@ check_matching_with_multibyte_ops (struct dfa *d, state_num s, size_t idx)
   size_t i;
   int *rarray;
 
-  MALLOC (rarray, d->states[s].mbps.nelem);
+  rarray = d->mb_match_lens;
   for (i = 0; i < d->states[s].mbps.nelem; ++i)
     {
       position pos = d->states[s].mbps.elems[i];
@@ -3189,7 +3195,7 @@ transit_state_consume_1char (struct dfa *d, state_num s,
 
   /* Calculate the length of the (single/multi byte) character
      to which p points.  */
-  *mbclen = (mblen_buf[*pp - buf_begin] == 0) ? 1 : mblen_buf[*pp - buf_begin];
+  *mbclen = (d->mblen_buf[*pp - buf_begin] == 0) ? 1 : d->mblen_buf[*pp - buf_begin];
 
   /* Calculate the state which can be reached from the state 's' by
      consuming '*mbclen' single bytes from the buffer.  */
@@ -3218,9 +3224,6 @@ transit_state_consume_1char (struct dfa *d, state_num s,
           insert (d->follows[d->states[s].mbps.elems[i].index].elems[j], pps);
     }
 
-  if (match_lens == NULL && work_mbls != NULL)
-    free (work_mbls);
-
   /* FIXME: this return value is always ignored.  */
   return rs;
 }
@@ -3268,12 +3271,11 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
       if (rs == TRANSIT_STATE_DONE)
         ++*pp;
 
-      free (match_lens);
       return s1;
     }
 
   /* This state has some operators which can match a multibyte character.  */
-  alloc_position_set (&follows, d->nleaves);
+  follows = *d->mb_follows;
 
   /* 'maxlen' may be longer than the length of a character, because it may
      not be a character but a (multi character) collating element.
@@ -3281,7 +3283,7 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
      'maxlen' bytes.  */
   transit_state_consume_1char (d, s, pp, match_lens, &mbclen, &follows);
 
-  wc = inputwcs[*pp - mbclen - buf_begin];
+  wc = d->inputwcs[*pp - mbclen - buf_begin];
   s1 = state_index (d, &follows, wchar_context (wc));
   realloc_trans_if_necessary (d, s1);
 
@@ -3298,12 +3300,10 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
                       &follows);
         }
 
-      wc = inputwcs[*pp - mbclen - buf_begin];
+      wc = d->inputwcs[*pp - mbclen - buf_begin];
       s1 = state_index (d, &follows, wchar_context (wc));
       realloc_trans_if_necessary (d, s1);
     }
-  free (match_lens);
-  free (follows.elems);
   return s1;
 }
 
@@ -3311,7 +3311,7 @@ transit_state (struct dfa *d, state_num s, unsigned char const **pp)
 /* Initialize mblen_buf and inputwcs with data from the next line.  */
 
 static void
-prepare_wc_buf (const char *begin, const char *end)
+prepare_wc_buf (struct dfa *d, const char *begin, const char *end)
 {
 #if MBS_SUPPORT
   unsigned char eol = eolbyte;
@@ -3325,35 +3325,35 @@ prepare_wc_buf (const char *begin, const char *end)
       if (remain_bytes == 0)
         {
           remain_bytes
-            = mbrtowc (inputwcs + i, begin + i, end - begin - i + 1, &mbs);
+            = mbrtowc (d->inputwcs + i, begin + i, end - begin - i + 1, &mbs);
           if (remain_bytes < 1
               || remain_bytes == (size_t) -1
               || remain_bytes == (size_t) -2
-              || (remain_bytes == 1 && inputwcs[i] == (wchar_t) begin[i]))
+              || (remain_bytes == 1 && d->inputwcs[i] == (wchar_t) begin[i]))
             {
               remain_bytes = 0;
-              inputwcs[i] = (wchar_t) begin[i];
-              mblen_buf[i] = 0;
+              d->inputwcs[i] = (wchar_t) begin[i];
+              d->mblen_buf[i] = 0;
               if (begin[i] == eol)
                 break;
             }
           else
             {
-              mblen_buf[i] = remain_bytes;
+              d->mblen_buf[i] = remain_bytes;
               remain_bytes--;
             }
         }
       else
         {
-          mblen_buf[i] = remain_bytes;
-          inputwcs[i] = 0;
+          d->mblen_buf[i] = remain_bytes;
+          d->inputwcs[i] = 0;
           remain_bytes--;
         }
     }
 
   buf_end = (unsigned char *) (begin + i);
-  mblen_buf[i] = 0;
-  inputwcs[i] = 0;              /* sentinel */
+  d->mblen_buf[i] = 0;
+  d->inputwcs[i] = 0;              /* sentinel */
 #endif /* MBS_SUPPORT */
 }
 
@@ -3391,10 +3391,18 @@ dfaexec (struct dfa *d, char const *begin, char *end,
 
   if (d->mb_cur_max > 1)
     {
-      MALLOC (mblen_buf, end - begin + 2);
-      MALLOC (inputwcs, end - begin + 2);
+      static bool mb_alloc = false;
+      REALLOC_IF_NECESSARY (d->mblen_buf, d->nmblen_buf, end - begin + 2);
+      REALLOC_IF_NECESSARY (d->inputwcs, d->ninputwcs, end - begin + 2);
       memset (&mbs, 0, sizeof (mbstate_t));
-      prepare_wc_buf ((const char *) p, end);
+      prepare_wc_buf (d, (const char *) p, end);
+      if (!mb_alloc)
+        {
+          MALLOC (d->mb_match_lens, d->nleaves);
+          MALLOC (d->mb_follows, 1);
+          alloc_position_set (d->mb_follows, d->nleaves);
+          mb_alloc = true;
+        }
     }
 
   for (;;)
@@ -3421,8 +3429,6 @@ dfaexec (struct dfa *d, char const *begin, char *end,
               if (backref)
                 {
                   *backref = 1;
-                  free (mblen_buf);
-                  free (inputwcs);
                   *end = saved_end;
                   return (char *) p;
                 }
@@ -3455,11 +3461,6 @@ dfaexec (struct dfa *d, char const *begin, char *end,
             {
               if (backref)
                 *backref = (d->states[s].backref != 0);
-              if (d->mb_cur_max > 1)
-                {
-                  free (mblen_buf);
-                  free (inputwcs);
-                }
               *end = saved_end;
               return (char *) p;
             }
@@ -3484,17 +3485,12 @@ dfaexec (struct dfa *d, char const *begin, char *end,
             ++*count;
 
           if (d->mb_cur_max > 1)
-            prepare_wc_buf ((const char *) p, end);
+            prepare_wc_buf (d, (const char *) p, end);
         }
 
       /* Check if we've run off the end of the buffer.  */
       if ((char *) p > end)
         {
-          if (d->mb_cur_max > 1)
-            {
-              free (mblen_buf);
-              free (inputwcs);
-            }
           *end = saved_end;
           return NULL;
         }
@@ -3545,6 +3541,12 @@ free_mbdata (struct dfa *d)
   free (d->mbcsets);
   d->mbcsets = NULL;
   d->nmbcsets = 0;
+
+  free (d->inputwcs);
+  if (d->mb_follows != NULL)
+    free (d->mb_follows->elems);
+  free (d->mb_follows);
+  free (d->mb_match_lens);
 }
 
 /* Initialize the components of a dfa that the other routines don't
-- 
1.9.1