¿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 muchísimo más rápido que el código Java que solía escribir. (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 a GNU grep específicamente. Aquí hay una nota del autor, Mike Haertel:

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

GNU grep es rápido porque EJECUTA MUY POCAS INSTRUCCIONES PARA CADA BYTE que mira.

GNU grep usa el bien conocido algoritmo Boyer-Moore, que busca primero la letra final de la cadena objective, y usa una tabla de búsqueda para indicarle qué tan lejos puede omitir la entrada cada vez que encuentre un carácter que no coincida.

GNU grep también desenrolla el bucle interno de Boyer-Moore y configura las entradas de la tabla delta Boyer-Moore de tal manera que no es necesario realizar 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 realmente mira (y omite muchos bytes por completo).

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

Entonces, en lugar de usar una entrada orientada a la línea, GNU grep lee los datos sin procesar en un buffer grande, busca en el buffer usando Boyer-Moore, y solo cuando encuentra una coincidencia va y busca las líneas salientes delimitadoras (Ciertas opciones de línea de comandos como – n desactivar esta optimización.)

Esta respuesta es un subconjunto de la información tomada desde aquí .

Para agregar a la excelente respuesta de Steve.

Puede que no sea ampliamente conocido, pero grep es casi siempre más rápido cuando se usa para un patrón más largo que uno corto, 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 35% más rápida!

¿Cómo? Boyer-Moore construye una tabla de salto de la secuencia patrón, y cada vez que hay una falta de coincidencia, escoge el salto más largo posible (desde el último carácter al primero) antes de comparar un solo carácter en la entrada al carácter en la tabla de salto.

Aquí hay un buen video que explica Boyer Moore

Otro concepto erróneo común (para GNU grep) es que fgrep es más rápido que grep . f en fgrep no significa “rápido”, significa “fijo” (consulte la página de manual), y dado que ambos son el mismo progtwig, y ​​ambos usan Boyer-Moore , no hay diferencia de velocidad entre ellos al buscar cadenas fijas sin regexp caracteres especiales. La única razón por la que uso fgrep es cuando hay un carácter especial de fgrep (como . , [] O * ). No quiero que se interprete como tal. E incluso entonces, la forma más portátil / estándar de grep -F es preferible a fgrep .