Strange execution time for recursive grep

Question

I'm on a Linux Ubuntu machine, grepping a large number of files. Can anyone explain these timings?

>time grep -nIr acct_margin *
[... 3 results ...]
real    0m0.555s
user    0m0.400s
sys     0m0.150s

Case insensitive:

>time grep -niIr acct_margin *
[... 3 results ...]

real    0m45.739s
user    0m45.300s
sys     0m0.240s

With an "or" operator in the regex:

>time grep -nIr "acct_margin\|MARGIN_TABLE" *
[... 5 results ...]

real    0m15.892s
user    0m15.540s
sys     0m0.260s

Case insensitive:

>time grep -niIr "acct_margin\|MARGIN_TABLE" *
[... 5 results ...]

real    0m52.433s
user    0m52.050s
sys     0m0.200s

I've run the commands enough that the files should be cached (htop confirms open ram space).

Case insensitivity incurs a factor of nearly 100x slower? That should be a constant time increase in amount of processing. Pipe operator a factor of 30x slower? I guess I can't argue with the results, but I'm just curious how one writes grep such that it performs this way, and if there's any way around it. High performance grep, anyone?

Answer 1

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.¹ 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

1. Do not use the -i switch and construct the case-insensitive regular expression by hand.

2. 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).

3. Select one of the non-default regular expression types (--fixed-strings, --extended-regexp or --perl-regexp).

4. 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 computer², 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.

---

_{¹ I'm not suggesting that this is how grep works internally. THis is emant to illustrate why case-insensitive matching is more complicated.}

_{² Intel Core i5-3570K, 16 GiB RAM, Ubuntu 12.10}