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

 
 

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

bug #14472: grep is slow in multibyte locales

Submitted by:  Andreas Schwab <schwab>
Submitted on:  Thu Sep 8 13:44:06 2005  
Votes:  181  
 
Category: NoneSeverity: 3 - Normal
Item Group: NoneStatus: Fixed
Privacy: PublicAssigned to: None
Open/Closed: Closed

(Jump to the original submission Jump to the original submission)

Tue Mar 16 14:40:26 2010, 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>
(Why is this post is considered to be spam? Users may have reported it to be spam or, if it has been recently posted, it may just be waiting for spamchecks to be run.)
Spam content:

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.


http://skylinemp3.com/
__________________
Anna
-Deleted Account- <annaanna1>
Thu Jul 3 14:38:20 2008, 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 Jun 26 22:33:09 2008, 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 Feb 1 19:07:09 2008, 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 Oct 10 22:47:33 2007, 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 Sep 16 12:13:21 2005, 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 Sep 16 09:45:25 2005, 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 Sep 8 13:44:06 2005, 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 (13kB - application/octet-stream - Checking of multibyte starings is avoided as far as possible.)
file #14130:  grep-i18n-speedup.diff added by schwab (2kB - text/x-diff - Lazily compute mb_properties)
file #3267:  yy added by schwab (95kB - text/plain - gprof output)

 

Depends on the following items: None found

Items that depend on this one: None found

 

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

    Do you think this task is very important?
    If so, you can click here to 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
    Tue Mar 16 14:40:26 2010bonziniStatusConfirmed=>Fixed
      Open/ClosedOpen=>Closed
    Thu Jul 3 14:15:57 2008noritnkAttached File-=>Added grep-mbs-speedup.patch, #15989
    Wed May 7 21:46:23 2008dberkholzCarbon-Copy-=>Added -unavailable-
      Carbon-Copy-=>Added dberkholz
    Sun Mar 23 09:36:08 2008pprkutCarbon-Copy-=>Added pprkut
    Tue Feb 5 15:03:44 2008theirixCarbon-Copy-=>Added theirix
    Fri Feb 1 19:07:57 2008adamrosensteinCarbon-Copy-=>Added adamrosenstein
    Thu Oct 11 09:24:25 2007schwabAttached File-=>Added grep-i18n-speedup.diff, #14130
    Wed Oct 10 22:47:33 2007taaStatusNone=>Confirmed
    Thu Sep 8 13:44:07 2005schwabAttached File-=>Added yy, #2933

    Back to the top


    Powered by Savane 3.1-cleanup