GNU bug report logs - #32750
[PATCH 2/2] dfa: optmization of alternation in NFA

Previous Next

To add a comment to this bug, you must first unarchive it, by sending
a message to control AT debbugs.gnu.org, with unarchive 32750 in the body.
You can then email your comments to 32750 AT debbugs.gnu.org in the normal way.

Toggle the display of automated, internal messages from the tracker.

Message #5 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: <bug-grep <at> gnu.org>
Subject: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Mon, 17 Sep 2018 23:14:52 +0900

[Message part 1 (text/plain, inline)]

Hi,

Even when similer states exists in alternation, DFA treats them as
separate items.  It may complicate the transition in NFA and cause
slowdown.  This change assembles the states into one.

For example, ab|ac is changed into a(b|c).

This change speeds-up matching for many branched pattern.  For
example, grep speeds-up more than 30x in following case.

  seq 10000 | sed 's/$/ abcdefghijklmnopqrstuvwxyz/; s/$/./' >in
  time -p env LC_ALL=C grep -vf in in

  (before) real 63.43 user 61.67 system 1.65
  (after)  real  1.64 user  1.61 system 0.03

  # If we do not add '.' at last in pattern, not dfa but kwset is used.

grep also speeds-up about 3x in following case.

  time -p env LC_ALL=C grep -vf /usr/share/dict/linux.words /usr/share/dict/linux.words

  (before) real  2.48 user  2.09 system 0.38
  (after)  real  7.69 user  6.32 system 1.29

Thanks,
Norihiro

[0001-dfa-simplify-initial-state.patch (text/plain, attachment)]

[0002-dfa-optmization-of-alternation-in-NFA.patch (text/plain, attachment)]

Message #8 received at 32750 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, 32750 <at> debbugs.gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Mon, 17 Sep 2018 23:18:18 -0700

Thanks for the patch. A quick question: what does the identifier "dfautf8noss" 
stand for? I couldn't figure it out.

Message #11 received at 32750 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: 32750 <at> debbugs.gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Wed, 19 Sep 2018 00:13:30 +0900

Paul Eggert <eggert <at> cs.ucla.edu> wrote:
> Thanks for the patch. A quick question: what does the identifier "dfautf8noss" stand for? I couldn't figure it out.

It means "No use superset for utf8".

I thought of various things for the name of the function, but I could
not think of a good name.

Message #14 received at submit <at> debbugs.gnu.org (full text, mbox):

From: Paul Jackson <pj <at> usa.net>
To: bug-grep <at> gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Tue, 18 Sep 2018 11:15:54 -0500

Norihiro Tanaka wrote:
>> It means "No use superset for utf8".

Would a comment be useful,  such as in the following,
(which may have to be reworded to be correct) ?

/*   Optimize DFA,  but don't use superset (noss) for utf8 */
 static void
-dfaoptimize (struct dfa *d)
+dfautf8noss (struct dfa *d)


-- 
                Paul Jackson
                pj <at> usa.net

Message #17 received at 32750 <at> debbugs.gnu.org (full text, mbox):

From: Eric Blake <eblake <at> redhat.com>
To: Paul Jackson <pj <at> usa.net>, 32750 <at> debbugs.gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Tue, 18 Sep 2018 11:24:10 -0500

On 9/18/18 11:15 AM, Paul Jackson wrote:
> Norihiro Tanaka wrote:
>>> It means "No use superset for utf8".
> 
> Would a comment be useful,  such as in the following,
> (which may have to be reworded to be correct) ?
> 
> /*   Optimize DFA,  but don't use superset (noss) for utf8 */
>   static void
> -dfaoptimize (struct dfa *d)
> +dfautf8noss (struct dfa *d)

Or even some strategic spelling, as in:

dfa_utf8_no_ss

-- 
Eric Blake, Principal Software Engineer
Red Hat, Inc.           +1-919-301-3266
Virtualization:  qemu.org | libvirt.org

Message #22 received at 32750-done <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 32750-done <at> debbugs.gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Tue, 18 Sep 2018 21:12:18 -0700

[Message part 1 (text/plain, inline)]

Norihiro Tanaka wrote:
> I thought of various things for the name of the function, but I could
> not think of a good name.

Yes, that's a tough one. I eventually came up with maybe_disable_superset_dfa. 
Perhaps we can think of an ever better one.

I installed your patches into Gnulib, along with the attached relatively-minor 
fixups, and then propagated the result into grep by updating the Gnulib version 
that the grep master points to.

As you may notice, nowadays I prefer using signed types like ptrdiff_t to 
unsigned ones like size_t, as the signed types have a significant advantage in 
overflow checking with gcc -fsanitize=undefined. Perhaps at some point we should 
change the other instances of size_t in dfa.c, but one step at a time.

Thanks again for the performance improvement.

[0001-dfa-reorder-enum-for-efficiency.patch (text/x-patch, attachment)]

[0002-dfa-prune-states-as-we-go.patch (text/x-patch, attachment)]

[0003-dfa-tweak-allocation-performance.patch (text/x-patch, attachment)]

[0004-dfa-use-more-informative-function-name.patch (text/x-patch, attachment)]

Message #25 received at 32750 <at> debbugs.gnu.org (full text, mbox):

From: Jim Meyering <jim <at> meyering.net>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 32750 <at> debbugs.gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Tue, 18 Sep 2018 22:13:38 -0700

