grab

agarrar - grep simple, pero muy rápido

Esta es mi propia versión experimental y paralela de grep , por lo que puedo probar varias estrategias para acelerar el acceso a grandes árboles de directorios. En almacenamiento Flash o SSD, puedes burlar fácilmente a los greps comunes hasta en un factor de 8.

Opciones:

 Usage: ./greppin [-rIOLlsSH] [-n <cores>] <regex> <path>

	-2	-- use PCRE2 instead of PCRE
	-O	-- print file offset of match
	-l	-- do not print the matching line (Useful if you want
		   to see _all_ offsets; if you also print the line, only
		   the first match in the line counts)
	-s	-- single match; dont search file further after first match
		   (similar to grep on a binary)
	-H	-- use hyperscan lib for scanning
	-S	-- only for hyperscan: interpret pattern as string literal instead of regex
	-L	-- machine has low mem; half chunk-size (default 2GB)
		   may be used multiple times
	-I	-- enable highlighting of matches (useful)
	-n	-- Use multiple cores in parallel (omit for single core)
	-r	-- recurse on directory

grab usa la biblioteca pcre , por lo que básicamente es equivalente a grep -P -a . La -P es importante, ya que las expresiones regulares compatibles con Perl tienen características diferentes a las expresiones regulares básicas.

Construir

Hay dos ramas. master y greppin . Master es la captura "tradicional" que debería compilarse y ejecutarse en la mayoría de los sistemas POSIX. greppin viene con su propia versión optimizada y paralelizada de nftw() y readdir() , que nuevamente duplica la velocidad además de la aceleración que la rama master ya proporciona. La rama greppin se ejecuta en Linux, BSD y OSX. greppin también viene con soporte para las bibliotecas de hiperexploración de Intel que intentan explotar las instrucciones SIMD de la CPU si es posible (AVX2, AVX512, etc.) al compilar el patrón de expresiones regulares en código JIT.

Lo más probable es que quieras construir la rama greppin :

 $ git checkout greppin
[...]
$ cd src; make
[...]

Asegúrese de tener instalados los paquetes de biblioteca pcre y pcre2 . En sistemas BSD necesitas gmake en lugar de make . Si desea utilizar tecnología de punta con el motor de expresiones regulares múltiples de greppin y el soporte de hiperescaneo, primero debe obtenerlo y compilarlo:

 $ git clone https://github.com/intel/hyperscan
[...]
$ cd hyperscan
$ mkdir build; cd build
$ cmake -DFAT_RUNTIME=1 -DBUILD_STATIC_AND_SHARED=1 ..
[...]
$ make
[...]

Esto creará el llamado tiempo de ejecución completo de las bibliotecas de hiperexploración que contienen soporte para todas las familias de CPU para seleccionar el patrón de compilación correcto en tiempo de ejecución para obtener el mayor rendimiento. Una vez que finaliza la compilación, construyes greppin contra eso:

(dentro del repositorio clonado)

 $ cd src
$ HYPERSCAN_BUILD=/path/to/hyperscan/build make -f Makefile.hs
[...]

Esto producirá un binario greppin que habilita la opción -H para cargar un motor diferente en tiempo de ejecución, intentando explotar todos los bits de rendimiento posibles.

Podría vincularlo con bibliotecas ya instaladas, pero la API agregó recientemente algunas funciones en la versión 5.x y la mayoría de las distribuciones se envían con 4.x.

¿Por qué es más rápido?

grab usa mmap(2) y coincide con todo el blob de archivos sin contar las nuevas líneas (lo que grep está haciendo incluso si no hay ninguna coincidencia [según una revisión mía del código grep en 2012; las cosas pueden ser diferentes hoy]), lo cual es mucho más rápido que read(2) dividir el archivo en pequeños fragmentos y contar las nuevas líneas. Si está disponible, grab también utiliza la función PCRE JIT. Sin embargo, las aceleraciones sólo se pueden medir en árboles de archivos grandes o en discos duros o SSD rápidos. En el último caso, la aceleración puede ser realmente drástica (hasta 3 veces más rápida) si se empareja de forma recursiva y en paralelo. Dado que el almacenamiento es el cuello de botella, no tiene sentido paralelizar la búsqueda en discos duros, ya que la búsqueda lleva más tiempo que simplemente hacer cosas en línea.

Además, grab omite archivos que son demasiado pequeños para contener la expresión regular. Para expresiones regulares más grandes en una búsqueda recursiva, esto puede omitir una cantidad bastante buena de archivos sin siquiera abrirlos.

Se requiere una pcre lib bastante nueva; en algunos sistemas más antiguos, la compilación puede fallar debido a que faltan PCRE_INFO_MINLENGTH y pcre_study() .

