buggrep - Bugs: bug #14472, grep is slow in multibyte locales

 
 

You are not allowed to post comments on this tracker with your current authentication level.

bug #14472: grep is slow in multibyte locales

Submitted by:  Andreas Schwab <schwab>
Submitted on:  Thu 08 Sep 2005 01:44:06 PM UTC  
Votes:  181  
 
Category:  None Severity:  3 - Normal
Item Group:  None Status:  Fixed
Privacy:  Public Assigned to:  None
Open/Closed:  Closed

( Jump to the original submission)

Tue 16 Mar 2010 02:40:26 PM UTC, comment #7:

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

Paolo Bonzini <bonzini>
  Spam posted by annaanna1
Thu 03 Jul 2008 02:38:20 PM UTC, comment #6:

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

Norihirio Tanaka <noritnk>
Thu 26 Jun 2008 10:33:09 PM UTC, comment #5:

Same here. Extremally slow.

grep-2.5.3-2.x86_64

$ export LANG=C
$ time grep FREE LOG-POLISH > x
grep --colour=auto FREE LOG-POLISH > x 0.02s user 0.00s system 26% cpu 0.089 total
$ time grep FREE LOG-POLISH > x
grep --colour=auto FREE LOG-POLISH > x 0.02s user 0.00s system 43% cpu 0.061 total
$ time grep FREE LOG-POLISH > x
grep --colour=auto FREE LOG-POLISH > x 0.02s user 0.01s system 45% cpu 0.066 total
$ time grep FREE LOG-POLISH > x
grep --colour=auto FREE LOG-POLISH > x 0.02s user 0.00s system 41% cpu 0.064 total

Now the turtle mode.

$ export LANG=pl_PL.UTF-8
$ time grep FREE LOG-POLISH > x
grep --colour=auto FREE LOG-POLISH > x 56,99s user 0,00s system 99% cpu 57,002 total
$ time grep FREE LOG-POLISH > x
grep --colour=auto FREE LOG-POLISH > x 57,81s user 0,02s system 99% cpu 57,843 total
$ time grep FREE LOG-POLISH > x
grep --colour=auto FREE LOG-POLISH > x 57,48s user 0,01s system 99% cpu 57,499 total

Arkadiusz Miskiewicz <arekm>
Fri 01 Feb 2008 07:07:09 PM UTC, comment #4:

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

Adam Rosenstein <adamrosenstein>
Wed 10 Oct 2007 10:47:33 PM UTC, comment #3:

$ apt-cache search '.*' >> f2

... repeat above about 50 times.

$ wc -l f2
239700 f2
$ LC_ALL=C time grep 'pack.*ge' f2 > /dev/null
0.03 real 0.02 user 0.00 sys
$ LC_ALL=en_US.utf-8 time grep 'pack.*ge' f2 > /dev/null
9.85 real 9.50 user 0.34 sys

Grep is taking way too long in utf-8, even though the file contains plain ascii text.

Tony Abou-Assaleh <taa>
Project Administrator
Fri 16 Sep 2005 12:13:21 PM UTC, comment #2:

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

Andreas Schwab <schwab>
Fri 16 Sep 2005 09:45:25 AM UTC, comment #1:

Could you please specify how you run grep (command line options)?

MBS strike heavy in case of ignore case matches.

Johannes T. Prinz <purple>
Thu 08 Sep 2005 01:44:06 PM UTC, original submission:

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.

Andreas Schwab <schwab>

 

Attached Files
file #15989:  grep-mbs-speedup.patch added by noritnk (13KiB - application/octet-stream - Checking of multibyte starings is avoided as far as possible.)
file #14130:  grep-i18n-speedup.diff added by schwab (2KiB - text/x-diff - Lazily compute mb_properties)
file #3267:  yy added by schwab (95KiB - text/plain - gprof output)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by bonzini (Posted a comment)
  • -email is unavailable- added by annaanna1 (Posted a comment)
  • -email is unavailable- added by noritnk (Updated the item)
  • -email is unavailable- added by arekm (Posted a comment)
  • -email is unavailable- added by dberkholz
  • -email is unavailable- added by dberkholz (Voted in favor of this item)
  • -email is unavailable- added by pprkut (Voted in favor of this item)
  • -email is unavailable- added by theirix (Voted in favor of this item)
  • -email is unavailable- added by adamrosenstein (Voted in favor of this item)
  • -email is unavailable- added by adamrosenstein (Posted a comment)
  • -email is unavailable- added by schwab (Updated the item)
  • -email is unavailable- added by taa (Posted a comment)
  •  

    Do you think this task is very important?
    If so, you can add your encouragement to it.
    This task has 181 encouragements so far.

    Only logged-in users can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 11 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2010-03-16 bonzini StatusConfirmed => Fixed
        Open/ClosedOpen => Closed
    2008-07-03 noritnk Attached File- => Added grep-mbs-speedup.patch, #15989
    2008-05-07 dberkholz Carbon-Copy- => Added -email is unavailable-
        Carbon-Copy- => Added dberkholz
    2008-03-23 pprkut Carbon-Copy- => Added pprkut
    2008-02-05 theirix Carbon-Copy- => Added theirix
    2008-02-01 adamrosenstein Carbon-Copy- => Added adamrosenstein
    2007-10-11 schwab Attached File- => Added grep-i18n-speedup.diff, #14130
    2007-10-10 taa StatusNone => Confirmed
    2005-09-08 schwab Attached File- => Added yy, #2933

    Back to the top


    Powered by Savane 3.3