Subject: Re: bug#17576: [PATCH] dfa: speed-up at initial state

From: Norihiro Tanaka <[email-masked]>
Date: Mon, 26 May 2014 23:12:50 +0900

Paul Eggert wrote:
> I guess that grep needs a performance test suite, so that we can find
> problems like this in a more-disciplined way.

I agree, but I have no idea to perform it.

BTW, I retried them on Fedora 20, but I couldn't confirm significant
slowdown.

  Intel(R) Core(TM)2 Duo CPU     E8500  @ 3.16GHz
  Fedora 20  GCC 4.8.2 20131017 (Red Hat 4.8.2-1) (x86-64)

$ yes jjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj | head -10000000 >k
$ yes j | head -100000000 >l

[ before 0001-dfa-speed-up-at-initial-state.patch ]

$ env LC_ALL=C src/grep '\(a\|b\)' k
real 0.96
user 0.85
sys 0.10
$ env LC_ALL=C src/grep '\(a\|b\)' l
real 0.64
user 0.60
sys 0.03

[ after 0001-dfa-speed-up-at-initial-state.patch ]

$ env LC_ALL=C src/grep '\(a\|b\)' k
real 0.58
user 0.52
sys 0.05
$ env LC_ALL=C src/grep '\(a\|b\)' l
real 0.75
user 0.69
sys 0.05

However, I could confirm slowdown on RHEL6 GCC 4.4.7.  According to the
result, I see that GCC fails in inlination.  In addition to
0001-dfa-speed-up-at-initial-state.patch, I applied an attached patch,
and retried them.  Then I confirmed speed-up.

$ env LC_ALL=C src/grep '\(a\|b\)' k
real 0.46
user 0.35
sys 0.10
$ env LC_ALL=C src/grep '\(a\|b\)' l
real 0.54
user 0.49
sys 0.04

Thanks,
Norihiro
From f527b4d3448a88fbc035eed2fe81df52aa8ba743 Mon Sep 17 00:00:00 2001
From: Norihiro Tanaka <[email-masked]>
Date: Sun, 25 May 2014 17:41:11 +0900
Subject: [PATCH] dfa: separate dfaexec function to help optimization by
 compiler

* src/dfa.c (dfaexec_main): Rename from dfaexec, add inline attribute.
(dfaexec_mb): New function.  Run it when d->multibyte is true.   For this
function inlination must be avoided.
(dfaexec_sb): New function.  Run it when d->multibyte is false.  For this
function inlination must be avoided.
(dfaexec): Call dfaexec_mb or dfaexec_sb accoding to d->multibyte.
---
 src/dfa.c | 35 +++++++++++++++++++++++++++++------
 1 file changed, 29 insertions(+), 6 deletions(-)

diff --git a/src/dfa.c b/src/dfa.c
index a41d002..519361f 100644
--- a/src/dfa.c
+++ b/src/dfa.c
@@ -3280,9 +3280,9 @@ skip_remains_mb (struct dfa *d, unsigned char const *p,
    Finally, if BACKREF is non-NULL set *BACKREF to indicate whether we
    encountered a back-reference (1) or not (0).  The caller may use this
    to decide whether to fall back on a backtracking matcher.  */
-char *
-dfaexec (struct dfa *d, char const *begin, char *end,
-         int allow_nl, size_t *count, int *backref)
+static inline char *
+dfaexec_main (struct dfa *d, char const *begin, char *end,
+             int allow_nl, size_t *count, int *backref, bool const multibyte)
 {
   state_num s, s1;              /* Current state.  */
   unsigned char const *p, *mbp; /* Current input character.  */
@@ -3301,7 +3301,7 @@ dfaexec (struct dfa *d, char const *begin, char *end,
   saved_end = *(unsigned char *) end;
   *end = eol;
 
-  if (d->multibyte)
+  if (multibyte)
     {
       memset (&d->mbs, 0, sizeof d->mbs);
       if (! d->mb_match_lens)
@@ -3313,7 +3313,7 @@ dfaexec (struct dfa *d, char const *begin, char *end,
 
   for (;;)
     {
-      if (d->multibyte)
+      if (multibyte)
         {
           while ((t = trans[s]) != NULL)
             {
@@ -3402,7 +3402,7 @@ dfaexec (struct dfa *d, char const *begin, char *end,
             }
 
           s1 = s;
-          if (d->multibyte)
+          if (multibyte)
             {
               /* Can match with a multibyte character (and multicharacter
                  collating element).  Transition table might be updated.  */
@@ -3447,6 +3447,29 @@ dfaexec (struct dfa *d, char const *begin, char *end,
   return (char *) p;
 }
 
+static char *__attribute__((noinline))
+dfaexec_mb (struct dfa *d, char const *begin, char *end,
+           int allow_nl, size_t *count, int *backref)
+{
+  return dfaexec_main (d, begin, end, allow_nl, count, backref, true);
+}
+
+static char *__attribute__((noinline))
+dfaexec_sb (struct dfa *d, char const *begin, char *end,
+           int allow_nl, size_t *count, int *backref)
+{
+  return dfaexec_main (d, begin, end, allow_nl, count, backref, false);
+}
+
+char *
+dfaexec (struct dfa *d, char const *begin, char *end,
+         int allow_nl, size_t *count, int *backref)
+{
+  return (d->multibyte
+    ? dfaexec_mb (d, begin, end, allow_nl, count, backref)
+    : dfaexec_sb (d, begin, end, allow_nl, count, backref));
+}
+
 struct dfa *
 dfasuperset (struct dfa const *d)
 {
-- 
1.9.3