¿Por qué egrep [wW] [oO] [rR] [dD] es más rápido que grep -i word?

49

Lo he estado usando con grep -imás frecuencia y descubrí que es más lento que su egrepequivalente, donde coincido con la letra mayúscula o minúscula de cada letra:

$ 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

¿Hace grep -ipruebas adicionales que egrepno?

tildearrow
fuente
12
Pruebe al greprevés para asegurarse de que no está midiendo la diferencia entre el almacenamiento en caché de disco de la mosca.
EightBitTony
3
He grep'd el archivo antes de la prueba, por lo que está en caché. Casi las mismas veces si se hace en orden inverso.
tildearrow
21
Esto puede depender de la configuración regional: algunas configuraciones regionales implican cálculos complejos para tener en cuenta la insensibilidad a mayúsculas y minúsculas. GNU grep es particularmente lento en muchas situaciones que involucran Unicode. ¿Qué configuración regional usaste? ¿Bajo qué variante de Unix? ¿Cuál es el contenido de su archivo de prueba?
Gilles 'SO- deja de ser malvado'
66
@Gilles se ve bien, repitiendo cada prueba aquí 100 veces (cronometrando todo), egrepes más rápido que grephasta que configuré LANG=Cy luego ambos son más o menos lo mismo.
EightBitTony
2
@EightBitTony Mire el usertiempo (que no incluye el tiempo de espera para el disco). Hay un orden de magnitud en la diferencia.
kasperd

Respuestas:

70

grep -i 'a'es equivalente a grep '[Aa]'en un entorno local solo ASCII. En un entorno local Unicode, las equivalencias y conversiones de caracteres pueden ser complejas, por lo que es grepposible que tenga que hacer un trabajo adicional para determinar qué caracteres son equivalentes. La configuración regional relevante es LC_CTYPE, que determina cómo se interpretan los bytes como caracteres.

En mi experiencia, GNU greppuede ser lento cuando se invoca en un entorno local UTF-8. Si sabe que solo está buscando caracteres ASCII, invocarlo en una configuración regional solo ASCII puede ser más rápido. Eso espero

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

produciría tiempos indistinguibles.

Dicho esto, no puedo reproducir su hallazgo con GNU grepen Debian jessie (pero no especificó su archivo de prueba). Si configuro un entorno local ASCII ( LC_ALL=C), grep -ies más rápido. Los efectos dependen de la naturaleza exacta de la cadena, por ejemplo, una cadena con caracteres repetidos reduce el rendimiento ( que es de esperar ).

Gilles 'SO- deja de ser malvado'
fuente
El autor usa Ubuntu 14.04 que se envía con grep 2.10. La velocidad de las coincidencias entre mayúsculas y minúsculas ( -i) con configuraciones regionales multibyte debería haber mejorado en 2.17 .
Lekensteyn
@Lekensteyn Es bueno saberlo, gracias. Ubuntu 14.04 en realidad viene con grep 2.16, pero eso también es anterior a 2.17; Probé con grep 2.20, lo que explica por qué no vi la misma desaceleración.
Gilles 'SO- deja de ser malo'
Correcto, estaba mirando la versión LTS incorrecta, Ubuntu 12.04 viene con grep 2.10, mientras que Ubuntu 14.04 incluye grep 2.16.
Lekensteyn
1
Estoy bastante seguro de que grep -i 'a'es equivalente a grep '[Aa]'en cualquier localidad. El ejemplo correcto es grep -i 'i'cuál es grep '[Ii]'o grep '[İi]'(Mayúscula I con punto arriba, U + 130, configuración regional turca). Sin embargo, no hay una manera eficiente de grepencontrar esta clase de equivalencia dada una localización.
MSalters
15

Por curiosidad, probé esto en un sistema Arch Linux:

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

Y luego algunas estadísticas cortesía de ¿Hay alguna forma de obtener el mínimo, el máximo, la mediana y el promedio de una lista de números en un solo comando? :

$ 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
> 
> 

Estoy en el en_GB.utf8lugar, pero los tiempos son casi indistinguibles.

muru
fuente