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>
 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 (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