Why is egrep [wW][oO][rR][dD] faster than grep -i word?

Question

I've been using grep -i more often and I found out that it is slower than its egrep equivalent, where I match against the upper or lower case of each letter:

$ time grep -iq "thats" testfile

real    0m0.041s
user    0m0.038s
sys     0m0.003s
$ time egrep -q "[tT][hH][aA][tT][sS]" testfile

real    0m0.010s
user    0m0.003s
sys     0m0.006s

Does grep -i do additional tests that egrep doesn't?

Answer 1

grep -i 'a' is equivalent to grep '[Aa]' in an ASCII-only locale. In a Unicode locale, character equivalences and conversions can be complex, so grep may have to do extra work to determine which characters are equivalent. The relevant locale setting is LC_CTYPE, which determines how bytes are interpreted as characters.

In my experience, GNU grep can be slow when invoked in a UTF-8 locale. If you know that you're searching for ASCII characters only, invoking it in an ASCII-only locale may be faster. I expect that

time LC_ALL=C grep -iq "thats" testfile
time LC_ALL=C egrep -q "[tT][hH][aA][tT][sS]" testfile

would produce indistinguishable timings.

That being said, I can't reproduce your finding with GNU grep on Debian jessie (but you didn't specify your test file). If I set an ASCII locale (LC_ALL=C), grep -i is faster. The effects depend on the exact nature of the string, for example a string with repeated characters reduces the performance (which is to be expected).

Answer 2

Out of curiosity, I tested this on an Arch Linux system:

$ uname -r
4.4.5-1-ARCH
$ df -h .
Filesystem      Size  Used Avail Use% Mounted on
tmpfs           3.9G  720K  3.9G   1% /tmp
$ dd if=/dev/urandom bs=1M count=1K | base64 > foo
$ df -h .                                         
Filesystem      Size  Used Avail Use% Mounted on
tmpfs           3.9G  1.4G  2.6G  35% /tmp
$ for i in {1..100}; do /usr/bin/time -f '%e' -ao grep.log grep -iq foobar foo; done
$ for i in {1..100}; do /usr/bin/time -f '%e' -ao egrep.log egrep -q '[fF][oO][oO][bB][aA][rR]' foo; done

$ grep --version
grep (GNU grep) 2.23
Copyright (C) 2016 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>.
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.

Written by Mike Haertel and others, see <http://git.sv.gnu.org/cgit/grep.git/tree/AUTHORS>.

And then some stats courtesy of Is there a way to get the min, max, median, and average of a list of numbers in a single command?:

$ R -q -e "x <- read.csv('grep.log', header = F); summary(x); sd(x[ , 1])"
> x <- read.csv('grep.log', header = F); summary(x); sd(x[ , 1])
       V1       
 Min.   :1.330  
 1st Qu.:1.347  
 Median :1.360  
 Mean   :1.362  
 3rd Qu.:1.370  
 Max.   :1.440  
[1] 0.02322725
> 
> 
$ R -q -e "x <- read.csv('egrep.log', header = F); summary(x); sd(x[ , 1])"
> x <- read.csv('egrep.log', header = F); summary(x); sd(x[ , 1])
       V1       
 Min.   :1.330  
 1st Qu.:1.340  
 Median :1.360  
 Mean   :1.365  
 3rd Qu.:1.380  
 Max.   :1.430  
[1] 0.02320288
> 
> 

I'm on the en_GB.utf8 locale, but the times are nearly indistinguishable.