There are more queued patches which will improve speed further; however, the roughly-quadratic cases should be fixed.



Thank you for the bug report. This bug has been fixed in the
development sources, which can be downloaded using git from
git://git.sv.gnu.org/grep.git

I have confirmed with version 2.5.3 on Linux.

testcase
^^^^^^^^
text.txt has 10000000 line of "a". (i.e. 20000000 byte)

contents and results
^^^^^^^^^^^^^^^^^^^^
# LANG=en_US.UTF8 time grep b test.txt

2.07user 0.02system 0:02.11elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (174major+34minor)pagefaults 0swaps

0.03user 0.04system 0:00.09elapsed 72%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (171major+26minor)pagefaults 0swaps


# LANG=en_US.UTF8 time ../../grep/bin/grep -v a test.txt

before patching:
more slowly

apply grep-mbs-speedup.patch :
1.04user 0.05system 0:01.15elapsed 94%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (173major+26minor)pagefaults 0swaps


# LANG=en_US.UTF8 time grep -iv a test.txt

before patching:
more slowly

apply grep-mbs-speedup.patch :
3.97user 0.02system 0:04.03elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (177major+34minor)pagefaults 0swaps


# LANG=en_US.UTF8 time ../../grep.orig/bin/grep -i b test.txt

before patching:
2.81user 0.02system 0:02.87elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (180major+42minor)pagefaults 0swaps

apply grep-mbs-speedup.patch :
3.33user 0.08system 0:03.45elapsed 98%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (177major+34minor)pagefaults 0swaps

I can confirm that on versions 2.5.2 (shipped with openSuSE 10.3) and 2.5.3:

LC_ALL=en_US.utf-8 is four orders of magnitude slower than LC_ALL=C when grepping pure ASCII input with a frequently matched simple [no kleene star] pattern.  This effectively hobbles all kinds of scripts...

# wc -l /var/log/messages
90833 /var/log/messages

# LC_ALL=C time grep proxy /var/log/messages > /dev/null
0.03user 0.00system 0:00.04elapsed 107%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+185minor)pagefaults 0swaps

# LC_ALL=en_US.utf-8 time grep proxy /var/log/messages > /dev/null
84.94user 0.05system 1:29.63elapsed 94%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+239minor)pagefaults 0swaps

It doesn't matter how grep is called, but the effect is more visible the more matches are found on the data.

When running in a multibyte locale dfaexec calls mbrtowc much too often.  Note how the calls sum up to more then two thirds of the total run time.  The input was a ~4000 line file.