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

Submitter:  Andreas Schwab <schwab>
Submitted:  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 #8: 

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

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

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)
  •  

    There are 181 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

     

    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.14-f13d.
    Corresponding source code