Krep - Alat pencarian string 5x lebih cepat daripada grep

• Alat pencarian string super cepat yang ditulis dalam C untuk aplikasi yang mengutamakan performa
• Memilih algoritme optimal secara dinamis berdasarkan karakteristik pola dan perangkat keras
• Memanfaatkan perangkat keras seperti SSE4.2/AVX2 untuk memberikan throughput maksimum
• Untuk mendukung skala besar, file dibagi menjadi chunk dan diproses secara paralel dengan multithreading
• Menggunakan algoritme pencarian yang paling sesuai tergantung pada polanya
  • Boyer-Moore-Horspool: cocok untuk pencocokan pola umum
  • Algoritme Knuth-Morris-Pratt (KMP): dioptimalkan untuk pola pendek
  • Rabin-Karp: efektif untuk pola panjang
  • Akselerasi SIMD: peningkatan performa pada perangkat keras yang mendukung SSE4.2, AVX2
• Menggunakan memory-mapped file I/O untuk meminimalkan system call dan memaksimalkan throughput
• Opsi pencarian yang fleksibel
  • Pencarian case-sensitive dan case-insensitive
  • Selain mencari di file, bisa langsung mencari dalam string
  • Menyediakan mode yang hanya menampilkan jumlah kecocokan

Cara penggunaan

krep [OPTIONS] PATTERN [FILE]  

• Mencari “error” di file log: krep "error" system.log
• Mencari tanpa membedakan huruf besar/kecil dengan 8 thread: krep -i -t 8 "ERROR" large_logfile.log
• Menampilkan jumlah kecocokan (tanpa menampilkan baris yang cocok): krep -c "TODO" *.c
• Mencari langsung dalam string, bukan file: krep -s "Hello" "Hello world"

Opsi command line

• -i : pencarian tanpa membedakan huruf besar/kecil
• -c : hanya menampilkan jumlah kecocokan tanpa menampilkan baris yang cocok
• -t NUM : menggunakan NUM thread (default: 4)
• -s STRING : mencari dalam string, bukan file
• -v : menampilkan informasi versi
• -h : menampilkan bantuan

Benchmark

• Performa krep sangat unggul dibandingkan alat pencarian string pada umumnya.
  • krep membutuhkan 0,78 detik untuk mencari pola umum pada file teks 1GB, yang berarti kecepatan 1.282MB per detik
  • grep membutuhkan 2,95 detik untuk tugas yang sama, dengan kecepatan 339MB per detik
  • ripgrep membutuhkan 1,48 detik, dengan kecepatan 676MB per detik
• → krep sekitar 3,8x lebih cepat daripada grep, dan sekitar 1,9x lebih cepat daripada ripgrep (performa dapat berbeda tergantung perangkat keras dan karakteristik file)

Asal nama

• “krep” berasal dari kata dalam bahasa Islandia, “kreppan”
• Artinya “mencengkeram dengan cepat”
• Melambangkan pengenalan pola yang efisien
• Nama perintahnya singkat dan ringkas sehingga mudah diketik

[clickin]

Kalau harus mengorbankan dukungan regex tetapi hanya 2 kali lebih cepat daripada ripgrep, kegunaannya jadi agak terbatas juga.
Saya sepertinya akan tetap memakai ripgrep yang mendukung regex.

[GN⁺]

Opini Hacker News

• Fitur CPU (misalnya AVX2) harus dideteksi saat runtime

  • ifdef hanya mendeteksi pada build time apakah compiler mendukungnya
  • Program hanya dikompilasi ketika compiler mendukung AVX2
  • Perlu memeriksa saat runtime apakah CPU mendukung AVX2
  • Ada bagian di proyek yang menyebut "deteksi pada waktu konfigurasi melalui flag CPUID dan uji eksekusi instruksi yang sebenarnya"
  • Dapat memanfaatkan instruksi SSE4.2 dan AVX2 secara otomatis

• Pengenalan posting blog tentang proyek krep

  • Di halaman berandanya dikatakan lebih cepat daripada ripgrep
  • Ingin membandingkannya dengan keseluruhan benchmark ripgrep
  • Terjadi error terkait madvise(), perlu menambahkan -D_GNU_SOURCE ke CFLAGS di Makefile

• Pentingnya test case

  • Masalah batas chunk pada pencarian file multithread cukup mengkhawatirkan
  • Memperkenalkan edge case baru pada pencarian sederhana
  • Menambahkan satu karakter ke file bisa membuat kecocokan rusak

• Hasil benchmark setelah masalah build diperbaiki

  • Pada percobaan benchmark pertama, kecepatannya lebih lambat
  • ripgrep 1,52 kali lebih cepat daripada krep

• Percobaan benchmark dengan frekuensi kecocokan tinggi

  • krep 3,40 kali lebih cepat daripada ripgrep
  • Jumlah kecocokan sangat berbeda
  • krep mungkin tidak memberikan hasil yang akurat

• Percobaan benchmark tambahan

  • ripgrep lebih cepat dalam mencari pola tertentu
  • krep gagal menemukan kecocokan

• Algoritma ripgrep dan penggunaan memory map

  • ripgrep menggunakan algoritma pencarian substring tingkat lanjut
  • Menggunakan memory map dan pemrosesan paralel
  • krep juga menggunakan pemrosesan paralel, memakai multithread saat mencari dalam satu file

• Keraguan terhadap hasil benchmark

  • Aneh jika ripgrep membutuhkan lebih dari 40 detik untuk mencari pola di file 5GB
  • Meminta OP menjelaskan cara mereproduksi benchmark tersebut

• Pendapat tentang nama krep

  • "re" pada grep berarti regular expression
  • Karena krep tidak menggunakan regular expression, namanya mungkin kurang tepat