ugrep indexer
v1.0.0
ugrep-indexerユーティリティは、再帰的にファイルのインデックスを作成し、再帰的な grep を高速化します。
また、コマンドライン オプションで指定すると、アーカイブおよび圧縮ファイルの内容にインデックスが付けられます。これにより、指定されたパターンに一致するコンテンツがない場合に、それらを検索する必要がなくなります。
ugrep は、インデックスベースの検索をサポートする grep 互換の高速ファイル検索ツールです。インデックス ベースの検索は、遅いファイル システムやファイル システムのキャッシュが効果的でない場合に大幅に高速化されます。検索対象のドライブ上のファイル システムが RAM にキャッシュされていない、つまり「コールド」な場合、インデックスを作成すると検索が高速化されます。ファイルのインデックスを使用して、指定された正規表現パターンに一致する可能性のあるファイルのみを検索します。このインデックスにより、一致する可能性があるかどうかを簡単にチェックできるため、すべてのファイルを検索する必要がなくなります。
ugrep を使用したインデックスベースの検索は安全であり、一致する可能性のある更新されたファイルをスキップすることはありません。インデックス作成後にファイルやディレクトリが追加または変更された場合、検索ではファイルおよびディレクトリのタイムスタンプとインデックス作成のタイムスタンプを比較することにより、ファイル システムに加えられたこれらの追加や変更が常に検索されます。
インデックス作成後に多くのファイルが追加または変更された場合、インデックスを最新の状態にするために再インデックスが必要になる場合があります。再インデックス作成は増分であるため、最初のインデックス作成プロセスほど時間はかかりません。
インデックスベースの検索の典型的かつ小規模な例です。たとえば、別のドライブに配置された ugrep v3.12.6 リポジトリ上での検索です。
$ 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
インデックス作成を行わないコールド ファイル システムでの通常の検索には、 driveをアンマウントし、再度マウントして FS キャッシュをクリアしてインデックス作成の効果を記録した後、1.02 秒かかります。
$ 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 では、同じコールド検索で 1.18 秒かかり、さらに時間がかかります (ripgrep はデフォルトでバイナリ ファイルをスキップするため、オプション-Iは指定されていません)。
$ time rg -l 'std::chrono'
src/ugrep.cpp
1.18 real 0.01 user 0.06 sys
対照的に、インデックス作成では、コールド ファイル システムの検索に ugrep を使用すると 0.0487 秒しかかかりません。これは、 driveをアンマウントし、再度マウントして FS キャッシュをクリアしてインデックス作成の効果を記録した後、21 倍高速になります。
$ 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
経過時間には常にある程度のばらつきがあり、検索時間の範囲が 0.0487 (21 倍の高速化) ～ 0.0983 秒 (10 倍の高速化) となった 4 回の検索実行の最良時間は 0.0487 秒です。
いくつかの要因、インデックス付けされたファイルのサイズ、ファイル システムの読み取り速度、およびほとんどのファイルがコールドであるとの仮定に応じて、この小規模なデモと比較して速度の向上は一般的に大幅に高くなる可能性があります。
私が設計したインデックス作成アルゴリズムはおそらく単調です。精度が高くなると、誤検知率が減り、検索パフォーマンスの向上が保証されますが、インデックス ストレージのオーバーヘッドも増加します。同様に、精度が低いと検索パフォーマンスが低下しますが、インデックス ストレージのオーバーヘッドも軽減されます。したがって、インデクサーをmonotonic インデクサーと名付けました。
ファイル ストレージ スペースが貴重な場合は、より低いインデックス作成精度を指定することで、インデックス ストレージのオーバーヘッドを減らすことができます。
レベル 0 (オプション-0 ) で上記の例にインデックスを付けると、インデックス作成ストレージのオーバーヘッドが 8.6 倍減少し、ファイルあたり 4256 バイトからファイルあたりわずか 490 バイトに減少します。
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
この例では、実際に 16 個のファイルが検索されました (15 個の誤検知) ため、インデックス付き検索はインデックスなしの検索よりも 12 倍高速です。
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
この例よりも複雑な正規表現パターンでは、自然に誤検知率が高くなる可能性があります。これは、一致しないにもかかわらず、一致する可能性があるとみなされるファイルの割合です。誤検知率が大きくなり影響がある場合、誤検知率が高くなると検索速度が低下する可能性があります。
次の表は、インデックス作成の精度がインデックス作成ストレージとインデックス付けされたファイルごとの平均ノイズにどのような影響を与えるかを示しています。右端の列は、 ugrep --index -I -l 'std::chrono'の検索速度と誤検知率を示しています。
| 準拠 | インデックスストレージ (KB) | 平均ノイズ | 誤検知 | 検索時間(秒) |
|---|---|---|---|---|
-0 | 631 | 42% | 15 | 0.0722 |
-1 | 1276 | 39% | 1 | 0.0506 |
-2 | 1576年 | 36% | 0 | 0.0487 |
-3 | 2692 | 31% | 0 | ウンチ |
-4 | 2966 | 28% | 0 | ウンチ |
-5 | 4953 | 23% | 0 | ウンチ |
-6 | 5474 | 19% | 0 | ウンチ |
-7 | 9513 | 15% | 0 | ウンチ |
-8 | 10889 | 11% | 0 | ウンチ |
-9 | 13388 | 7% | 0 | ウンチ |
指定された正規表現が、たとえばugrep --index -I -l '(todo|TODO)[: ]'の検索で、より多くの考えられるパターンに一致する場合、検索された 1317 ファイルの中で誤検知の割合が高くなる可能性があります。その結果、検索時間がわずかに長くなります。
| 準拠 | 誤検知 | 検索時間(秒) |
|---|---|---|
-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 | ウンチ |
-7 | 0 | ウンチ |
-8 | 0 | ウンチ |
-9 | 0 | ウンチ |
精度-4がデフォルトです (以前のリリースでは-5でした)。これは、それほど複雑でない正規表現パターンでの検索に非常にうまく機能する傾向があります。
注意点が 1 つあります。インデックスをチェックするには、常にわずかなオーバーヘッドが発生します。これは、ファイルが最近検索または読み取られたため、すべてのファイルがすでに RAM にキャッシュされている場合、明らかに、インデックス作成によって検索が高速化される必要はないことを意味します。その場合、インデックスを付けない検索の方が高速になる可能性があります。さらに、インデックスベースの検索は起動時間が長くなります。ハッシュ テーブルに変換する必要がある Unicode 文字クラスとワイルドカードが使用されている場合、この起動時間は長くなります。
要約すると、インデックス ベースの検索は、大量のコールド ファイルを検索する場合や、正規表現パターンがあまり一致しない場合に最も効果的です。つまり、無制限の繰り返し*と+の使用を制限し、Unicode 文字クラスの使用を制限したい場合です。可能。これにより、ugrep の起動時間が短縮され、誤検知パターンの一致率が制限されます (以下の Q&A も参照)。
すべての非バイナリ ファイルに再帰的かつ増分的にインデックスを作成し、進行状況を表示します。
ugrep-indexer -I -v
アーカイブや圧縮ファイルに保存されている非バイナリ ファイルを含む、すべての非バイナリ ファイルを再帰的かつ増分的にインデックス付けし、進行状況を表示します。
ugrep-indexer -z -I -v
アーカイブや圧縮ファイルを含むすべての非バイナリ ファイルの増分インデックスを作成し、進行状況を表示し、ファイルへのシンボリック リンクをたどります (ただし、ディレクトリへのシンボリック リンクはたどりません)。ただし、.gitignore 内のグロブに一致するファイルとディレクトリのインデックスは作成しません。
ugrep-indexer -z -I -v -S -X
アーカイブや圧縮ファイルを含むすべての非バイナリ ファイルのインデックスの再作成を強制的に行い、ファイルへのシンボリック リンクをたどりますが (ディレクトリへのリンクではありません)、.gitignore 内のグロブに一致するファイルとディレクトリのインデックスは作成しません。
ugrep-indexer -f -z -I -v -S -X
同じですが、インデックス作成の精度を 5 (デフォルト) から 0 に下げることで、インデックス ファイルのストレージを最小限に抑えます。
ugrep-indexer -f -0 -z -I -v -S -X
インデックス ファイルのサイズが大きくなりますが、インデックス作成の精度を 5 (デフォルト) から 7 に増やすことで、検索パフォーマンスを向上させます。
ugrep-indexer -f7zIvSX
すべての非表示の._UG#_Storeインデックス ファイルを再帰的に削除して、ディレクトリ ツリーをインデックスなしの状態に復元します。
ugrep-indexer -d
以下を使用して構成およびコンパイルします。
./build.sh
必須ではないが必要な場合は、次のようにインストールします。
sudo make install
1 つのインデックス ファイルを作成するオプションを追加します。たとえば、ugrep に明示的に指定します。これにより、インデックス ファイルが高速なファイル システム上にある場合、インデックス付きの検索速度がさらに向上する可能性があります。それ以外の場合は、単一のインデックス ファイルを同時に検索することができず、実際にディレクトリがスキップされる (インデックスもスキップする) ときにさらに多くのインデックス エントリがチェックされるため、大きな改善は期待できず、場合によっては速度が低下する可能性もあります。実験すれば分かるだろう。このアプローチの重要な注意点は、 ugrep --indexを使用したインデックス ベースの検索が安全ではなくなっていることです。インデックスが作成されていない新しいファイルや変更されたファイルは検索されません。
各 N-gram ブルーム フィルターには、ハッシュの競合を避けるためにハッシュ テーブル内に独自の「ビット層」があります。たとえば、2 グラムは 3 グラムとビットを共有しません。これにより、実際にはパターンの一部ではない文字が誤って一致するという誤検知が発生することがなくなります。ただし、1 グラム (単一文字) のビット空間は小さい (最大 256 ビット)。したがって、ハッシュ テーブルが大きい場合、一部のビットが無駄になります。無駄を減らすために考えられるアプローチは、1 グラムと 2 グラムを組み合わせて同じビット空間を共有することです。これは、2 番目の文字が (NUL) に設定された 1 グラムが 2 グラムと等しいと考えると簡単に実行できます。別のハッシュ方法に基づいた 2 番目の 2 グラム ハッシュを使用すると、誤検知率を下げることができます。あるいは、「ビット層」を 8 から 9 に拡張して、9 グラムを保存することもできます。これにより、追加コストなしで、長いパターン (9 つ以上) のインデックス作成の精度が向上します。一方で、その変更により、パターンに含まれない文字が誤って一致した場合に、より多くの誤検知が発生する可能性があります。完璧な 1 グラム精度という利点が失われます。
インデックスを作成すると、インデックスが作成された各ディレクトリに隠しインデックス ファイル._UG#_Storeが追加されます。インデックス付けされたファイルは、ugrep-indexer によってスキャンされ (決して変更されません)、インデックス ファイルが生成されます。
インデックス ファイルのサイズは指定された精度によって異なり、 -0が最小 (小さなインデックス ファイル)、 -9最大 (大きなインデックス ファイル) となります。デフォルトの精度は-4です。インデックス作成サイズと検索速度に対する精度の影響の詳細については、次の Q を参照してください。
シンボリックにリンクされたディレクトリは、インデックス ファイルを追加したくないファイル システムまたは別のファイル システム内の任意の場所に配置される可能性があるため、インデックス作成はディレクトリへのシンボリック リンクをたどることはありません。 ugrep-indexer オプション-Sを使用すると、ファイルへのシンボリック リンクのインデックスを作成できます。
オプション-v ( --verbose ) は、インデックス付けの進行状況と、インデックス付けされた各ファイルの「ノイズ」を表示します。ノイズは、入力のエントロピーまたはランダム性の尺度です。ノイズのレベルが高いということは、ファイルの内容を表すインデックス作成の精度が低いことを意味します。たとえば、ランダムなデータを含む大きなファイルは、正確にインデックスを作成するのが難しく、高レベルのノイズが発生します。
インデックス作成の複雑さは、インデックスを作成する特定のファイルのサイズに比例します。実際には、これは高速なプロセスではなく、検索もそれほど速くなく、大きなディレクトリ ツリーに対する完全なインデックス作成パスを完了するには時間がかかる場合があります。インデックス作成が完了すると、ugrep-indexer によってインデックス作成の結果が表示されます。追加されたインデックスの合計サイズと平均インデックス作成ノイズも報告されます。
ファイルをスキャンしてインデックスを作成すると、64KB のインデックス付けハッシュ テーブルが作成されます。次に、ugrep-indexer は、目標精度を超えない限り、bitwise-and を使用したビット圧縮でテーブルを半分にします。半分にすることは、インデックス ハッシュ テーブル セルあたり 8 ビットに対応する、パターンの開始からのオフセットでテーブルが 8 ウィンドウのハッシュをエンコードするという事実によって可能になります。テーブルの 2 つの半分を組み合わせると、一部のビットが 1 から 0 に反転し、誤検出一致が発生する可能性があります。これは、インデクサーの単調性を証明します。ゼロビットのハッシュ値は一致の可能性を示します。
ugrep-indexer は「バイナリ ファイル」を検出しますが、これは無視でき、ugrep-indexer オプション-I ( --ignore-binary ) を使用してインデックスを作成することはできません。これは、典型的なシナリオである、ugrep オプション-I ( --ignore-binary ) を使用してバイナリ ファイルを無視して検索する場合に便利です。
ugrep-indexer は、オプション-X ( --ignore-files ) で指定された場合、 .gitignore ファイルの除外に従います。ファイル システムのスペースを節約するために、無視されたファイルとディレクトリにはインデックスが作成されません。これは、ugrep オプション--ignore-filesを使用してファイルを検索する場合にうまく機能します。
インデックス作成は、CTRL-C などで中止できます。その場合、ugrep による検索機能は失われませんが、ディレクトリ構造のインデックスが部分的にのみ残されます。
オプション-c 、古い参照やインデックスのないファイルやディレクトリのインデックスをチェックします。
インデックスは、ugrep-indexer オプション-dを使用して削除されます。
ugrep-indexer は、数千のランダムな検索パターンを使用した数千のファイルに対するugrep --index検索結果と、インデックスのない「遅い」 ugrep検索結果を比較することによって広範囲にテストされています。
インデックスベースの検索は、オプション-v ( --invert-match )、 --filter 、 -P ( --perl-regexp )、および-Z ( --fuzzy ) を除くすべての ugrep オプションで機能します。 --indexを指定したオプション-c ( --count ) を使用すると、 --min-count=1が自動的に設定され、ゼロ一致のファイルをすべてスキップします。
インデックス作成後にファイルまたはディレクトリが更新、追加、または削除された場合、ugrep --index 、再帰的検索パス上に存在するこれらのファイルおよびディレクトリを常に検索します。 ugrep-indexer を再度実行すると、すべてのインデックスを増分更新できます。
正規表現パターンは、オプション--indexを使用した ugrep によって、指定された正規表現パターンの最初の 16 バイトまでのハッシュ テーブルの形式に内部的に変換されます。正規表現パターンが複雑な場合、構築時間を短縮するために、場合によっては短縮される可能性があります。したがって、検索する正規表現パターンの最初の 8 ～ 16 文字が最も重要であり、検索速度を低下させる可能性があるいわゆる誤検出一致を制限するために、一致しすぎないようにする必要があります。
ugrep では、正規表現パターンが DFA に変換されます。インデックス付けハッシュ有限オートマトン (HFA) は、ラベル付きエッジを持つ状態遷移としてハッシュ テーブルをコンパクトに表現するために、DFA の上に構築されます。この HFA は最大 8 つのレイヤーで構成され、各レイヤーは 1 バイトずつシフトされ、パターン上の次の 8 バイト ウィンドウを表します。各 HFA レイヤーは、パターンのその部分のインデックス ハッシュをエンコードします。選択されたインデックス ハッシュ関数は「加算的」です。これは、前のハッシュでハッシュされるときに次のバイトが追加されることを意味します。これは、HFA 構築のオーバーヘッドを大幅に削減するため、非常に重要です。状態へのラベル付き HFA 遷移を、それぞれが個別のハッシュ値を持つ単一エッジのセットではなく、16 ビットのハッシュ値範囲を持つ複数のエッジとしてエンコードできるようになりました。この目的のために、私はstd::set<T>から派生したオープンエンド範囲ライブラリreflex::ORanges<T>を使用します。
単一文字列のインデックスベースの検索を示すために、プライム 61 インデックス ハッシュ関数を使用した非常に単純な単一文字列のmaybe_match()関数を以下に示します。
// 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;
}
素数 61 ハッシュは、現実的な実験設定を使用して、他の多くの可能なハッシュ関数の中から選択されました。候補ハッシュ関数は、100 MB の Wikipedia ファイルからランダムに抽出された単語を繰り返し検索することによってテストされました。この単語は、1 つ、2 つ、または 3 つのランダムな文字で変化しました。この突然変異は、Wikipedia ファイル内の実際の有効な単語に対応しないことを確認するためにチェックされます。次に、変異した単語がファイルに一致するたびに、偽陽性率が記録されました。誤検知率が最小限に抑えられたハッシュ関数が全体として適切な候補となるはずです。
8 のウィンドウ (パターンの長さに応じてそれより短いウィンドウ) を使用することにより、標準のブルーム フィルターと比較して誤検知率が低くなります。より具体的には、ブルーム フィルターのNの代わりにN²ハッシュ関数が使用されます。短いパターンの場合、多くの場合、 Nは小さすぎて誤検知を制限できません。したがって、 N² の方が効果的です。また、パターンの最初の 8 バイトのどこかに文字が含まれる一致パターンはすべて拒否されますが、実際にはインデックス付きファイルのどこにも出現しませんが、標準のブルーム フィルタでは誤検出一致が発生する可能性があります。さらに、ハッシュ テーブルのインデックス付けに使用されるビット アドレス指定により、効率的なテーブル圧縮が可能になります。
インデックス作成は不可逆圧縮の一種です。インデックス作成の精度が高くなるほど、一致しないファイルをより多くスキップするため、ugrep 検索のパフォーマンスが向上します。精度が高くなるとノイズが減少します（損失が少なくなります）。ノイズが多いと、ugrep が一致しないインデックス付きファイルを検索することがあります。これらを「偽陽性一致」と呼びます。精度を高めるには、より大きなインデックス ファイルが必要になります。通常、ファイルあたりのインデックス作成ストレージは平均して 4K 以下であることが予想されます。最小値は、ファイル名と 4 バイトのインデックス ヘッダーを除いて、ファイルごとに 128 バイトのインデックス ストレージです。非常に大きなノイズの多いファイルの場合、最大はファイルあたり 64K バイトのストレージです。
ugrep --index --statsを使用してインデックス付きファイルを検索する場合、オプション--stats 、インデックスベースの検索が完了した後の検索統計を表示します。インデックス作成のノイズ (つまり、誤検知) によって多くのファイルが検索からスキップされない場合、精度が高いほどインデックス作成の効率が向上し、検索速度が向上する可能性があります。
UTF-16 および UTF-32 ファイルにもインデックスが付けられます。インデクサーは、それらを内部で UTF-8 に変換してインデックスを作成した後、UTF-8 として扱います。
ファイルのアーカイブ (zip/tar/pax/cpio) と圧縮によって、ディスク領域が節約されます。一方、アーカイブや圧縮ファイルの検索は、通常のファイルの検索よりもはるかに時間がかかります。 ugrep-indexer -z -Iを使用してアーカイブと圧縮ファイルにインデックスを作成し、 ugrep -z -I --index PATTERNを使用して検索すると、アーカイブと圧縮ファイルがスキップされる場合、検索が高速化されます。一方、アーカイブや圧縮ファイル用のインデックス ファイル エントリの追加により、ディスク ストアの要件が増加します。アーカイブおよび圧縮ファイルにバイナリが含まれている場合、オプション-Iこれらのバイナリを無視することに注意してください。
インデックス付けハッシュ テーブルを構築するためのugrep --indexの起動オーバーヘッドは、正規表現パターンによって異なります。正規表現パターンが非常に「寛容」である場合、つまり、多くの可能なパターンに一致する場合、ハッシュ テーブルを計算するためにugrep --indexの起動時間が大幅に増加します。これは、大きな Unicode 文字クラスとワイルドカードが使用されている場合、特に無制限の*と+繰り返しで発生する可能性があります。起動時間がどのように増加するかを確認するには、オプションugrep --index -r PATTERN /dev/null --stats=vm使用して、PATTERN で /dev/null を検索します。
インデックス ファイルには情報コンテンツが非常に密に含まれている必要があります。これは、私が設計して実装した ugrep 用の新しいインデックス作成アルゴリズムの場合に当てはまります。インデックス ファイルの密度が高くなるほど、元のファイル データがより正確に表現されます。そのため、インデックス ファイルの圧縮が困難または不可能になります。これは、インデックス ファイルが実際にどの程度効果的であるかを示す良い指標でもあります。
