¿Cómo funciona grep tan rápido?

Question

Estoy realmente sorprendido por la funcionalidad de GREP en shell, antes solía utilizar el método de subcadena en Java pero ahora uso GREP para ello y se ejecuta en cuestión de segundos, es muchísimo más rápido que el código de Java que solía escribir. (de acuerdo con mi experiencia, podría estar equivocado)

Dicho esto, no he podido averiguar cómo está sucediendo. tampoco hay mucho disponible en la web.

¿Alguien me puede ayudar con esto?

Answer 1

Suponiendo que su pregunta se refiera específicamente a GNU grep. Aquí hay una nota del autor, Mike Haertel:

GNU grep es rápido porque EVITA MIRAR CADA ENTRADA BYTE.

grep de GNU es rápido, ya que ejecuta instrucciones MUY POCOS PARA CADA BYTE que hace vistazo a.

grep de GNU utiliza el conocido algoritmo de Boyer-Moore, que se ve primero de la letra final de la cadena de destino, y utiliza una tabla de búsqueda para diga que lo avanzados que puede saltar en la entrada cada vez que encuentra un carácter no coincidente.

grep de GNU también se desenrolla el bucle interno de Boyer-Moore, y establece los Boyer-Moore entradas de la tabla delta de tal manera que no es necesario que hacer la prueba de salida de bucle en cada paso desenrollado. El resultado de esto es que, en el límite, GNU grep promedia menos de 3 instrucciones x86 ejecutadas para cada byte de entrada que en realidad mira (y omite muchos bytes por completo).

GNU grep usa llamadas al sistema de entrada Raw Unix y evita copiar datos después de leerlo. Además, GNU grep evita la interrupción de la entrada a las líneas . ¡Buscar nuevas líneas ralentizaría grep por un factor de varias veces, porque para encontrar las nuevas líneas tendría que mirar cada byte!

Así que en lugar de utilizar la entrada de línea por línea, GNU grep lee datos en bruto en un buffer de gran tamaño, busca en la memoria intermedia utilizando Boyer-Moore, y sólo cuando encuentra una coincidencia lo hace ir a buscar a las nuevas líneas que delimitan (Ciertas opciones de línea de comandos como -n desactivar esta optimización.)

esta respuesta es un subconjunto de la información tomada de here.

Answer 2

Para agregar a la excelente respuesta de Steve.

No puede ser ampliamente conocida, pero grep es casi siempre más rápido cuando grepping para un largo patrón de cuerdas que uno corto, porque en un patrón más largo, Boyer-Moore puede omitir hacia delante en pasos más largos para lograr incluso mejor sublineales velocidades:

Ejemplo:

# after running these twice to ensure apples-to-apples comparison 
# (everything is in the buffer cache) 

$ time grep -c 'tg=f_c' 20140910.log 
28 
0.168u 0.068s 0:00.26 

$ time grep -c ' /cc/merchant.json tg=f_c' 20140910.log 
28 
0.100u 0.056s 0:00.17 

¡La forma más larga es 35% más rápida!

¿Cómo es que? Boyer-Moore crea una tabla de salto desde la cadena de patrones, y siempre que hay una falta de coincidencia, elige el salto más largo posible (desde el último carácter al primero) antes de comparar un único carácter en la entrada al elemento en el grupo mesa.

Aquí es a good video explaining Boyer Moore

Otro error común (por grep de GNU) es que es más rápido que fgrepgrep. f en fgrep no significa 'rápido', significa 'fijo' (vea la página man), y dado que ambos son el mismo programa, y ​​ambos usan Boyer-Moore, no hay diferencia en la velocidad entre ellos cuando buscando cadenas fijas sin regexp caracteres especiales. La única razón por la que uso fgrep es cuando hay una charla especial de expresiones regulares (como ., [] o *) No deseo que se interprete como tal. E incluso entonces, se prefiere la forma más portátil/estándar de grep -F sobre fgrep.