buggrep - Bugs: bug #29391, -i and utf8 slowness, speedup idea


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

bug #29391: -i and utf8 slowness, speedup idea

Submitted by:  Egmont Koblinger <egmont>
Submitted on:  Wed 31 Mar 2010 09:13:46 AM UTC  
Votes:  10  
Category: NoneSeverity: 3 - Normal
Item Group: NoneStatus: None
Privacy: PublicAssigned to: None
Open/Closed: Open

Wed 31 Mar 2010 04:21:52 PM UTC, comment #2:

Matching for -i isn't easy. Though I have proposed `kwsmb.patch'
as one of the solutions, it mayn't be so complete.


Norihirio Tanaka <noritnk>
Wed 31 Mar 2010 10:34:48 AM UTC, comment #1:

True, there's still work to do on -i, I am not even sure Turkish locales work as of now. Thanks for the ideas.

Paolo Bonzini <bonzini>
Wed 31 Mar 2010 09:13:46 AM UTC, original submission:

[ followup of https://bugzilla.redhat.com/show_bug.cgi?id=194471 ]

The combination of --ignore-case and UTF-8 is very slow, even when no special treatment is required for UTF-8. There's also a huge regression in speed compared to Ubuntu Hardy's grep-2.5.3 with I-don't-know-what patches. Some timing data:

$ # Create a 100MB file.
$ dd if=/dev/urandom of=data bs=1M count=100

$ # Ubuntu's grep-2.5.3, UTF-8: fast
$ time LC_ALL=en_US.UTF-8 /bin/fgrep -i foobar data
real 0m0.245s
user 0m0.128s
sys 0m0.112s

$ # Stock grep-2.6.2, 8-bit: fast
$ time LC_ALL=en_US fgrep -i foobar data
real 0m0.156s
user 0m0.084s
sys 0m0.072s

$ # Stock grep-2.6.2, UTF-8: very slow
$ time LC_ALL=en_US.UTF-8 fgrep -i foobar data
real 0m10.264s
user 0m10.049s
sys 0m0.080s

This is approximately a 40-60x slowdown.

I understand that the combination of UTF-8 and ignore-case is a tricky situation, and if I'm having tr_TR.UTF-8 locale then sure I want to pay this price for the correct handling of dotless i's.

Most of the time, however, I'm working with en_US.UTF-8 and grepping variable names in source code and such, usually without any accents.

Grep could do the following:

It could look at the pattern, and check if the following conditions are all true:

- no placeholder that could match a variable-length character (e.g. no "." in the pattern) or other weird stuff

- only ASCII characters

- only characters whose old-fashioned ASCII upper/lowercase counterparts are the same as the locale-aware upper/lowercase counterparts, that is, no "i" or "I" in the pattern if the locale is Turkish.

If all these are true, it could use whatever algorithm it's using for 8-bit locales, because it will find the same matches. This would provide a 40-60x speedup for a very common use case: case insensitively finding an English word.

Egmont Koblinger <egmont>


No files currently attached


Depends on the following items: None found

Items that depend on this one: None found


Carbon-Copy List
  • -unavailable- added by bill_mcgonigle
  • -unavailable- added by burt
  • -unavailable- added by noritnk (Posted a comment)
  • -unavailable- added by bonzini (Posted a comment)
  • -unavailable- added by egmont (Submitted the item)

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 10 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 2 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Fri 07 Sep 2012 07:35:55 PM UTCbill_mcgonigleCarbon-Copy-=>Added bill_mcgonigle
    Tue 03 Jul 2012 06:46:54 PM UTCburtCarbon-Copy-=>Added -unavailable-

    Back to the top

    Powered by Savane 3.1-cleanup