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.

https://savannah.gnu.org/patch/?6899

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