Krep - grepより5倍高速な文字列検索ツール

 (davidesantangelo.github.io)
10 ポイント 投稿者 GN⁺ 2025-03-13 | 2件のコメント | WhatsAppで共有
  • 性能が重要なアプリケーション向けにCで書かれた超高速文字列検索ツール
  • パターンの特性とハードウェアに応じて最適なアルゴリズムを動的に選択
  • SSE4.2/AVX2のようなハードウェアを活用し、最大スループットを提供
  • 大容量対応のためファイルをチャンクに分割し、マルチスレッド並列処理を実行
  • パターンに応じて最適な検索アルゴリズムを使用
    • Boyer-Moore-Horspool: 一般的なパターンマッチングに適する
    • Knuth-Morris-Pratt (KMP) アルゴリズム: 短いパターンに最適化
    • Rabin-Karp: 長いパターンに効果的
    • SIMDアクセラレーション: SSE4.2、AVX2対応ハードウェアで性能向上
  • メモリマップトファイルI/Oを使用してシステムコールを最小化し、スループットを最大化
  • 柔軟な検索オプション
    • 大文字小文字を区別する検索と区別しない検索
    • ファイル検索のほか、文字列を直接検索可能
    • 一致回数のみを出力するモードを提供

使用方法

krep [OPTIONS] PATTERN [FILE]
  • ログファイルで“error”を検索: krep "error" system.log
  • 大文字小文字を区別せず、8個のスレッドを使って検索: krep -i -t 8 "ERROR" large_logfile.log
  • 一致回数を出力（マッチした行は出力しない）: krep -c "TODO" *.c
  • ファイルではなく文字列から直接検索: krep -s "Hello" "Hello world"

コマンドラインオプション

  • -i : 大文字小文字を区別せず検索
  • -c : マッチした行を出力せず、一致回数のみを出力
  • -t NUM : NUM 個のスレッドを使用（デフォルト: 4）
  • -s STRING : ファイルではなく文字列から検索
  • -v : バージョン情報を出力
  • -h : ヘルプを出力

ベンチマーク

  • krepの性能は、一般的な文字列検索ツールと比べて非常に優れている。
    • krepは1GBのテキストファイルで一般的なパターンを検索するのに0.78秒かかり、これは毎秒1,282MBの速度を意味する
    • grepは同じ作業に2.95秒かかり、毎秒339MBの速度を記録した
    • ripgrepは1.48秒かかり、毎秒676MBの速度を示した
  • → krepはgrepより約3.8倍高速で、ripgrepより約1.9倍高速 （ハードウェアおよびファイル特性により性能は変わる場合がある）

名前の由来

  • 「krep」 はアイスランド語の**「kreppan」**に由来する
  • 「素早くつかみ取る」という意味を持つ
  • 効率的なパターン認識を象徴している
  • 短く簡潔なコマンド名で、タイピングしやすい

関連記事

2件のコメント

 
clickin 2025-03-13

正規表現対応を捨てたうえで ripgrep より2倍しか速くないのなら、活用度はやや低いですね。
私は普通に、正規表現が使える ripgrep を引き続き使うと思います。
 
GN⁺ 2025-03-13
Hacker Newsの意見

  • CPU機能（例: AVX2）はランタイムで検出されるべき

    • ifdefはコンパイラが対応しているかをビルド時に検出するだけ
    • プログラムはコンパイラがAVX2をサポートしている場合にのみコンパイルされる
    • ランタイムでCPUがAVX2をサポートしているか確認する必要がある
    • プロジェクトには「構成時にCPUIDフラグと実際の命令実行テストを通じて検出」という記述がある
    • SSE4.2とAVX2命令を自動的に活用できる

  • krepプロジェクトに関するブログ記事の紹介

    • ホームページではripgrepより高速だとされている
    • ripgrep全体のベンチマークと比較してみたい
    • madvise()関連のエラーが発生し、MakefileのCFLAGSに-D_GNU_SOURCEを追加する必要がある

  • テストケースの重要性

    • マルチスレッドのファイル検索ではチャンク境界の問題が気になる
    • 単純な検索に新たなエッジケースを持ち込んでいる
    • ファイルに1文字追加するとマッチが壊れる可能性がある

  • ビルド問題解決後のベンチマーク結果

    • 最初のベンチマーク試行では速度が遅い
    • ripgrepがkrepより1.52倍高速

  • マッチ頻度が高いベンチマークの試行

    • krepがripgrepより3.40倍高速
    • マッチ数に大きな差がある
    • krepは正確な結果を返していない可能性がある

  • 追加のベンチマーク試行

    • ripgrepのほうが特定のパターンを見つけるのが速い
    • krepはマッチを見つけられない

  • ripgrepのアルゴリズムとメモリマップの使用

    • ripgrepは高度な部分文字列検索アルゴリズムを使用している
    • メモリマップと並列処理を使用している
    • krepも並列処理を使用しており、単一ファイル検索時にもマルチスレッドを使う

  • ベンチマーク結果への疑問

    • ripgrepが5GBファイルでパターン検索に40秒以上かかるのは不自然
    • OPにベンチマークの再現方法を求めている

  • krepという名前に関する意見

    • grepの「re」は正規表現を意味する
    • krepは正規表現を使わないため、名前が不適切かもしれない