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: Norihiro Tanaka <noritnk <at> kcn.ne.jp>
Subject: bug#16823: closed (Re: bug#16823: Use DFA regex engine on fgrep
 matcher)
Date: Mon, 24 Mar 2014 01:19:02 +0000

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

Your bug report

#16823: Use DFA regex engine on fgrep matcher

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 16823 <at> debbugs.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: 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 3 (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)]

[Message part 5 (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 6 (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)]

Previous Next

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