grep - 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: |
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.
$ # Ubuntu's grep-2.5.3, UTF-8: fast
$ # Stock grep-2.6.2, 8-bit: fast
$ # Stock grep-2.6.2, UTF-8: very slow
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
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- |
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