ugrep indexer
v1.0.0
La utilidad ugrep-indexer indexa archivos de forma recursiva para acelerar el grepping recursivo.
Además, el contenido de los archivos comprimidos y comprimidos se indexa cuando se especifica con una opción de línea de comandos. Esto elimina la búsqueda cuando ninguno de sus contenidos coincide con los patrones especificados.
ugrep es un buscador rápido de archivos compatible con grep que admite búsquedas basadas en índices. La búsqueda basada en índices puede ser significativamente más rápida en sistemas de archivos lentos y cuando el almacenamiento en caché del sistema de archivos es ineficaz: si el sistema de archivos en una unidad buscada no está almacenado en caché en la RAM, es decir, está "frío", entonces la indexación acelerará la búsqueda. Solo busca aquellos archivos que puedan coincidir con un patrón de expresiones regulares específico utilizando un índice del archivo. Este índice permite comprobar rápidamente si existe una posible coincidencia, así evitamos buscar en todos los archivos.
La búsqueda indexada con ugrep es segura y nunca omite archivos actualizados que ahora pueden coincidir. Si se agregan o modifican archivos y directorios después de la indexación, la búsqueda siempre buscará estas adiciones y cambios realizados en el sistema de archivos comparando las marcas de tiempo de archivos y directorios con la marca de tiempo de indexación.
Cuando se agregan o modifican muchos archivos después de la indexación, es posible que deseemos volver a indexar para actualizar los índices. La reindexación es incremental, por lo que no llevará tanto tiempo como el proceso de indexación inicial.
Un ejemplo típico pero pequeño de una búsqueda basada en índices, por ejemplo en el repositorio ugrep v3.12.6 ubicado en una unidad separada:
$ cd drive/ugrep
$ ugrep-indexer -I
12247077 bytes scanned and indexed with 19% noise on average
1317 files indexed in 28 directories
28 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
5605227 bytes indexing storage increase at 4256 bytes/file
La búsqueda normal en un sistema de archivos frío sin indexación tarda 1,02 segundos después de desmontar la drive y volver a montarla para borrar la caché de FS y registrar el efecto de la indexación:
$ ugrep -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 1.02 seconds with 8 threads: 1 matching (0.07593%)
Ripgrep 13.0.0 tarda más con 1,18 segundos para la misma búsqueda en frío (ripgrep omite archivos binarios de forma predeterminada, por lo que la opción -I no está especificada):
$ time rg -l 'std::chrono'
src/ugrep.cpp
1.18 real 0.01 user 0.06 sys
Por el contrario, con la indexación, la búsqueda en un sistema de archivos frío solo toma 0,0487 segundos con ugrep, que es 21 veces más rápido, después de desmontar drive y volver a montarla para borrar la caché de FS y registrar el efecto de la indexación:
$ ugrep --index -I -l 'std::chrono' --stats
src/ugrep.cpp
Searched 1317 files in 28 directories in 0.0487 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1316 of 1317 files with non-matching indexes
Siempre hay cierta variación en el tiempo transcurrido, siendo 0,0487 segundos el mejor tiempo de cuatro ejecuciones de búsqueda que produjeron un rango de tiempo de búsqueda de 0,0487 (aceleración de 21 veces) a 0,0983 segundos (aceleración de 10 veces).
El aumento de velocidad puede ser significativamente mayor en general en comparación con esta pequeña demostración, dependiendo de varios factores, el tamaño de los archivos indexados, la velocidad de lectura del sistema de archivos y suponiendo que la mayoría de los archivos estén fríos.
El algoritmo de indexación que diseñé es probablemente monótono : una mayor precisión garantiza un mayor rendimiento de la búsqueda al reducir la tasa de falsos positivos, pero también aumenta la sobrecarga de almacenamiento del índice. Del mismo modo, una menor precisión disminuye el rendimiento de la búsqueda, pero también reduce la sobrecarga de almacenamiento del índice. Por lo tanto, llamé a mi indexador indexador monótono .
Si el espacio de almacenamiento de archivos es escaso, entonces podemos reducir la sobrecarga de almacenamiento de índice especificando una precisión de indexación más baja.
Indexar el ejemplo anterior con el nivel 0 (opción -0 ) reduce la sobrecarga de almacenamiento de indexación 8,6 veces, de 4256 bytes por archivo a unos miserables 490 bytes por archivo:
12247077 bytes scanned and indexed with 42% noise on average
1317 files indexed in 28 directories
0 new directories indexed
1317 new files indexed
0 modified files indexed
0 deleted files removed from indexes
128 binary files ignored with --ignore-binary
0 symbolic links skipped
0 devices skipped
646123 bytes indexing storage increase at 490 bytes/file
La búsqueda indexada sigue siendo 12 veces más rápida que la no indexada en este ejemplo, con 16 archivos realmente buscados (15 falsos positivos):
Searched 1317 files in 28 directories in 0.0722 seconds with 8 threads: 1 matching (0.07593%)
Skipped 1301 of 1317 files with non-matching indexes
Los patrones de expresiones regulares que son más complejos que este ejemplo pueden tener naturalmente una tasa de falsos positivos más alta, que es la tasa de archivos que se consideran posiblemente coincidentes cuando no lo son. Una tasa de falsos positivos más alta puede reducir la velocidad de búsqueda cuando la tasa es lo suficientemente grande como para tener impacto.
La siguiente tabla muestra cómo la precisión de la indexación afecta el almacenamiento de indexación y el ruido promedio por archivo indexado. Las columnas de la derecha muestran la velocidad de búsqueda y la tasa de falsos positivos para ugrep --index -I -l 'std::chrono' :
| según | almacenamiento de índice (KB) | ruido promedio | falsos positivos | tiempo de búsqueda (s) |
|---|---|---|---|---|
-0 | 631 | 42% | 15 | 0.0722 |
-1 | 1276 | 39% | 1 | 0.0506 |
-2 | 1576 | 36% | 0 | 0.0487 |
-3 | 2692 | 31% | 0 | unch |
-4 | 2966 | 28% | 0 | unch |
-5 | 4953 | 23% | 0 | unch |
-6 | 5474 | 19% | 0 | unch |
-7 | 9513 | 15% | 0 | unch |
-8 | 10889 | 11% | 0 | unch |
-9 | 13388 | 7% | 0 | unch |
Si la expresión regular especificada coincide con muchos más patrones posibles, por ejemplo con la búsqueda ugrep --index -I -l '(todo|TODO)[: ]' , entonces podemos observar una mayor tasa de falsos positivos entre los 1317 archivos buscados. lo que resulta en tiempos de búsqueda ligeramente más largos:
| según | falsos positivos | tiempo de búsqueda (s) |
|---|---|---|
-0 | 189 | 0,292 |
-1 | 69 | 0,122 |
-2 | 43 | 0.103 |
-3 | 19 | 0.101 |
-4 | 16 | 0,097 |
-5 | 2 | 0.096 |
-6 | 1 | unch |
-7 | 0 | unch |
-8 | 0 | unch |
-9 | 0 | unch |
La precisión -4 es la predeterminada (antes -5 en versiones anteriores), que tiende a funcionar muy bien para buscar con patrones de expresiones regulares de complejidad modesta.
Una palabra de precaución. Siempre hay una pequeña sobrecarga para verificar los índices. Esto significa que si todos los archivos ya están almacenados en caché en la RAM, porque los archivos fueron buscados o leídos recientemente, entonces la indexación no necesariamente acelerará la búsqueda, obviamente. En ese caso, una búsqueda no indexada podría ser más rápida. Además, una búsqueda basada en índices tiene un tiempo de inicio más largo. Este tiempo de inicio aumenta cuando se utilizan clases de caracteres Unicode y comodines que deben convertirse en tablas hash.
En resumen, la búsqueda basada en índices es más eficaz cuando se buscan muchos archivos fríos y cuando los patrones de expresiones regulares no coinciden demasiado, es decir, queremos limitar el uso de repeticiones ilimitadas * y + y limitar el uso de clases de caracteres Unicode cuando posible. Esto reduce el tiempo de inicio de ugrep y limita la tasa de coincidencias de patrones falsos positivos (consulte también las preguntas y respuestas a continuación).
Indexe de forma recursiva e incremental todos los archivos no binarios que muestren progreso:
ugrep-indexer -I -v
Indexe de forma recursiva e incremental todos los archivos no binarios, incluidos los archivos no binarios almacenados en archivos comprimidos y en archivos comprimidos, mostrando el progreso:
ugrep-indexer -z -I -v
Indexe incrementalmente todos los archivos no binarios, incluidos archivos y archivos comprimidos, muestre el progreso, siga enlaces simbólicos a archivos (pero no a directorios), pero no indexe archivos ni directorios que coincidan con los globos en .gitignore:
ugrep-indexer -z -I -v -S -X
Fuerce la reindexación de todos los archivos no binarios, incluidos archivos y archivos comprimidos, siga enlaces simbólicos a archivos (pero no a directorios), pero no indexe archivos ni directorios que coincidan con los globos en .gitignore:
ugrep-indexer -f -z -I -v -S -X
Lo mismo, pero reduzca el almacenamiento de archivos de índice al mínimo disminuyendo la precisión de la indexación de 5 (predeterminado) a 0:
ugrep-indexer -f -0 -z -I -v -S -X
Aumente el rendimiento de la búsqueda aumentando la precisión de la indexación de 5 (predeterminado) a 7 a costa de archivos de índice más grandes:
ugrep-indexer -f7zIvSX
Elimine recursivamente todos los archivos de índice ._UG#_Store ocultos para restaurar el árbol de directorios a no indexado:
ugrep-indexer -d
Configurar y compilar con:
./build.sh
Si lo desea pero no es necesario, instale con:
sudo make install
Agregue una opción para crear un archivo de índice, por ejemplo, especificado explícitamente en ugrep. Esto podría mejorar aún más la velocidad de búsqueda indexada si el archivo indexado se encuentra en un sistema de archivos rápido. De lo contrario, no espere muchas mejoras o incluso una posible desaceleración, ya que no se puede buscar un único archivo de índice simultáneamente y se verificarán más entradas de índice cuando en realidad se omiten directorios (omitiendo también sus índices). Los experimentos lo dirán. Una advertencia fundamental de este enfoque es que la búsqueda basada en índices con ugrep --index ya no es segura: no se buscarán archivos nuevos y modificados que aún no estén indexados.
Cada filtro Bloom de N-gram tiene su propio "nivel de bits" en la tabla hash para evitar conflictos hash. Por ejemplo, 2 gramos no comparten ningún bit con 3 gramos. Esto garantiza que nunca tengamos falsos positivos con caracteres que coincidan falsamente y que en realidad no sean parte del patrón. Sin embargo, el espacio de bits de 1 gramo (un solo carácter) es pequeño (como máximo 256 bits). Por lo tanto, desperdiciamos algunos bits cuando las tablas hash son más grandes. Un posible enfoque para reducir el desperdicio es combinar 1 gramo con 2 gramos para compartir el mismo espacio de bits. Esto es fácil de hacer si consideramos que 1 gramo es igual a 2 gramos con el segundo carácter establecido en (NUL). Podemos reducir la tasa de falsos positivos con un segundo hash de 2 gramos basado en un método de hash diferente. O podemos ampliar los "niveles de bits" de 8 a 9 para almacenar 9 gramos. Esto aumentará la precisión de la indexación para patrones más largos (9 o más) sin costo adicional. Por otro lado, ese cambio puede causar más falsos positivos cuando coinciden falsamente caracteres que no forman parte del patrón; perdemos la ventaja de una precisión perfecta de 1 gramo.
La indexación agrega un archivo de índice oculto ._UG#_Store a cada directorio indexado. Los archivos indexados son escaneados (¡nunca modificados!) por ugrep-indexer para generar archivos de índice.
El tamaño de los archivos de índice depende de la precisión especificada, siendo -0 el más bajo (archivos de índice pequeños) y -9 el más alto (archivos de índice grandes). La precisión predeterminada es -4 . Consulte la siguiente pregunta para obtener detalles sobre el impacto de la precisión en el tamaño de la indexación frente a la velocidad de búsqueda.
La indexación nunca sigue enlaces simbólicos a directorios , porque los directorios enlazados simbólicamente pueden estar ubicados en cualquier lugar de un sistema de archivos, o en otro sistema de archivos, donde no queremos agregar archivos de índice. Aún puede indexar enlaces simbólicos a archivos con la opción ugrep-indexer -S .
La opción -v ( --verbose ) muestra el progreso de la indexación y el "ruido" de cada archivo indexado. El ruido es una medida de entropía o aleatoriedad en la entrada. Un mayor nivel de ruido significa que la indexación fue menos precisa al representar el contenido de un archivo. Por ejemplo, un archivo grande con datos aleatorios es difícil de indexar con precisión y tendrá un alto nivel de ruido.
La complejidad de la indexación es lineal en el tamaño de un archivo determinado a indexar. En la práctica, no es un proceso rápido, ni una búsqueda tan rápida, y puede llevar algún tiempo completar una pasada de indexación completa sobre un árbol de directorios grande. Cuando se completa la indexación, ugrep-indexer muestra los resultados de la indexación. También se informa el tamaño total de los índices agregados y el ruido de indexación promedio.
Al escanear un archivo para indexarlo, se obtiene una tabla de hashes de indexación de 64 KB. Luego, el indexador ugrep divide a la mitad la tabla con compresión de bits usando bit a bit, y siempre que no se exceda la precisión objetivo. La reducción a la mitad es posible gracias al hecho de que la tabla codifica hashes para 8 ventanas en desplazamientos desde el inicio del patrón, correspondientes a los 8 bits por celda de la tabla de hash de índice. La combinación de las dos mitades de la tabla puede convertir algunos bits de uno a cero, lo que puede provocar una coincidencia falsa positiva. Esto prueba la monotonicidad del indexador. Un valor hash de cero bits indica una posible coincidencia.
El ugrep-indexer detecta "archivos binarios", que pueden ignorarse y no indexarse con la opción -I ( --ignore-binary ) del ugrep-indexer. Esto es útil cuando se busca con la opción ugrep -I ( --ignore-binary ) para ignorar archivos binarios, que es un escenario típico.
El ugrep-indexer obedece a las exclusiones de archivos .gitignore cuando se especifica con la opción -X ( --ignore-files ). Los archivos y directorios ignorados no se indexarán para ahorrar espacio en el sistema de archivos. Esto funciona bien cuando se buscan archivos con la opción ugrep --ignore-files .
La indexación se puede cancelar, por ejemplo con CTRL-C, lo que no resultará en una pérdida de capacidad de búsqueda con ugrep, pero dejará la estructura del directorio sólo parcialmente indexada.
La opción -c comprueba los índices en busca de referencias obsoletas y archivos y directorios no indexados.
Los índices se eliminan con la opción ugrep-indexer -d .
El indexador ugrep ha sido probado exhaustivamente comparando los resultados de búsqueda ugrep --index con los resultados de búsqueda "lentos" no indexados ugrep en miles de archivos con miles de patrones de búsqueda aleatorios.
La búsqueda indexada funciona con todas las opciones de ugrep excepto con la opción -v ( --invert-match ), --filter , -P ( --perl-regexp ) y -Z ( --fuzzy ). La opción -c ( --count ) con --index configura automáticamente --min-count=1 para omitir todos los archivos con cero coincidencias.
Si se actualizaron, agregaron o eliminaron archivos o directorios después de la indexación, ugrep --index siempre buscará estos archivos y directorios cuando estén presentes en la ruta de búsqueda recursiva. Puede ejecutar ugrep-indexer nuevamente para actualizar incrementalmente todos los índices.
Los patrones de expresiones regulares se convierten internamente mediante ugrep con la opción --index a una forma de tablas hash para hasta los primeros 16 bytes de los patrones de expresiones regulares especificados, posiblemente más cortos para reducir el tiempo de construcción cuando los patrones de expresiones regulares son complejos. Por lo tanto, los primeros 8 a 16 caracteres de un patrón de expresiones regulares para buscar son los más críticos y no deben coincidir demasiado para limitar las llamadas coincidencias falsas positivas que pueden ralentizar la búsqueda.
En ugrep, un patrón de expresiones regulares se convierte en un DFA. Se construye un autómata finito de hash de indexación (HFA) sobre el DFA para representar de forma compacta las tablas hash como transiciones de estado con bordes etiquetados. Este HFA consta de hasta ocho capas, cada una desplazada un byte para representar la siguiente ventana de 8 bytes sobre el patrón. Cada capa HFA codifica hashes de índice para esa parte del patrón. La función hash de índice elegida es "aditiva", lo que significa que el siguiente byte se agrega cuando se combina con el hash anterior. Esto es muy importante ya que reduce críticamente los gastos generales de construcción del HFA. Ahora podemos codificar transiciones HFA etiquetadas a estados como múltiples aristas con rangos de valores hash de 16 bits en lugar de un conjunto de aristas individuales, cada una con un valor hash individual. Para este fin, utilizo mi biblioteca de rangos abiertos reflex::ORanges<T> derivada de std::set<T> .
A continuación se proporciona una función maybe_match() de cadena única muy simple con la función hash de índice principal 61 para demostrar la búsqueda basada en índices de una sola cadena:
// prime 61 hashing
uint16_t indexhash(uint16_t h, uint8_t b, size_t size)
{
return ((h << 6) - h - h - h + b) & (size - 1);
}
// return possible match of string given array of hashes of size <= 64K (power of two)
bool maybe_match(const char *string, uint8_t *hashes, size_t size)
{
size_t len = strlen(string); // practically we can and should limit len to e.g. 15 or 16
for (const char *window = string; len > 0; ++window, --len)
{
uint16_t h = window[0] & (size - 1);
if (hashes[h] & 0x01)
return false
size_t k, n = len < 8 ? len : 8;
for (k = 1; k < n; ++k)
{
h = indexhash(h, window[k], size);
if (hashes[h] & (1 << k))
return false;
}
}
return true;
}
El hash Prime 61 se eligió entre muchas otras funciones hash posibles utilizando una configuración experimental realista. Se probó una función hash candidata buscando repetidamente una palabra extraída al azar de un archivo de Wikipedia de 100 MB. La palabra fue mutada con una, dos o tres letras aleatorias. Esta mutación se verifica para asegurarse de que no corresponda a una palabra válida real en el archivo de Wikipedia. Luego se registró la tasa de falsos positivos cada vez que una palabra mutada coincide con el archivo. Una función hash con una tasa mínima de falsos positivos debería ser una buena candidata en general.
Al utilizar una ventana de 8 (o más corta dependiendo de la longitud del patrón), la tasa de falsos positivos es menor en comparación con los filtros Bloom estándar. Más específicamente, se utilizan funciones hash N² en lugar de N en un filtro Bloom. Para patrones más cortos, N suele ser demasiado pequeño para limitar los falsos positivos. Por tanto, el N² es más eficaz. También rechaza cualquier patrón de una coincidencia que tenga un carácter en cualquier lugar de los primeros 8 bytes del patrón que en realidad no aparece en ningún lugar de un archivo indexado, mientras que un filtro Bloom estándar podría tener una coincidencia falsa positiva. Además, el direccionamiento de bits utilizado para indexar la tabla hashes permite una compresión eficiente de la tabla.
La indexación es una forma de compresión con pérdidas. Cuanto mayor sea la precisión de la indexación, más rápido debería ser el rendimiento de la búsqueda ugrep al omitir más archivos que no coincidan. Una mayor precisión reduce el ruido (menos pérdidas). Un alto nivel de ruido hace que a veces ugrep busque archivos indexados que no coinciden. A estos los llamamos "coincidencias falsas positivas". Una mayor precisión requiere archivos de índice más grandes. Normalmente esperamos un almacenamiento de indexación de 4K o menos por archivo en promedio. El mínimo es 128 bytes de almacenamiento de índice por archivo, excluyendo el nombre del archivo y un encabezado de índice de 4 bytes. El máximo es 64 KB de almacenamiento por archivo para archivos muy grandes y ruidosos.
Al buscar archivos indexados con ugrep --index --stats , la opción --stats muestra las estadísticas de búsqueda una vez completada la búsqueda basada en indexación. Cuando muchos archivos no se omiten de la búsqueda debido al ruido de indexación (es decir, falsos positivos), una mayor precisión ayuda a aumentar la eficacia de la indexación, lo que puede acelerar la búsqueda.
Los archivos UTF-16 y UTF-32 también están indexados. El indexador los trata como UTF-8 después de convertirlos internamente a UTF-8 para indexarlos.
El espacio en disco se ahorra archivando (zip/tar/pax/cpio) y comprimiendo archivos. Por otro lado, la búsqueda de archivos comprimidos y comprimidos es mucho más lenta que la búsqueda de archivos normales. Indexar archivos y archivos comprimidos con ugrep-indexer -z -I y buscarlos con ugrep -z -I --index PATTERN acelera la búsqueda, es decir, cuando se omiten archivos y archivos comprimidos. Por otro lado, los requisitos de almacenamiento en disco aumentarán con la adición de entradas de archivos de índice para archivos comprimidos y comprimidos. Tenga en cuenta que cuando los archivos comprimidos contienen binarios, la opción -I ignora estos binarios.
La sobrecarga inicial de ugrep --index para construir tablas hash de indexación depende de los patrones de expresiones regulares. Si un patrón de expresiones regulares es muy "permisivo", es decir, coincide con muchos patrones posibles, entonces el tiempo de inicio de ugrep --index aumenta significativamente para calcular tablas hash. Esto puede suceder cuando se utilizan clases de caracteres Unicode grandes y comodines, especialmente con repeticiones ilimitadas * y + . Para saber cómo aumenta el tiempo de inicio, use la opción ugrep --index -r PATTERN /dev/null --stats=vm para buscar /dev/null con su PATRÓN.
Los archivos de índice deben tener un contenido de información muy denso y ese es el caso de este nuevo algoritmo de indexación para ugrep que diseñé e implementé. Cuanto más denso es un archivo de índice, más compacto representa con precisión los datos del archivo original. Eso hace que sea difícil o imposible comprimir archivos de índice. Este también es un buen indicador de la eficacia que tendrá un archivo de índice en la práctica.
