Krep - herramienta de búsqueda de cadenas 5 veces más rápida que grep

• Herramienta de búsqueda de cadenas ultrarrápida escrita en C para aplicaciones donde el rendimiento es crítico
• Selecciona dinámicamente el algoritmo óptimo según las características del patrón y el hardware
• Aprovecha hardware como SSE4.2/AVX2 para ofrecer el máximo rendimiento
• Divide los archivos en chunks para admitir grandes volúmenes y realiza procesamiento paralelo multihilo
• Usa el algoritmo de búsqueda más adecuado según el patrón
  • Boyer-Moore-Horspool: adecuado para coincidencia de patrones en general
  • Algoritmo Knuth-Morris-Pratt (KMP): optimizado para patrones cortos
  • Rabin-Karp: eficaz para patrones largos
  • Aceleración SIMD: mejora de rendimiento en hardware compatible con SSE4.2 y AVX2
• Usa I/O de archivos con mapeo de memoria para minimizar llamadas al sistema y maximizar el rendimiento
• Opciones de búsqueda flexibles
  • Búsqueda sensible e insensible a mayúsculas/minúsculas
  • Además de buscar en archivos, permite buscar directamente en cadenas
  • Incluye un modo para mostrar solo la cantidad de coincidencias

Uso

krep [OPTIONS] PATTERN [FILE]  

• Buscar “error” en un archivo de logs: krep "error" system.log
• Buscar sin distinguir mayúsculas/minúsculas usando 8 hilos: krep -i -t 8 "ERROR" large_logfile.log
• Mostrar la cantidad de coincidencias (sin imprimir las líneas encontradas): krep -c "TODO" *.c
• Buscar directamente en una cadena en lugar de un archivo: krep -s "Hello" "Hello world"

Opciones de línea de comandos

• -i : buscar sin distinguir mayúsculas/minúsculas
• -c : mostrar solo la cantidad de coincidencias, sin imprimir las líneas encontradas
• -t NUM : usar NUM hilos (valor predeterminado: 4)
• -s STRING : buscar en una cadena en lugar de un archivo
• -v : mostrar información de versión
• -h : mostrar ayuda

Benchmarks

• El rendimiento de krep es sobresaliente en comparación con herramientas comunes de búsqueda de cadenas.
  • krep tardó 0.78 segundos en buscar un patrón común en un archivo de texto de 1GB, lo que equivale a 1,282MB por segundo
  • grep tardó 2.95 segundos en la misma tarea, con una velocidad de 339MB por segundo
  • ripgrep tardó 1.48 segundos, mostrando una velocidad de 676MB por segundo
• → krep es aproximadamente 3.8 veces más rápido que grep y 1.9 veces más rápido que ripgrep (el rendimiento puede variar según el hardware y las características del archivo)

Origen del nombre

• “krep” proviene del islandés “kreppan”
• Significa “agarrar rápidamente”
• Simboliza el reconocimiento eficiente de patrones
• Es un comando corto y conciso, fácil de escribir

[clickin]

Si al abandonar el soporte para expresiones regulares solo logra ser el doble de rápido que ripgrep, la utilidad sí queda un poco limitada.
Creo que yo simplemente seguiré usando ripgrep, que sí soporta expresiones regulares.

[GN⁺]

Comentarios en Hacker News

• Las funciones de CPU (por ejemplo, AVX2) deben detectarse en tiempo de ejecución

  • ifdef solo detecta en tiempo de compilación si el compilador lo soporta
  • El programa solo se compila cuando el compilador soporta AVX2
  • Hay que verificar en tiempo de ejecución si la CPU soporta AVX2
  • En el proyecto aparece la parte de "detección en tiempo de configuración mediante banderas CPUID y prueba real de ejecución de instrucciones"
  • Puede aprovechar automáticamente las instrucciones SSE4.2 y AVX2

• Presentación de una publicación de blog sobre el proyecto krep

  • En la página principal dice que es más rápido que ripgrep
  • Quisiera compararlo con el benchmark completo de ripgrep
  • Ocurre un error relacionado con madvise(), y hace falta agregar -D_GNU_SOURCE a CFLAGS del Makefile

• Importancia de los casos de prueba

  • Preocupa el problema de los límites de bloque en la búsqueda de archivos multihilo
  • Introduce nuevos casos límite en una búsqueda simple
  • Agregar un solo carácter al archivo puede romper una coincidencia

• Resultados del benchmark tras resolver el problema de compilación

  • En el primer intento de benchmark la velocidad es lenta
  • ripgrep es 1.52 veces más rápido que krep

• Intento de benchmark con alta frecuencia de coincidencias

  • krep es 3.40 veces más rápido que ripgrep
  • La cantidad de coincidencias difiere mucho
  • Puede que krep no esté dando resultados correctos

• Intentos adicionales de benchmark

  • ripgrep es más rápido para encontrar ciertos patrones
  • krep no encuentra coincidencias

• Algoritmo de ripgrep y uso de memoria mapeada

  • ripgrep usa algoritmos avanzados de búsqueda de subcadenas
  • Usa memoria mapeada y procesamiento en paralelo
  • krep también usa procesamiento en paralelo, y usa multihilo al buscar en un solo archivo

• Dudas sobre los resultados del benchmark

  • Es raro que ripgrep tarde más de 40 segundos en buscar un patrón en un archivo de 5 GB
  • Le piden al OP que explique cómo reprodujo el benchmark

• Opiniones sobre el nombre krep

  • El "re" de grep significa expresiones regulares
  • Como krep no usa expresiones regulares, puede que el nombre no sea el correcto