Krep - grep'ten 5 kat daha hızlı bir metin arama aracı

• Performansın kritik olduğu uygulamalar için C ile yazılmış ultra hızlı bir metin arama aracı
• Desen özellikleri ve donanıma göre en uygun algoritmayı dinamik olarak seçer
• SSE4.2/AVX2 gibi donanımları kullanarak maksimum throughput sağlar
• Büyük ölçek desteği için dosyaları parçalara bölerek çok iş parçacıklı paralel işlem uygular
• Desene göre en uygun arama algoritmasını kullanır
  • Boyer-Moore-Horspool: genel desen eşleme için uygundur
  • Knuth-Morris-Pratt (KMP) algoritması: kısa desenler için optimize edilmiştir
  • Rabin-Karp: uzun desenlerde etkilidir
  • SIMD hızlandırma: SSE4.2, AVX2 destekli donanımlarda performansı artırır
• Bellek eşlemeli dosya G/Ç kullanarak sistem çağrılarını en aza indirir ve throughput'u en üst düzeye çıkarır
• Esnek arama seçenekleri
  • Büyük/küçük harf duyarlı ve duyarsız arama
  • Dosya aramaya ek olarak doğrudan metin içinde arama yapılabilir
  • Yalnızca eşleşme sayısını yazdıran mod sunar

Kullanım

krep [OPTIONS] PATTERN [FILE]  

• Günlük dosyasında “error” arama: krep "error" system.log
• Büyük/küçük harf duyarsız, 8 iş parçacığı kullanarak arama: krep -i -t 8 "ERROR" large_logfile.log
• Eşleşme sayısını yazdırma (eşleşen satırlar yazdırılmaz): krep -c "TODO" *.c
• Dosya yerine doğrudan bir metin içinde arama: krep -s "Hello" "Hello world"

Komut satırı seçenekleri

• -i : büyük/küçük harf duyarsız arama
• -c : eşleşen satırları yazdırmadan yalnızca eşleşme sayısını yazdırır
• -t NUM : NUM adet iş parçacığı kullanır (varsayılan: 4)
• -s STRING : dosya yerine metin içinde arama
• -v : sürüm bilgisini yazdırır
• -h : yardım bilgisini yazdırır

Benchmark

• krep performansı, yaygın metin arama araçlarıyla karşılaştırıldığında oldukça yüksektir.
  • krep, 1GB metin dosyasında genel bir deseni aramak için 0.78 saniye harcadı; bu, saniyede 1,282MB anlamına gelir
  • grep aynı iş için 2.95 saniye harcadı ve saniyede 339MB hız kaydetti
  • ripgrep ise 1.48 saniye sürdü ve saniyede 676MB hız gösterdi
• → krep, grep'ten yaklaşık 3.8 kat, ripgrep'ten ise yaklaşık 1.9 kat daha hızlıdır (performans, donanım ve dosya özelliklerine göre değişebilir)

İsmin kökeni

• “krep”, İzlandaca “kreppan” sözcüğünden türetilmiştir
• “hızlıca kavramak” anlamına gelir
• Verimli desen tanımayı simgeler
• Kısa ve sade bir komut olduğu için yazması kolaydır

[clickin]

Regex desteğinden vazgeçip de ripgrep'ten yalnızca 2 kat daha hızlı oluyorsa, kullanım değeri biraz düşük kalıyor.
Ben galiba regex destekli ripgrep'i kullanmaya devam ederim.

[GN⁺]

Hacker News görüşleri

• CPU özellikleri (ör. AVX2) çalışma zamanında algılanmalı

  • ifdef, yalnızca derleme zamanında derleyicinin bunu destekleyip desteklemediğini algılar
  • Program yalnızca derleyici AVX2'yi desteklediğinde derlenir
  • Çalışma zamanında CPU'nun AVX2'yi destekleyip desteklemediği kontrol edilmeli
  • Projede "yapılandırma sırasında CPUID bayrakları ve gerçek komut yürütme testiyle algılama" ifadesi yer alıyor
  • SSE4.2 ve AVX2 komutlarından otomatik olarak yararlanabilir

• krep projesiyle ilgili blog yazısına giriş

  • Ana sayfada ripgrep'ten daha hızlı olduğu belirtiliyor
  • Tam ripgrep benchmark'ı ile karşılaştırmak istiyorum
  • madvise() ile ilgili hata oluşuyor, Makefile'daki CFLAGS'a -D_GNU_SOURCE eklemek gerekiyor

• Test vakalarının önemi

  • Çok iş parçacıklı dosya aramasında parça sınırı sorunu düşündürücü
  • Basit aramaya yeni edge case'ler ekliyor
  • Dosyaya tek bir karakter eklemek eşleşmeyi bozabilir

• Derleme sorunları çözüldükten sonraki benchmark sonuçları

  • İlk benchmark denemesinde hız yavaş
  • ripgrep, krep'ten 1,52 kat daha hızlı

• Eşleşme sıklığının yüksek olduğu benchmark denemesi

  • krep, ripgrep'ten 3,40 kat daha hızlı
  • Eşleşme sayıları arasında büyük fark var
  • krep doğru sonuçlar vermiyor olabilir

• Ek benchmark denemeleri

  • ripgrep belirli bir pattern'i bulmada daha hızlı
  • krep eşleşmeleri bulamıyor

• ripgrep'in algoritması ve bellek eşlemeli kullanım

  • ripgrep gelişmiş alt dize arama algoritmaları kullanıyor
  • Bellek eşleme ve paralel işleme kullanıyor
  • krep de paralel işleme kullanıyor; tek dosya aramasında çok iş parçacığı kullanıyor

• Benchmark sonuçlarına dair şüpheler

  • ripgrep'in 5 GB'lık bir dosyada pattern ararken 40 saniyeden fazla sürmesi tuhaf
  • OP'den benchmark'ı nasıl yeniden üretebileceğini açıklaması isteniyor

• krep adlandırmasına dair görüş

  • grep'teki "re", düzenli ifadeleri ifade eder
  • krep düzenli ifade kullanmadığı için ad yanlış olabilir