[debbugs-tracker] bug#16823: closed (Use DFA regex engine on fgrep matcher)

[GNU bug Tracking System]

Your message dated Sun, 23 Mar 2014 18:18:34 -0700
with message-id <address@hidden>
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
address@hidden)


-- 
16823: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=16823
GNU Bug Tracking System
Contact address@hidden with problems

--- Begin Message --- Subject: Use DFA regex engine on fgrep matcher Date: Thu, 20 Feb 2014 22:26:35 +0900

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
Description: Binary data

--- End Message ---

--- Begin Message --- Subject: Re: bug#16823: Use DFA regex engine on fgrep matcher Date: Sun, 23 Mar 2014 18:18:34 -0700 User-agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Thunderbird/24.4.0 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
Description: Text document

--- End Message ---