Los archivos se asignan y combinan en fragmentos de 1 GB. Para archivos que son más grandes, los últimos 4096 bytes (1 página) de un fragmento se superponen, de modo que se puedan encontrar coincidencias en un límite de 1 Gigas. En este caso, verás que la coincidencia se duplica (pero con el mismo desplazamiento).

Si mide grep versus grab , tenga en cuenta eliminar los cachés de dentry y de página entre cada ejecución: echo 3 > /proc/sys/vm/drop_caches

Tenga en cuenta que grep imprimirá solo 'coincidencias de archivos binarios', si detecta archivos binarios, mientras que grab imprimirá todas las coincidencias, a menos que se proporcione -s . Por lo tanto, para una prueba de velocidad debe buscar una expresión que no exista en los datos para poder forzar la búsqueda en todos los archivos.

grab se creó para buscar rápidamente en grandes árboles de directorios sin indexación. El grep original tiene un conjunto de opciones mucho más completo. La aceleración para una coincidencia de un solo archivo es muy pequeña, si es que se puede medir.

Para los SSD, la opción multinúcleo tiene sentido. Para los discos duros no es así, ya que el cabezal debe colocarse de un lado a otro entre los subprocesos, lo que potencialmente destruye el principio de localidad y acaba con el rendimiento.

La rama greppin presenta su propia versión paralela sin bloqueo de nftw() , por lo que el tiempo de inactividad de N - 1 núcleos cuando el primer núcleo construye el árbol de directorios también se puede utilizar para trabajar.

Lo que queda por tener en cuenta: grab atravesará directorios físicamente , es decir, no seguirá enlaces simbólicos.

lugar

spot es la versión paralela de find . Admite las opciones utilizadas con más frecuencia tal como las conoce. No hay mucho más que contar al respecto, solo pruébalo.

Ejemplos

Esto muestra la aceleración en una máquina de 4 núcleos con una búsqueda en un SSD:

 root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -r foobardoesnotexist /source/linux

real	0m34.811s
user	0m3.710s
sys	0m10.936s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -r foobardoesnotexist /source/linux

real	0m31.629s
user	0m4.984s
sys	0m8.690s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 2 -r foobardoesnotexist /source/linux

real	0m15.203s
user	0m3.689s
sys	0m4.665s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 4 -r foobardoesnotexist /source/linux

real	0m13.135s
user	0m4.023s
sys	0m5.581s

Con rama greppin :

 root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -a -P -r linus /source/linux/|wc -l
16918

real    1m12.470s
user    0m49.548s
sys     0m6.162s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time greppin -n 4 -r linus /source/linux/|wc -l
16918

real    0m8.773s
user    0m4.670s
sys     0m5.837s
root@linux:~#

¡Sí! ~ 9 contra ~ 72! Eso es 8 veces más rápido en una máquina SSD de 4 núcleos que el grep tradicional.

Solo para probar que resultó en el mismo resultado:

 root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# greppin -n 4 -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0  -
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# grep -P -a -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0  -
root@linux:~#

En la comparación de un solo núcleo, la aceleración también depende de qué CPU el kernel realmente programa el grep , por lo que un grab puede ser más rápido o no (en su mayoría lo es). Si la carga es igual entre las pruebas de un solo núcleo, grab verá una aceleración si busca en árboles de archivos grandes. En configuraciones de múltiples núcleos, el agarre puede resultar beneficioso.

comparación de ripgrep

El proyecto se puede encontrar aquí.

La principal aceleración que se encuentra dentro de sus tablas de referencia se debe al hecho de que ripgrep ignora muchos archivos (notablemente archivos de puntos) cuando se invoca sin opciones especiales, además de tratar los archivos binarios como un objetivo de coincidencia única (similar a grep ). Para obtener resultados comparables, tenga en cuenta (4 es el número de núcleos):

• echo 3 > /proc/sys/vm/drop_caches entre cada ejecución
• Agregue -j 4 -a --no-unicode --no-pcre2-unicode -uuu --mmap a ripgrep , ya que de forma predeterminada coincidirá con Unicode, que es 3 veces más lento, e intenta compensar la pérdida de velocidad omitiendo 'ignorar' -archivos basados ​​en. -e es más rápido que -P , así que mejor elige -e , pero eso no es tan poderoso como un PCRE
• redirigir la salida a /dev/null para evitar efectos basados ​​en tty
• agregue -H -n 4 a greppin si desea el mejor rendimiento. -H es compatible con PCRE con muy pocas excepciones (según el documento de hiperescaneo)
• setfattr -n user.pax.flags -v "m" /path/to/binary si ejecuta sistemas grsec y requiere asignaciones rwx JIT

Entonces sigue adelante y comprueba los horarios. Incluso cuando no se utiliza hiperexploración, greppin es significativamente más rápido que rg cuando se utilizan expresiones PCRE2 (PCRE2 frente a PCRE2) y aún más rápido cuando se comparan las expresiones más rápidas (-e frente a hiperexploración).