¿Cómo funciona grep tan rápido?

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

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

Puede alguien ayudarme con esto?

Asumiendo que su pregunta se refiere GNU grepespecíficamente. Aquí hay una nota del autor, Mike Haertel:

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

GNU grep es rápido, ya que ejecuta instrucciones muy pocos para cada byte que lo hace ver.

GNU grep usa el conocido algoritmo de Boyer-Moore, que busca primero la letra final de la cadena de destino, y usa una tabla de búsqueda para decirle qué tan adelante puede saltar en la entrada cada vez que encuentra un carácter que no coincide.

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

GNU grep utiliza llamadas al sistema de entrada de Unix sin procesar y evita copiar datos después de leerlos. Además, GNU grep EVITA DIVULGAR LA ENTRADA EN LÍNEAS. Buscar nuevas líneas ralentizaría grep en un factor de varias veces, ¡porque para encontrar las nuevas líneas tendría que mirar cada byte!

Entonces, en lugar de usar entrada orientada a líneas, GNU grep lee datos sin procesar en un búfer grande, busca en el búfer usando Boyer-Moore, y solo cuando encuentra una coincidencia, busca los saltos de línea delimitadores (ciertas opciones de línea de comando como - n deshabilite esta optimización.)

Esta respuesta es un subconjunto de la información extraída de aquí .

Para agregar a la excelente respuesta de Steve.

Puede que no sea muy conocido, pero grep casi siempre es más rápido cuando se busca una cadena de patrón más larga que una corta, porque en un patrón más largo, Boyer-Moore puede saltar hacia adelante en pasos más largos para lograr velocidades sublineales aún mejores :

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 un 35% más rápida!

¿Cómo? Boyer-Moore construye una tabla de salto hacia adelante a partir de la cadena de patrones, y siempre que hay una falta de coincidencia, elige el salto más largo posible (del último carácter al primero) antes de comparar un solo carácter en la entrada con el carácter en la tabla de salto.

Aquí hay un video que explica a Boyer Moore (Crédito a kommradHomer)

Otro error común (para GNU grep) es que fgrepes más rápido que grep. fin fgrepno significa 'rápido', significa 'fijo' (ver la página de manual), y dado que ambos son el mismo programa, y ​​ambos usan Boyer-Moore , no hay diferencia de velocidad entre ellos cuando se busca fijo- cadenas sin caracteres especiales regexp. La única que usar la razón fgrepes cuando hay un char especial expresión regular (como ., [], o *) No quiero que sea interpretado como tal. E incluso entonces grep -Fse prefiere la forma más portátil / estándar de fgrep.