Case insensitivity incurs a factor of nearly 100x slower? That should be a constant time increase in amount of processing.
Well, no. For starters, there are 1024 different strings that match acct_margin with the -i
switch.
Matching acct_margin is case sensitively easy; if the current character isn't an a, skip. With case-folding, you have to check if the current character is an a or an A. That's not only two tests, you also have a lot more matches you can't skip directly.1 It gets more difficult for non-ASCII characters.
Nevertheless, grep -i
shouldn't be so slow. This seems to be bad implementation of case-folding when multi-byte characters are anticipated (even though none are present in the files).
Possible workarounds
Do not use the -i
switch and construct the case-insensitive regular expression by hand.
If the files contain only ASCII characters, temporarily set the encoding identifier of the environment variable LANG to ISO-8859-1 (a.k.a. Western European, Latin-1 or Code Page 819).
Select one of the non-default regular expression types (--fixed-strings
, --extended-regexp
or --perl-regexp
).
If the files contain only ASCII characters and case-folding the output is admissible, do not use the -i
switch and pipe case-folded characters to grep.
Test setup
I've created a 500 MB file of Base64-encoded pseudo-random bytes on my computer2, killed all CPU- or memory-intensive processes and compared the execution times of the above workarounds to a plain grep
or grep -i
.
I've fed the input file to grep and tr using a redirector and discarded the output to eliminate potential sources of bias.
I've run every command several times; the execution times were stable (maximum variation of ±0.01s).
Bechmarks
$ # Make time output only elapsed time:
$ TIME=" %es"
$ # C create 500MB file of 76 printable ASCII characters per line:
$ < /dev/urandom base64 | head -c 500MB > file
$ # Verify that current character encoding is UTF8:
$ echo " $LANG"
en_US.UTF-8
# Benchmark of case-sensitive `grep' for comparison:
$ < file time grep test > /dev/null
0.45s
$ # Benchmark of case-sensitive `grep --perl-regexp' for comparison:
$ < file time grep -P test > /dev/null
0.82s
$ # Benchmark of case-insensitive `grep' for comparison:
$ < file time grep -i test > /dev/null
21.08s
$ # Workaround 1:
$ < file time grep [Tt][Ee][Ss][Tt] > /dev/null
1.53s
$ # Workaround 2:
$ (LANG=en_US.ISO-8859-1; < file time grep -i test > /dev/null)
1.53s
$ # Workaround 3:
$ < file time grep -Pi test > /dev/null
1.33s
$ # Workarounds 2 and 3 combined:
$ (LANG=en_US.ISO-8859-1; < file time grep -Pi test > /dev/null)
1.25s
$ # Workarounds 4:
$ < file time tr [A-Z] [a-z] | grep test > /dev/null
0.46s
There was no measurable difference between the default and the other non-default regular expression types.
There was no measurable difference between the last version of grep from the standard Ubuntu repositories (2.10) and the latest stable version of GNU grep (2.14).
Conclusions
Workaround 1 and 2 result in the same speed-up.
This suggests that workaround 1 is similar to how grep's case-folding works when no multi-byte characters are anticipated.
While --perl-regexp
is a lot slower for case-sensitive matching, it's magnitudes faster for case-insentive matching.
--perl-regexp
becomes even faster if no multi-byte characters are anticipated.
At the expense of case-folding the output, workaround 4 can be as fast as case-sensitive matching.
1 I'm not suggesting that this is how grep works internally. THis is emant to illustrate why case-insensitive matching is more complicated.
2 Intel Core i5-3570K, 16 GiB RAM, Ubuntu 12.10