On Mon, Sep 17, 2018 at 7:16 AM Norihiro Tanaka <noritnk <at> kcn.ne.jp> wrote:
> Even when similer states exists in alternation, DFA treats them as
> separate items.  It may complicate the transition in NFA and cause
> slowdown.  This change assembles the states into one.
>
> For example, ab|ac is changed into a(b|c).
>
> This change speeds-up matching for many branched pattern.  For
> example, grep speeds-up more than 30x in following case.
>
>   seq 10000 | sed 's/$/ abcdefghijklmnopqrstuvwxyz/; s/$/./' >in
>   time -p env LC_ALL=C grep -vf in in
>
>   (before) real 63.43 user 61.67 system 1.65
>   (after)  real  1.64 user  1.61 system 0.03
>
>   # If we do not add '.' at last in pattern, not dfa but kwset is used.
>
> grep also speeds-up about 3x in following case.
>
>   time -p env LC_ALL=C grep -vf /usr/share/dict/linux.words /usr/share/dict/linux.words
>
>   (before) real  2.48 user  2.09 system 0.38
>   (after)  real  7.69 user  6.32 system 1.29

Thank you for the patches.
However, the before/after numbers you show here suggest that the
"after" code takes more than triple of the time of "before".

Also, when I compared grep compiled at
123620af88f55c3e0cc9f0aed7311c72f625bc82 (latest, including your
changes) and that compiled at the prior commit,
9c11510507ebcd31671f10d9b88532f8e6657ad2, I find that the new version
takes over 30 seconds, while the prior one took about 20 seconds.

FTR, I used gcc version 9.0.0 20180912, compiling with -O3.

Message #28 received at 32750 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Jim Meyering <jim <at> meyering.net>, Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Cc: 32750 <at> debbugs.gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Wed, 19 Sep 2018 00:48:42 -0700

Jim Meyering wrote:
>>    seq 10000 | sed 's/$/ abcdefghijklmnopqrstuvwxyz/; s/$/./' >in
>>    time -p env LC_ALL=C grep -vf in in
>>
>>    (before) real 63.43 user 61.67 system 1.65
>>    (after)  real  1.64 user  1.61 system 0.03
>>
>>    # If we do not add '.' at last in pattern, not dfa but kwset is used.
>>
>> grep also speeds-up about 3x in following case.
>>
>>    time -p env LC_ALL=C grep -vf /usr/share/dict/linux.words /usr/share/dict/linux.words
>>
>>    (before) real  2.48 user  2.09 system 0.38
>>    (after)  real  7.69 user  6.32 system 1.29
> Thank you for the patches.
> However, the before/after numbers you show here suggest that the
> "after" code takes more than triple of the time of "before". >
> Also, when I compared grep compiled at
> 123620af88f55c3e0cc9f0aed7311c72f625bc82 (latest, including your
> changes) and that compiled at the prior commit,
> 9c11510507ebcd31671f10d9b88532f8e6657ad2, I find that the new version
> takes over 30 seconds, while the prior one took about 20 seconds.


Is that last pair of times for the second benchmark he gave? I confess to being 
lazy and not trying that benchmark, as I was on an Ubuntu system that didn't 
have the linux.words file.

Did you try the first benchmark? On my Ubuntu 18.04 x86-64 (Xeon E3-1225 V2) 
platform, I got (before) real 55.51 user 51.53 sys 3.98, (after) real 0.64 user 
0.60 sys 0.04, so the change is a big performance win there.

On the other hand, I just now did the 2nd benchmark with a copy of a Fedora 28 
linux.words file, and got (before) real 8.06 user 6.20 sys 1.85, (after) real 
21.69 user 21.21 sys 0.47, so it's about three times slower. Ouch.

Message #31 received at 32750 <at> debbugs.gnu.org (full text, mbox):

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: Jim Meyering <jim <at> meyering.net>
Cc: 32750 <at> debbugs.gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Thu, 20 Sep 2018 00:24:22 +0900

[Message part 1 (text/plain, inline)]

On Tue, 18 Sep 2018 22:13:38 -0700
Jim Meyering <jim <at> meyering.net> wrote:

> Also, when I compared grep compiled at
> 123620af88f55c3e0cc9f0aed7311c72f625bc82 (latest, including your
> changes) and that compiled at the prior commit,
> 9c11510507ebcd31671f10d9b88532f8e6657ad2, I find that the new version
> takes over 30 seconds, while the prior one took about 20 seconds.
> 
> FTR, I used gcc version 9.0.0 20180912, compiling with -O3.

Thanks for your investigation.

Sorry, I forgot to send the patch.  We need the patch to optimize MERGE
function to speed-up for some cases.

Thanks,
Norihiro

[0001-dfa-optimization-for-state-merge.patch (application/octet-stream, attachment)]

Message #34 received at 32750 <at> debbugs.gnu.org (full text, mbox):

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, Jim Meyering <jim <at> meyering.net>
Cc: 32750 <at> debbugs.gnu.org
Subject: Re: bug#32750: [PATCH 2/2] dfa: optmization of alternation in NFA
Date: Wed, 19 Sep 2018 08:45:44 -0700

[Message part 1 (text/plain, inline)]

Norihiro Tanaka wrote:
> Sorry, I forgot to send the patch.  We need the patch to optimize MERGE
> function to speed-up for some cases.

Thanks, that improved the performance of the 'grep -vf linux.words linux.words' 
benchmark from (before the recent changes) real 8.06 user 6.20 sys 1.85 to 
(after) real 2.57 user 2.11 sys 0.45.

I installed it (with minor tweaks to the ChangeLog) into gnulib master and 
updated the grep master accordingly. I'll CC: this email to bug-gnulib to give 
them a heads-up, attaching the revised patch.

[0001-dfa-optimization-for-state-merge.patch (text/x-patch, attachment)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.