Take the 2-minute tour ×
Super User is a question and answer site for computer enthusiasts and power users. It's 100% free, no registration required.

Consider:

$ time lzop -d < tvtropes-index.lzo | egrep -B 5 '[Dd][eE][sS][cC][eE][nN][dD] ?[Ff][rR][oO][mM]'
real    0m0.438s

$ time lzop -d < tvtropes-index.lzo | egrep -B 5 'descend ?from' -i
real    0m11.294s

Both search case insensitively. Why is the -i version so slow? How do I make grep -i fast without entering things like [iI][nN] [tT][hH][iI][sS] [wW][aA][Yy]?

For example,

perl -ne 'print if /descend ?from/i'

works fast, but '-B 5' is not as trivial to implement as in grep (as well as other options).

share|improve this question
1  
Case insensitivity is hard, especially if you're doing it on unicode input. –  phogg Sep 6 '11 at 13:17
    
How to make fast case insensitivity, e.g. like "replace every x with [xX] in the pattern"? –  Vi. Sep 6 '11 at 13:33
add comment

3 Answers

up vote 7 down vote accepted

Case folding is hard

Simply mapping [a-z] to [A-Z] works for most simple ASCII-only text documents. However, it begins to break down as we explore other languages that use additional characters. It also doesn't take into account the fact that case mappings in some languages are not always algorithmic or static.

For example, if you case folded [a-z] -> [A-Z], a string like "Dürst" or "résumé" might end up looking a bit odd: "DüRST" or "RéSUMé".

You might be able speed it up by persuading grep that the world is ASCII once again, either by using an ancient grep or by playing with locales (LC_ALL=C?).

This conversation mentions "massive slow-downs on UTF8 locales" but doesn't help.

share|improve this answer
    
Is there ASCII-only fast case insensitive mode for grep? LANG=C grep -i fails (slow). –  Vi. Sep 6 '11 at 13:40
    
@Vi: lzop -d < thingy | tr '[A-Z]' '[a-z]' | grep ... maybe? –  RedGrittyBrick Sep 6 '11 at 13:54
1  
Sorry, "LANG=C grep -i" works (tested again correctly). –  Vi. Sep 6 '11 at 13:55
add comment

Hypothesis

These counterintuitive result is explained by this. Your regex is not the same as grep -i because grep -i is more general, taking into consideration complicated multi-byte string handling, at least when compiled with the preprocessor symbol MBS_SUPPORT.

Take a look here:

http://cvs.savannah.gnu.org/viewvc/grep/grep/src/search.c?revision=1.42&view=markup

Look for match_icase and MBS_SUPPORT.

share|improve this answer
add comment

If the actual case of the find is not critical, you might use tr to fold [A-Z] to [a-z] before the grep.

share|improve this answer
    
I would only do that to have a simpler regex to write. Although the case-insensitive regex blows up to a larger DFA, it's probably not a big issue. It depends on how many matches there are. If the file has a lot of false positives or full matches that use many of the possible case combinations, then the state graph will cache badly in the CPU. That probably does not arise. There will probably only be a few cases like DESCEND, Descend an descend which traverse the same "well-trodden" paths through the regex DFA. –  Kaz Mar 27 '12 at 23:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.