GNU bug report logs - #16823
Use DFA regex engine on fgrep matcher

Previous Next

Full log

View this message in rfc822 format

From: help-debbugs <at> gnu.org (GNU bug Tracking System)
To: Paul Eggert <eggert <at> cs.ucla.edu>
Cc: tracker <at> debbugs.gnu.org
Subject: bug#16823: closed (Use DFA regex engine on fgrep matcher)
Date: Mon, 24 Mar 2014 01:19:02 +0000

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

Your message dated Sun, 23 Mar 2014 18:18:34 -0700
with message-id <532F87EA.8040601 <at> cs.ucla.edu>
and subject line Re: bug#16823: Use DFA regex engine on fgrep matcher
has caused the debbugs.gnu.org bug report #16823,
regarding Use DFA regex engine on fgrep matcher
to be marked as done.

(If you believe you have received this mail in error, please contact
help-debbugs <at> gnu.org.)


-- 
16823: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16823
GNU Bug Tracking System
Contact help-debbugs <at> gnu.org with problems

[Message part 2 (message/rfc822, inline)]

From: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
To: submit <at> debbugs.gnu.org
Subject: Use DFA regex engine on fgrep matcher
Date: Thu, 20 Feb 2014 22:26:35 +0900

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

Package: grep
Tags: patch

In recent years, grep matcher is very fast by improving the dfa engine.
On the other hands, fgrep matcher only uses kwset engine, which isn't
generally very good at for case-insensitive matching.

The patch enables to switch case-insensitive matching with fgrep matcher
into one with grep matcher, which can use DFA engine, make --ignore-case
(-i) with fgrep master faster (about 30-40x) in UTF locale.


- Before the patch

$ yes $(printf '%078dm' 0)| head -1000000 | tr 0 a > in
$ for i in 1 2 3 4 5; do env LC_ALL=en_US.UTF-8 time src/fgrep -i 'n' in; done
Command exited with non-zero status 1
6.06user 2.23system 0:08.59elapsed 96%CPU (0avgtext+0avgdata 2624maxresident)k
0inputs+0outputs (0major+188minor)pagefaults 0swaps
Command exited with non-zero status 1
6.23user 2.15system 0:08.64elapsed 97%CPU (0avgtext+0avgdata 2608maxresident)k
0inputs+0outputs (0major+187minor)pagefaults 0swaps
Command exited with non-zero status 1
6.83user 1.44system 0:08.47elapsed 97%CPU (0avgtext+0avgdata 2608maxresident)k
0inputs+0outputs (0major+187minor)pagefaults 0swaps
Command exited with non-zero status 1
7.35user 1.25system 0:08.77elapsed 98%CPU (0avgtext+0avgdata 2624maxresident)k
0inputs+0outputs (0major+188minor)pagefaults 0swaps
Command exited with non-zero status 1
7.60user 0.63system 0:08.48elapsed 97%CPU (0avgtext+0avgdata 2608maxresident)k
0inputs+0outputs (0major+187minor)pagefaults 0swaps


- After the patch

$ yes $(printf '%078dm' 0)| head -1000000 | tr 0 a > in
$ for i in 1 2 3 4 5; do env LC_ALL=en_US.UTF-8 time src/fgrep -i 'n' in; done
Command exited with non-zero status 1
0.19user 0.10system 0:00.30elapsed 97%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps
Command exited with non-zero status 1
0.16user 0.06system 0:00.22elapsed 99%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps
Command exited with non-zero status 1
0.18user 0.04system 0:00.23elapsed 95%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps
Command exited with non-zero status 1
0.15user 0.07system 0:00.23elapsed 96%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps
Command exited with non-zero status 1
0.17user 0.04system 0:00.24elapsed 93%CPU (0avgtext+0avgdata 2976maxresident)k
0inputs+0outputs (0major+210minor)pagefaults 0swaps

Norihiro

[dfa_fgrep.txt (application/octet-stream, attachment)]

[Message part 5 (message/rfc822, inline)]

From: Paul Eggert <eggert <at> cs.ucla.edu>
To: Norihiro Tanaka <noritnk <at> kcn.ne.jp>, 16823-done <at> debbugs.gnu.org
Subject: Re: bug#16823: Use DFA regex engine on fgrep matcher
Date: Sun, 23 Mar 2014 18:18:34 -0700

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

Thanks, I pushed your patch (with a minor change to make it integrate 
with the latest grep) and then pushed some fixes and one major 
simplification: don't have any special case for "grep -iF PAT" when PAT 
contains no alphabetics.  This is rare enough that I expect it's not 
worth complicating grep to worry about it.

I'm attaching the combined patch, that is the merge of your patch plus 
my changes.

[grep-F.patch (text/plain, attachment)]

Previous Next

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