ugrep indexer
v1.0.0
Utilitas pengindeks ugrep mengindeks file secara rekursif untuk mempercepat pengambilan rekursif.
Isi arsip dan file terkompresi juga diindeks ketika ditentukan dengan opsi baris perintah. Hal ini menghilangkan pencarian ketika tidak ada konten yang cocok dengan pola yang ditentukan.
ugrep adalah pencari file cepat yang kompatibel dengan grep dan mendukung pencarian berbasis indeks. Pencarian berbasis indeks bisa jauh lebih cepat pada sistem file yang lambat dan ketika caching sistem file tidak efektif: jika sistem file pada drive yang dicari tidak di-cache dalam RAM, yaitu "dingin", maka pengindeksan akan mempercepat pencarian. Itu hanya mencari file-file yang mungkin cocok dengan pola regex tertentu dengan menggunakan indeks file. Indeks ini memungkinkan pemeriksaan cepat apakah ada potensi kecocokan, sehingga kami menghindari pencarian semua file.
Pencarian berbasis indeks dengan ugrep aman dan tidak pernah melewatkan file terbaru yang mungkin cocok. Jika ada file dan direktori yang ditambahkan atau diubah setelah pengindeksan, maka pencarian akan selalu mencari penambahan dan perubahan yang dilakukan pada sistem file dengan membandingkan stempel waktu file dan direktori dengan stempel waktu pengindeksan.
Ketika banyak file ditambahkan atau diubah setelah pengindeksan, maka kita mungkin ingin mengindeks ulang untuk memperbarui indeks. Pengindeksan ulang bersifat bertahap, sehingga tidak memerlukan waktu sebanyak proses pengindeksan awal.
Contoh umum namun kecil dari pencarian berbasis indeks, misalnya pada repositori ugrep v3.12.6 yang ditempatkan pada drive terpisah:
$ 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
Pencarian normal pada sistem file dingin tanpa pengindeksan memerlukan waktu 1,02 detik setelah melepas drive dan memasangnya kembali untuk menghapus cache FS guna mencatat efek pengindeksan:
$ 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 membutuhkan waktu lebih lama yaitu 1,18 detik untuk pencarian dingin yang sama (ripgrep melewatkan file biner secara default, jadi opsi -I tidak ditentukan):
$ time rg -l 'std::chrono'
src/ugrep.cpp
1.18 real 0.01 user 0.06 sys
Sebaliknya, dengan pengindeksan, pencarian sistem file dingin hanya membutuhkan 0,0487 detik dengan ugrep, yang 21 kali lebih cepat, setelah melepas drive dan memasangnya lagi untuk menghapus cache FS guna mencatat efek pengindeksan:
$ 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
Selalu ada beberapa variasi dalam waktu yang berlalu dengan 0,0487 detik merupakan waktu terbaik dari empat proses pencarian yang menghasilkan rentang waktu pencarian dari 0,0487 (peningkatan kecepatan 21x) hingga 0,0983 detik (peningkatan kecepatan 10x).
Peningkatan kecepatan secara umum mungkin jauh lebih tinggi dibandingkan dengan demo kecil ini, tergantung pada beberapa faktor, ukuran file yang diindeks, kecepatan baca sistem file dan asumsi sebagian besar file dingin.
Algoritme pengindeksan yang saya rancang terbukti monoton : akurasi yang lebih tinggi menjamin peningkatan kinerja pencarian dengan mengurangi tingkat positif palsu, tetapi juga meningkatkan overhead penyimpanan indeks. Demikian pula, akurasi yang lebih rendah menurunkan kinerja pencarian, namun juga mengurangi overhead penyimpanan indeks. Oleh karena itu, saya menamai pengindeks saya dengan pengindeks monotonik .
Jika ruang penyimpanan file sangat mahal, maka kita dapat mengurangi overhead penyimpanan indeks dengan menentukan akurasi pengindeksan yang lebih rendah.
Mengindeks contoh dari atas dengan level 0 (opsi -0 ) mengurangi overhead penyimpanan pengindeksan sebanyak 8,6 kali, dari 4256 byte per file menjadi 490 byte per file:
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
Pencarian yang diindeks masih jauh lebih cepat 12x dibandingkan yang tidak diindeks untuk contoh ini, dengan 16 file yang benar-benar dicari (15 positif palsu):
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
Pola regex yang lebih kompleks dari contoh ini mungkin memiliki tingkat positif palsu yang lebih tinggi secara alami, yaitu tingkat file yang dianggap mungkin cocok padahal sebenarnya tidak. Tingkat positif palsu yang lebih tinggi dapat mengurangi kecepatan pencarian ketika tingkat tersebut cukup besar untuk memberikan dampak.
Tabel berikut menunjukkan bagaimana akurasi pengindeksan memengaruhi penyimpanan pengindeksan dan rata-rata gangguan per file yang diindeks. Kolom paling kanan menunjukkan kecepatan pencarian dan tingkat positif palsu untuk ugrep --index -I -l 'std::chrono' :
| menurut. | penyimpanan indeks (KB) | kebisingan rata-rata | positif palsu | waktu pencarian |
|---|---|---|---|---|
-0 | 631 | 42% | 15 | 0,0722 |
-1 | 1276 | 39% | 1 | 0,0506 |
-2 | 1576 | 36% | 0 | 0,0487 |
-3 | 2692 | 31% | 0 | unch |
-4 | 2966 | 28% | 0 | unch |
-5 | 4953 | 23% | 0 | unch |
-6 | 5474 | 19% | 0 | unch |
-7 | 9513 | 15% | 0 | unch |
-8 | 10889 | 11% | 0 | unch |
-9 | 13388 | 7% | 0 | unch |
Jika regex yang ditentukan cocok dengan lebih banyak kemungkinan pola, misalnya dengan penelusuran ugrep --index -I -l '(todo|TODO)[: ]' , maka kita dapat mengamati tingkat positif palsu yang lebih tinggi di antara 1.317 file yang dicari, menghasilkan waktu pencarian yang sedikit lebih lama:
| menurut. | positif palsu | waktu pencarian |
|---|---|---|
-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 | unch |
-7 | 0 | unch |
-8 | 0 | unch |
-9 | 0 | unch |
Akurasi -4 adalah defaultnya (dari -5 sebelumnya di rilis lama), yang cenderung bekerja sangat baik untuk mencari dengan pola regex dengan kompleksitas sedang.
Satu kata peringatan. Selalu ada sedikit biaya tambahan untuk memeriksa indeks. Ini berarti bahwa jika semua file sudah di-cache di RAM, karena file baru saja dicari atau dibaca, maka pengindeksan tentu saja tidak akan mempercepat pencarian. Dalam hal ini, pencarian yang tidak diindeks mungkin lebih cepat. Selain itu, pencarian berbasis indeks memiliki waktu permulaan yang lebih lama. Waktu mulai ini bertambah ketika kelas karakter Unicode dan wildcard digunakan yang harus dikonversi ke tabel hash.
Ringkasnya, pencarian berbasis indeks paling efektif ketika mencari banyak file dingin dan ketika pola regex tidak terlalu cocok, misalnya kita ingin membatasi penggunaan pengulangan tak terbatas * dan + dan membatasi penggunaan kelas karakter Unicode ketika mungkin. Hal ini mengurangi waktu mulai ugrep dan membatasi tingkat kecocokan pola positif palsu (lihat juga Tanya Jawab di bawah).
Mengindeks semua file non-biner yang menunjukkan kemajuan secara rekursif dan bertahap:
ugrep-indexer -I -v
Secara rekursif dan bertahap mengindeks semua file non-biner, termasuk file non-biner yang disimpan dalam arsip dan file terkompresi, menunjukkan kemajuan:
ugrep-indexer -z -I -v
Secara bertahap mengindeks semua file non-biner, termasuk arsip dan file terkompresi, menunjukkan kemajuan, mengikuti tautan simbolik ke file (tetapi tidak ke direktori), tetapi jangan mengindeks file dan direktori yang cocok dengan gumpalan di .gitignore:
ugrep-indexer -z -I -v -S -X
Paksa pengindeksan ulang semua file non-biner, termasuk arsip dan file terkompresi, ikuti tautan simbolis ke file (tetapi tidak ke direktori), tetapi jangan mengindeks file dan direktori yang cocok dengan gumpalan di .gitignore:
ugrep-indexer -f -z -I -v -S -X
Sama, tetapi kurangi penyimpanan file indeks ke minimum dengan mengurangi akurasi pengindeksan dari 5 (default) menjadi 0:
ugrep-indexer -f -0 -z -I -v -S -X
Tingkatkan kinerja pencarian dengan meningkatkan akurasi pengindeksan dari 5 (default) menjadi 7 dengan mengorbankan file indeks yang lebih besar:
ugrep-indexer -f7zIvSX
Hapus semua file indeks ._UG#_Store yang tersembunyi secara rekursif untuk memulihkan pohon direktori menjadi tidak terindeks:
ugrep-indexer -d
Konfigurasikan dan kompilasi dengan:
./build.sh
Jika diinginkan tetapi tidak diperlukan, instal dengan:
sudo make install
Tambahkan opsi untuk membuat satu file indeks, misalnya ditentukan secara eksplisit ke ugrep. Hal ini selanjutnya dapat meningkatkan kecepatan pencarian yang diindeks jika file indeks terletak pada sistem file yang cepat. Jika tidak, jangan mengharapkan banyak perbaikan atau bahkan kemungkinan perlambatan, karena satu file indeks tidak dapat dicari secara bersamaan dan lebih banyak entri indeks akan diperiksa padahal sebenarnya direktori dilewati (melewatkan indeksnya juga). Eksperimen akan membuktikannya. Peringatan penting dari pendekatan ini adalah bahwa pencarian berbasis indeks dengan ugrep --index tidak lagi aman: file baru dan yang dimodifikasi yang belum diindeks tidak akan dicari.
Setiap filter N-gram Bloom memiliki "bit tier" sendiri di tabel hash untuk menghindari konflik hash. Misalnya 2 gram tidak berbagi bit apa pun dengan 3 gram. Hal ini memastikan bahwa kita tidak pernah mendapatkan hasil positif palsu dengan pencocokan karakter yang salah yang sebenarnya bukan bagian dari pola. Namun, ruang bit 1 gram (karakter tunggal) kecil (paling banyak 256 bit). Oleh karena itu, kami membuang beberapa bit ketika tabel hash lebih besar. Pendekatan yang mungkin dilakukan untuk mengurangi pemborosan adalah dengan menggabungkan 1 gram dengan 2 gram untuk berbagi ruang bit yang sama. Hal ini mudah dilakukan jika kita menganggap 1 gram sama dengan 2 gram dengan karakter kedua disetel ke (NUL). Kita dapat menurunkan tingkat positif palsu dengan hash 2 gram kedua berdasarkan metode hash yang berbeda. Atau kita dapat memperluas "tingkatan bit" dari 8 menjadi 9 untuk menyimpan 9 gram. Hal ini akan meningkatkan akurasi pengindeksan untuk pola yang lebih panjang (9 atau lebih) tanpa biaya tambahan. Di sisi lain, perubahan tersebut dapat menyebabkan lebih banyak kesalahan positif ketika karakter yang salah cocok dan bukan bagian dari pola; kita kehilangan keunggulan akurasi 1 gram yang sempurna.
Pengindeksan menambahkan file indeks tersembunyi ._UG#_Store ke setiap direktori yang diindeks. File yang diindeks dipindai (tidak pernah diubah!) oleh pengindeks ugrep untuk menghasilkan file indeks.
Ukuran file indeks bergantung pada akurasi yang ditentukan, dengan -0 terendah (file indeks kecil) dan -9 tertinggi (file indeks besar). Akurasi defaultnya adalah -4 . Lihat Q berikutnya untuk mengetahui detail tentang dampak akurasi pada ukuran pengindeksan versus kecepatan pencarian.
Pengindeksan tidak pernah mengikuti tautan simbolis ke direktori , karena direktori yang terhubung secara simbolis dapat berlokasi di mana saja dalam sistem file, atau di sistem file lain, di mana kita tidak ingin menambahkan file indeks. Anda masih dapat mengindeks tautan simbolis ke file dengan opsi pengindeks ugrep -S .
Opsi -v ( --verbose ) menampilkan kemajuan pengindeksan dan "kebisingan" dari setiap file yang diindeks. Kebisingan adalah ukuran entropi atau keacakan dalam masukan. Tingkat kebisingan yang lebih tinggi berarti pengindeksan kurang akurat dalam merepresentasikan konten file. Misalnya, file besar dengan data acak sulit diindeks secara akurat dan akan memiliki tingkat noise yang tinggi.
Kompleksitas pengindeksan bersifat linier dalam ukuran file tertentu yang akan diindeks. Dalam praktiknya, ini bukanlah proses yang cepat, pencarian tidak secepat itu, dan mungkin memerlukan waktu untuk menyelesaikan pengindeksan penuh melewati pohon direktori besar. Saat pengindeksan selesai, ugrep-indexer menampilkan hasil pengindeksan. Ukuran total indeks yang ditambahkan dan gangguan pengindeksan rata-rata juga dilaporkan.
Memindai file untuk mengindeks menghasilkan tabel hash pengindeksan 64KB. Kemudian, pengindeks ugrep membagi dua tabel dengan kompresi bit menggunakan bitwise-dan selama akurasi target tidak terlampaui. Halving dimungkinkan oleh fakta bahwa tabel mengkodekan hash untuk 8 jendela dengan offset dari awal pola, sesuai dengan 8 bit per sel tabel hashing indeks. Menggabungkan dua bagian tabel dapat mengubah beberapa bit menjadi nol dari satu, yang dapat menyebabkan kecocokan positif palsu. Ini membuktikan monotonisitas pengindeks. Nilai hash nol bit menunjukkan kemungkinan kecocokan.
Pengindeks ugrep mendeteksi "file biner", yang dapat diabaikan dan tidak diindeks dengan opsi pengindeks ugrep -I ( --ignore-binary ). Ini berguna ketika mencari dengan opsi ugrep -I ( --ignore-binary ) untuk mengabaikan file biner, yang merupakan skenario umum.
Pengindeks ugrep mematuhi pengecualian file .gitignore ketika ditentukan dengan opsi -X ( --ignore-files ). File dan direktori yang diabaikan tidak akan diindeks untuk menghemat ruang sistem file. Ini berfungsi dengan baik ketika mencari file dengan opsi ugrep --ignore-files .
Pengindeksan dapat dibatalkan, misalnya dengan CTRL-C, yang tidak akan mengakibatkan hilangnya kemampuan pencarian dengan ugrep, namun akan membuat struktur direktori hanya terindeks sebagian.
Opsi -c memeriksa indeks untuk referensi basi dan file serta direktori yang tidak diindeks.
Indeks dihapus dengan opsi ugrep-indexer -d .
Pengindeks ugrep telah diuji secara ekstensif dengan membandingkan hasil pencarian ugrep --index dengan hasil pencarian ugrep yang "lambat" yang tidak diindeks pada ribuan file dengan ribuan pola pencarian acak.
Pencarian berbasis indeks berfungsi dengan semua opsi ugrep kecuali dengan opsi -v ( --invert-match ), --filter , -P ( --perl-regexp ) dan -Z ( --fuzzy ). Opsi -c ( --count ) dengan --index secara otomatis menyetel --min-count=1 untuk melewati semua file yang tidak cocok.
Jika ada file atau direktori yang diperbarui, ditambahkan atau dihapus setelah pengindeksan, maka ugrep --index akan selalu mencari file dan direktori ini ketika ada di jalur pencarian rekursif. Anda dapat menjalankan ugrep-indexer lagi untuk memperbarui semua indeks secara bertahap.
Pola regex dikonversi secara internal oleh ugrep dengan opsi --index menjadi bentuk tabel hash hingga 16 byte pertama dari pola regex yang ditentukan, mungkin lebih pendek untuk mengurangi waktu konstruksi ketika pola regex rumit. Oleh karena itu, 8 hingga 16 karakter pertama dari pola regex yang akan dicari adalah yang paling penting dan tidak boleh terlalu cocok untuk membatasi apa yang disebut pencocokan positif palsu yang dapat memperlambat pencarian.
Di ugrep, pola regex diubah menjadi DFA. Otomatisasi terbatas hash pengindeksan (HFA) dibangun di atas DFA untuk secara kompak mewakili tabel hash sebagai transisi keadaan dengan tepi berlabel. HFA ini terdiri dari hingga delapan lapisan, masing-masing digeser satu byte untuk mewakili jendela 8-byte berikutnya pada pola tersebut. Setiap lapisan HFA mengkodekan hash indeks untuk bagian pola tersebut. Fungsi hash indeks yang dipilih adalah "aditif", artinya byte berikutnya ditambahkan ketika di-hash dengan hash sebelumnya. Hal ini sangat penting karena secara signifikan mengurangi biaya overhead konstruksi HFA. Sekarang kita dapat mengkodekan transisi berlabel HFA ke status sebagai beberapa sisi dengan rentang nilai hash 16-bit, bukan sekumpulan sisi tunggal yang masing-masing memiliki nilai hash tersendiri. Untuk tujuan ini, saya menggunakan perpustakaan rentang terbuka reflex::ORanges<T> yang berasal dari std::set<T> .
Fungsi string tunggal maybe_match() yang sangat sederhana dengan fungsi hash indeks 61 utama diberikan di bawah ini untuk mendemonstrasikan pencarian string tunggal berbasis indeks:
// 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;
}
Hash 61 utama dipilih di antara banyak kemungkinan fungsi hashing lainnya menggunakan pengaturan eksperimental yang realistis. Fungsi hashing kandidat diuji dengan berulang kali mencari kata yang diambil secara acak dari file Wikipedia berukuran 100 MB. Kata itu bermutasi dengan satu, dua atau tiga huruf acak. Mutasi ini diperiksa untuk memastikan tidak sesuai dengan kata valid sebenarnya di berkas Wikipedia. Kemudian tingkat positif palsu dicatat setiap kali kata yang bermutasi cocok dengan file tersebut. Fungsi hash dengan tingkat positif palsu yang minimal seharusnya menjadi kandidat yang baik secara keseluruhan.
Dengan menggunakan jendela 8 (atau lebih pendek tergantung pada panjang pola) tingkat positif palsu lebih rendah dibandingkan dengan filter Bloom standar. Lebih khusus lagi, fungsi hash N² digunakan sebagai pengganti N dalam filter Bloom. Untuk pola yang lebih pendek, N sering kali terlalu kecil untuk membatasi hasil positif palsu. Oleh karena itu, N² lebih efektif. Ini juga menolak pola apa pun dari pencocokan yang memiliki karakter di mana pun dalam 8 byte pertama pola tersebut tidak benar-benar muncul di mana pun dalam file yang diindeks, sedangkan filter Bloom standar mungkin memiliki pencocokan positif palsu. Selain itu, pengalamatan bit yang digunakan untuk mengindeks tabel hash memungkinkan kompresi tabel yang efisien.
Pengindeksan adalah bentuk kompresi lossy. Semakin tinggi akurasi pengindeksan, seharusnya semakin cepat kinerja pencarian ugrep dengan melewatkan lebih banyak file yang tidak cocok. Akurasi yang lebih tinggi mengurangi kebisingan (lebih sedikit kerugian). Tingkat kebisingan yang tinggi menyebabkan ugrep terkadang mencari file yang diindeks yang tidak cocok. Kami menyebutnya "kecocokan positif palsu". Akurasi yang lebih tinggi memerlukan file indeks yang lebih besar. Biasanya kami mengharapkan rata-rata penyimpanan pengindeksan 4K atau kurang per file. Penyimpanan indeks minimumnya adalah 128 byte per file, tidak termasuk nama file dan header indeks 4 byte. Penyimpanan maksimumnya adalah 64K byte per file untuk file berisik yang sangat besar.
Saat mencari file yang diindeks dengan ugrep --index --stats , opsi --stats menampilkan statistik pencarian setelah pencarian berbasis pengindeksan selesai. Ketika banyak file tidak dilewati dari pencarian karena gangguan pengindeksan (yaitu positif palsu), maka akurasi yang lebih tinggi membantu meningkatkan efektivitas pengindeksan, yang dapat mempercepat pencarian.
File UTF-16 dan UTF-32 juga diindeks. Pengindeks memperlakukannya sebagai UTF-8 setelah mengonversinya secara internal menjadi UTF-8 untuk diindeks.
Ruang disk dihemat dengan pengarsipan (zip/tar/pax/cpio) dan mengompresi file. Di sisi lain, pencarian arsip dan file terkompresi jauh lebih lambat dibandingkan pencarian file biasa. Mengindeks arsip dan file terkompresi dengan ugrep-indexer -z -I dan mencarinya dengan ugrep -z -I --index PATTERN mempercepat pencarian, yaitu ketika arsip dan file terkompresi dilewati. Di sisi lain, persyaratan penyimpanan disk akan meningkat dengan penambahan entri file indeks untuk arsip dan file terkompresi. Perhatikan bahwa ketika arsip dan file terkompresi berisi biner, opsi -I mengabaikan biner ini.
Overhead awal ugrep --index untuk membuat tabel hash pengindeksan bergantung pada pola regex. Jika pola regex sangat "permisif", yaitu cocok dengan banyak kemungkinan pola, maka waktu mulai ugrep --index meningkat secara signifikan untuk menghitung tabel hash. Hal ini mungkin terjadi ketika kelas karakter Unicode dan wildcard yang besar digunakan, terutama dengan pengulangan * dan + yang tidak terbatas. Untuk mengetahui peningkatan waktu start-up, gunakan opsi ugrep --index -r PATTERN /dev/null --stats=vm untuk mencari /dev/null dengan POLA Anda.
File indeks harus sangat padat dalam konten informasi dan itulah yang terjadi dengan algoritma pengindeksan baru untuk ugrep yang saya rancang dan implementasikan. Semakin padat suatu file indeks, semakin kompak file tersebut secara akurat mewakili data file asli. Hal ini membuat kompresi file indeks menjadi sulit atau tidak mungkin. Ini juga merupakan indikator yang baik tentang seberapa efektif file indeks dalam praktiknya.
