Krep - un outil de recherche de chaînes 5 fois plus rapide que grep

• Un outil de recherche de chaînes ultra-rapide, écrit en C, pour les applications où les performances sont cruciales
• Sélection dynamique de l’algorithme optimal selon les caractéristiques du motif et le matériel
• Exploite le matériel comme SSE4.2/AVX2 pour offrir un débit maximal
• Découpe les fichiers en chunks pour un traitement parallèle multithread afin de gérer de très gros volumes
• Utilise l’algorithme de recherche le plus adapté selon le motif
  • Boyer-Moore-Horspool : adapté à la recherche de motifs générale
  • Algorithme Knuth-Morris-Pratt (KMP) : optimisé pour les motifs courts
  • Rabin-Karp : efficace pour les motifs longs
  • Accélération SIMD : amélioration des performances sur le matériel compatible SSE4.2 et AVX2
• Utilise les fichiers mappés en mémoire pour les E/S afin de minimiser les appels système et maximiser le débit
• Options de recherche flexibles
  • Recherche sensible et insensible à la casse
  • Possibilité de rechercher directement dans une chaîne, en plus des fichiers
  • Mode permettant d’afficher uniquement le nombre de correspondances

Utilisation

krep [OPTIONS] PATTERN [FILE]  

• Rechercher « error » dans un fichier journal : krep "error" system.log
• Rechercher sans tenir compte de la casse avec 8 threads : krep -i -t 8 "ERROR" large_logfile.log
• Afficher le nombre de correspondances (sans afficher les lignes correspondantes) : krep -c "TODO" *.c
• Rechercher directement dans une chaîne au lieu d’un fichier : krep -s "Hello" "Hello world"

Options en ligne de commande

• -i : recherche insensible à la casse
• -c : affiche uniquement le nombre de correspondances sans afficher les lignes correspondantes
• -t NUM : utilise NUM threads (valeur par défaut : 4)
• -s STRING : recherche dans une chaîne plutôt que dans un fichier
• -v : affiche les informations de version
• -h : affiche l’aide

Benchmarks

• Les performances de krep sont excellentes par rapport aux outils classiques de recherche de chaînes.
  • krep a mis 0,78 seconde pour rechercher un motif courant dans un fichier texte de 1 Go, soit un débit de 1 282 Mo/s
  • grep a mis 2,95 secondes pour la même tâche, avec un débit de 339 Mo/s
  • ripgrep a mis 1,48 seconde, avec un débit de 676 Mo/s
• → krep est environ 3,8 fois plus rapide que grep, et environ 1,9 fois plus rapide que ripgrep (les performances peuvent varier selon le matériel et les caractéristiques du fichier)

Origine du nom

• « krep » vient de l’islandais « kreppan »
• Le mot signifie « saisir rapidement »
• Il symbolise une reconnaissance efficace des motifs
• C’est une commande courte et concise, facile à taper

[clickin]

Abandonner la prise en charge des expressions régulières pour n’être que deux fois plus rapide que ripgrep, ça réduit quand même pas mal son intérêt.
Moi, je pense que je vais simplement continuer à utiliser ripgrep, qui gère les expressions régulières.

[GN⁺]

Avis sur Hacker News

• Les fonctionnalités CPU (par ex. AVX2) doivent être détectées à l’exécution

  • ifdef ne détecte qu’à la compilation si le compilateur les prend en charge
  • Le programme n’est compilé que lorsque le compilateur prend en charge AVX2
  • Il faut vérifier à l’exécution si le CPU prend en charge AVX2
  • Le projet mentionne une « détection au moment de la configuration via les drapeaux CPUID et un test réel d’exécution des instructions »
  • Il peut exploiter automatiquement les instructions SSE4.2 et AVX2

• Présentation d’un billet de blog sur le projet krep

  • La page d’accueil affirme qu’il est plus rapide que ripgrep
  • J’aimerais voir une comparaison avec l’ensemble des benchmarks de ripgrep
  • Une erreur liée à madvise() se produit, il faut ajouter -D_GNU_SOURCE aux CFLAGS du Makefile

• Importance des cas de test

  • Le problème des frontières de blocs dans la recherche de fichiers multithread est préoccupant
  • Cela introduit de nouveaux edge cases dans une recherche simple
  • Ajouter un caractère dans le fichier peut casser une correspondance

• Résultats des benchmarks après résolution du problème de build

  • Lors de la première tentative de benchmark, la vitesse est lente
  • ripgrep est 1,52 fois plus rapide que krep

• Tentative de benchmark avec une fréquence élevée de correspondances

  • krep est 3,40 fois plus rapide que ripgrep
  • Le nombre de correspondances diffère fortement
  • krep pourrait ne pas fournir des résultats corrects

• Tentatives de benchmark supplémentaires

  • ripgrep est plus rapide pour trouver certains motifs
  • krep ne trouve pas les correspondances

• Algorithme de ripgrep et usage du memory mapping

  • ripgrep utilise des algorithmes avancés de recherche de sous-chaînes
  • Il utilise le memory mapping et le traitement parallèle
  • krep utilise aussi le traitement parallèle, avec du multithreading même pour la recherche dans un seul fichier

• Doutes sur les résultats des benchmarks

  • Il est étrange que ripgrep mette plus de 40 secondes à rechercher un motif dans un fichier de 5 Go
  • Demande à l’OP comment reproduire le benchmark

• Avis sur le nom de krep

  • Le « re » de grep signifie expressions régulières
  • Comme krep n’utilise pas d’expressions régulières, le nom est peut-être inadapté