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

 
 

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

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

Submitter:  Egmont Koblinger <egmont>
Submitted:  Wed 31 Mar 2010 09:13:46 AM UTC
Votes: 12
 
Category:  None Severity:  3 - Normal
Item Group:  None Status:  None
Privacy:  Public Assigned 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>

 

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

No files currently attached

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by gr4v_racz (Voted in favor of this item)
  • -email is unavailable- added by bill_mcgonigle
  • -email is unavailable- added by burt
  • -email is unavailable- added by noritnk (Posted a comment)
  • -email is unavailable- added by bonzini (Posted a comment)
  • -email is unavailable- added by egmont (Submitted the item)
  •  

    There are 12 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 3 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2016-09-28 gr4v_racz Carbon-Copy- Added gr4v_racz
    2012-09-07 bill_mcgonigle Carbon-Copy- Added bill_mcgonigle
    2012-07-03 burt Carbon-Copy- Added -email is unavailable-

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code