Krep - Ein 5-mal schnelleres String-Suchwerkzeug als grep

• Ein ultraschnelles String-Suchwerkzeug, in C geschrieben, für Anwendungen, bei denen Performance entscheidend ist
• Wählt dynamisch den optimalen Algorithmus je nach Mustercharakteristik und Hardware
• Nutzt Hardware wie SSE4.2/AVX2, um maximalen Durchsatz zu liefern
• Teilt Dateien für die Unterstützung großer Datenmengen in Chunks auf und verarbeitet sie per multithreaded Parallelisierung
• Verwendet je nach Muster den am besten geeigneten Suchalgorithmus
  • Boyer-Moore-Horspool: geeignet für allgemeines Pattern Matching
  • Knuth-Morris-Pratt (KMP)-Algorithmus: für kurze Muster optimiert
  • Rabin-Karp: effektiv für lange Muster
  • SIMD-Beschleunigung: bessere Performance auf Hardware mit SSE4.2- und AVX2-Unterstützung
• Verwendet Memory-Mapped File I/O, um Systemaufrufe zu minimieren und den Durchsatz zu maximieren
• Flexible Suchoptionen
  • Suche mit und ohne Groß-/Kleinschreibung
  • Neben der Dateisuche auch direkte Suche in Strings möglich
  • Modus zur Ausgabe nur der Anzahl von Treffern verfügbar

Verwendung

krep [OPTIONS] PATTERN [FILE]  

• Suche nach „error“ in einer Logdatei: krep "error" system.log
• Suche ohne Groß-/Kleinschreibung mit 8 Threads: krep -i -t 8 "ERROR" large_logfile.log
• Anzahl der Treffer ausgeben (ohne die gematchten Zeilen auszugeben): krep -c "TODO" *.c
• Direkte Suche in einem String statt in einer Datei: krep -s "Hello" "Hello world"

Kommandozeilenoptionen

• -i : Suche ohne Groß-/Kleinschreibung
• -c : Gibt nur die Anzahl der Treffer aus, ohne gematchte Zeilen auszugeben
• -t NUM : Verwendet NUM Threads (Standard: 4)
• -s STRING : Sucht in einem String statt in einer Datei
• -v : Gibt Versionsinformationen aus
• -h : Gibt die Hilfe aus

Benchmark

• Die Performance von krep ist im Vergleich zu gängigen String-Suchwerkzeugen sehr stark.
  • krep benötigte 0,78 Sekunden, um in einer 1-GB-Textdatei nach einem typischen Muster zu suchen, was einer Geschwindigkeit von 1.282 MB/s entspricht
  • grep benötigte für dieselbe Aufgabe 2,95 Sekunden und erreichte 339 MB/s
  • ripgrep benötigte 1,48 Sekunden und erreichte 676 MB/s
• → krep ist etwa 3,8-mal schneller als grep und etwa 1,9-mal schneller als ripgrep (die Performance kann je nach Hardware und Dateieigenschaften variieren)

Herkunft des Namens

• „krep“ leitet sich vom isländischen „kreppan“ ab
• Bedeutet „schnell greifen“
• Symbolisiert effiziente Mustererkennung
• Ein kurzer, prägnanter Befehl, der sich leicht tippen lässt

[clickin]

Wenn man auf die Unterstützung regulärer Ausdrücke verzichtet und dann trotzdem nur doppelt so schnell wie ripgrep ist, ist der praktische Nutzen eher begrenzt.
Ich werde wohl einfach weiter ripgrep mit Regex-Unterstützung benutzen.

[GN⁺]

Hacker-News-Kommentare

• CPU-Funktionen (z. B. AVX2) sollten zur Laufzeit erkannt werden

  • ifdef erkennt nur zur Build-Zeit, ob der Compiler sie unterstützt
  • Das Programm wird nur kompiliert, wenn der Compiler AVX2 unterstützt
  • Zur Laufzeit muss geprüft werden, ob die CPU AVX2 unterstützt
  • Im Projekt gibt es die Aussage „Erkennung zur Konfigurationszeit über CPUID-Flags und Tests der tatsächlichen Befehlsausführung“
  • SSE4.2- und AVX2-Befehle können automatisch genutzt werden

• Vorstellung eines Blogbeitrags zum krep-Projekt

  • Auf der Homepage heißt es, es sei schneller als ripgrep
  • Ich würde es gern mit dem vollständigen ripgrep-Benchmark vergleichen
  • Fehler im Zusammenhang mit madvise(), in den CFLAGS des Makefile muss -D_GNU_SOURCE ergänzt werden

• Die Bedeutung von Testfällen

  • Das Problem mit Chunk-Grenzen bei der Multithread-Dateisuche ist bedenklich
  • Es führt neue Edge Cases in eine einfache Suche ein
  • Fügt man der Datei ein einzelnes Zeichen hinzu, kann ein Match kaputtgehen

• Benchmark-Ergebnisse nach Behebung der Build-Probleme

  • Beim ersten Benchmark-Versuch ist die Geschwindigkeit langsam
  • ripgrep ist 1,52-mal schneller als krep

• Benchmark-Versuch mit hoher Match-Häufigkeit

  • krep ist 3,40-mal schneller als ripgrep
  • Die Anzahl der Matches unterscheidet sich stark
  • krep liefert möglicherweise keine korrekten Ergebnisse

• Weitere Benchmark-Versuche

  • ripgrep ist beim Finden bestimmter Muster schneller
  • krep findet keine Matches

• ripgreps Algorithmus und die Nutzung von Memory-Mapping

  • ripgrep verwendet einen fortschrittlichen Substring-Suchalgorithmus
  • Es nutzt Memory-Mapping und Parallelisierung
  • krep nutzt ebenfalls Parallelisierung und verwendet Multithreading bei der Suche in einer einzelnen Datei

• Zweifel an den Benchmark-Ergebnissen

  • Dass ripgrep bei der Mustersuche in einer 5-GB-Datei mehr als 40 Sekunden braucht, ist merkwürdig
  • Bitte an den OP, zu erklären, wie der Benchmark reproduziert werden kann

• Meinung zum Namen krep

  • Das „re“ in grep steht für reguläre Ausdrücke
  • krep verwendet keine regulären Ausdrücke, daher könnte der Name unpassend sein