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 08 Sep 2005 01:44:06 PM UTC  
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 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>
(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 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 (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 16 Mar 2010 02:40:26 PM UTCbonziniStatusConfirmed=>Fixed
      Open/ClosedOpen=>Closed
    Thu 03 Jul 2008 02:15:57 PM UTCnoritnkAttached File-=>Added grep-mbs-speedup.patch, #15989
    Wed 07 May 2008 09:46:23 PM UTCdberkholzCarbon-Copy-=>Added -unavailable-
      Carbon-Copy-=>Added dberkholz
    Sun 23 Mar 2008 09:36:08 AM UTCpprkutCarbon-Copy-=>Added pprkut
    Tue 05 Feb 2008 03:03:44 PM UTCtheirixCarbon-Copy-=>Added theirix
    Fri 01 Feb 2008 07:07:57 PM UTCadamrosensteinCarbon-Copy-=>Added adamrosenstein
    Thu 11 Oct 2007 09:24:25 AM UTCschwabAttached File-=>Added grep-i18n-speedup.diff, #14130
    Wed 10 Oct 2007 10:47:33 PM UTCtaaStatusNone=>Confirmed
    Thu 08 Sep 2005 01:44:07 PM UTCschwabAttached File-=>Added yy, #2933

    Back to the top


    Powered by Savane 3.1-cleanup