SIMD için Uygun Alt Dize Arama Algoritması (2018)

 (0x80.pl)
1 puan yazan GN⁺ 2025-06-15 | 1 yorum | WhatsApp'ta paylaş
  • SIMD dostu bir alt dize arama algoritması hakkındadır
  • Hızlı metin arama için teknik bir yaklaşım sunar
  • Paralel işleme kullanarak mevcut yöntemlere kıyasla verimliliği artırmayı hedefler
  • Geliştiriciler ve BT uzmanları için yararlı performans ipuçları olarak öne çıkar
  • Söz konusu algoritma, modern donanım optimizasyonu ile ilişkilidir

Genel Bakış

  • Bu belge, SIMD (Single Instruction, Multiple Data) komut setine optimize edilmiş bir alt dize arama algoritmasını tanıtır
  • Metin işleme hızının önem kazandığı günümüz BT ortamında, geleneksel sıralı arama yöntemlerinin sınırlarını tamamlayan bir paralel işleme yaklaşımını ele alır
  • SIMD kullanıldığında aynı anda birden fazla veri karşılaştırılabildiği için, büyük ölçekli metin arama işlerinde önemli performans kazanımları beklenebilir

Ana Noktalar

  • SIMD algoritması, giriş metnini birden fazla parçaya ayırdıktan sonra aynı komutla birçok baytı tek seferde karşılaştırır
  • Bu yöntem sayesinde, geleneksel döngü tabanlı karşılaştırmalara göre daha hızlı ve verimli arama yapılabilir
  • Özellikle metin arama, log analizi, DNA dizileme gibi yüksek hızlı büyük veri işleme gerektiren alanlarda etkili biçimde kullanılabilir

Geliştiriciler ve Mühendisler İçin Faydalar

  • SIMD dostu algoritmalar uygulandığında, asgari kod değişikliğiyle modern CPU'ların potansiyelini en üst düzeye çıkarma olanağı elde edilir
  • Mevcut arama mantığına kıyasla hız ve verimlilik açısından avantaj sağlar
  • Çok çekirdekli ortamlarda performans ölçeklenebilirliği de oldukça yüksektir

Sonuç

  • Alt dize arama performansının kritik olduğu BT servisleri, veri analizi ve gerçek zamanlı arama motoru alanlarında SIMD tabanlı algoritmaların benimsenmesi somut performans artışlarına yol açabilir
  • Modern donanım ortamlarından yararlanmak için temel bir optimizasyon stratejisidir

İlgili okumalar

1 yorum

 
GN⁺ 2025-06-15
Hacker News yorumları

  • ripgrep'in hızlandırma yaklaşımının, Rust'un regex crate'ini kullanan AVX2 (genel amaçlı) bir yaklaşım olduğu açıklanıyor. Örneğin \w+\s+Sherlock\s+\w+ gibi bir düzenli ifadede bile yalnızca Sherlock ayrı çıkarılıp hızlıca aranabiliyor. Gerçek uygulamaya buradan bakılabilir. Bu yazıdaki algoritmadan temel farkın, needle'ın ilk/son baytı yerine arka plan dağılımını kullanarak daha seyrek görülen 2 baytla aramayı optimize eden bir sezgisel yöntem kullanması olduğu belirtiliyor. Kıyaslama sonuçları, bunun basit Two-Way yaklaşımından ya da GNU libc'nin memmem'inden çok daha hızlı olduğunu gösteriyor. prebuilt benchmark'ında ise memmem benzeri rutinlerin, needle her sabitlendiğinde durumu tekrar tekrar yeniden kurmak zorunda kaldığı için verimsiz kaldığı; bunun da API'nin bir sınırlaması olduğu özellikle vurgulanıyor

    • Baytların arka plan dağılımının nasıl bilinebileceği, bu dağılımı haystack üzerinde tek tek taramanın tersine performansı düşürmeyeceği soruluyor

  • Wasm/WASI libc için SIMD optimizasyonu denerken bu tür bir dize arama algoritmasını uygulama deneyimi paylaşılıyor. Haystack uzunluğu belliyse ve needle yeterince büyükse Quick Search ile birleştirmenin faydalı olduğu görüşüyle birlikte ilgili kod ve algoritma açıklaması bağlantısı veriliyor

  • C# tarafında da IndexOf için SIMD kullanıldığı paylaşılıyor; ayrıntılara buradan ulaşılabilir

  • Kendisinin de SIMD yaklaşımını kullanarak dize arama ve split için çeşitli algoritmaları doğrudan uyguladığını anlatıyor. tamgu'nun conversion.cxx kaynağı paylaşılıyor. Metinde anlatılandan farklı bir algoritma kullandığını belirtiyor

    • Kendi algoritmasının kısa bir özetini istemeleri üzerine, örnek olarak özgün metindeki 1. algoritmanın ilk/son karakteri, 2. algoritmanın ise ilk 4 karakteri aynı anda karşılaştırarak birden çok aday konumu denetlediği açıklaması ekleniyor

    • Birkaç yıl önce Zig'in generic SIMD'sini kullanarak bunu LZ77 window search için uyarlanmış bir sürüm olarak uygulamaya çalıştığı deneyimini paylaşıyor. İlgili içerik burada

  • Hızlı HTTP ayrıştırması için SIMD algoritmaları kullanan hparse projesini hatırlattığını söyleyen bir yorum var

  • swar algoritmasının, 1 bayt hizalı veriyi 8 baytlık birime cast ederek UB'ye (tanımsız davranış) yol açtığı belirtiliyor. Unaligned load nedeniyle performans sorunu da olabileceği söyleniyor

    • Kendisinin bu tür kodları çoğu zaman idealize edilmiş algoritma ya da okunabilirlik amaçlı sözde kod olarak gördüğünü söylüyor. memcpy kullanılmaması ve sınır kontrollerinin de hatalı olması eleştiriliyor. Haystack uzunluğunun 8'in katı olduğu varsayılıyor ya da needle boşsa unsigned integer overflow nedeniyle out-of-bounds oluşuyor; yani toplam 3 ayrı UB var. Gerçekte SIMD demo kodlarının çoğunda ilginç vektör kullanım biçimleri gösterilirken sınır koşullarının atlandığını sık gördüğünü paylaşıyor

  • libc'nin strstr'ünün yavaş olduğu zaten biliniyor ama musl'ın hızlı ve modern bir algoritma kullandığı özellikle vurgulanıyor. Şimdi geriye sadece buna bir ad vermek kaldığı, ardından smart shootout'a eklenebileceği söyleniyor. En iyi SIMD algoritmalarıyla kıyaslandığında nasıl sonuç vereceği merak ediliyor

    • Referans benchmark olarak musl'ın Two-Way yaklaşımıyla, kendisinin paylaştığı SIMD optimize libc algoritmasının karşılaştırma sonuçları veriliyor. Benchmark yöntemi ilgili kodu temel alıyor. SIMD kullanımına dair iyileştirmeler bu tabloda görülebilir. Bunu olağanüstü değil ama gayet iyi bir iyileştirme olarak dürüstçe değerlendiriyor. musl'ın sabit uzunluklu dizeler (memmem) için daha uygun olduğunu, kendisinin ise Wasm ortamında uzunluğu bilinmeyen dizeler (strstr) üzerinde çeşitli optimizasyonları daha serbest deneyebildiğini söylüyor. NUL sonlandırmalı dizelerin birçok iyi algoritmayı zorladığını da ekliyor

    • smart'a daha fazla SIMD algoritması eklenirse iyi olacağını, vakit bulursa kendisinin de denemek istediğini belirtiyor

  • Dize aramada SIMD karşılaştırmasında 2018 sürümünün eksik olup olmadığı soruluyor

  • Dize boyutuna göre SIMD yaklaşımının gerçekten verimli olduğu eşik değerin ne olduğu soruluyor. Genel olarak kısa dizelerde SIMD kurulum maliyeti (hizalama, uzunluk hesaplama vb.) yüzünden bunun basit bayt tabanlı aramadan daha yavaş olabildiği, ayrıca bunun donanım mimarisine göre ciddi biçimde değişebileceği vurgulanıyor

    • Kendi deneyiminde tam tersinin geçerli olduğunu söylüyor. Bu tür algoritmalar gereksiz kurulum olmadan neredeyse brute force çalıştığı için uzun ve tekrarlı needle'larda zaman karmaşıklığı kötüleşiyor. Buna karşılık quadratic sorunları önleyen ya da sublinear çalışan gelişmiş dize arama algoritmalarının, needle yapısını daha derin inceleyen maliyetli bir hazırlık aşaması gerektirdiğini vurguluyor

  • Python'da başka bir dili çağırmadan doğrudan SIMD kullanılabilse iyi olurdu deniyor

    • Austin'in blogundan ve derleme yazısından söz edilerek (story on vowels detection bağlantı), "ayrı bir dil çağırmadan doğrudan SIMD kullanmak" ile tam olarak ne kastedildiği soruluyor. Sonuçta Assembly de bir bakıma "başka bir dil" sayılır diye esprili bir not düşülüyor. Python ve SIMD ekosisteminin PeachPy (Python içinde x86 assembly yazma), Mojo (yeni Python tarzı dil), CPython binding'i ince olan SIMD kütüphaneleri gibi çok geniş bir yelpazeye sahip olduğu anlatılıyor. Tam olarak hangi yaklaşımın istendiği soruluyor; ASCII hedefleniyorsa StringZilla'nın find_first_of fonksiyonu da (kod) öneriliyor

    • Neden özellikle bunu Python'da doğrudan yapmak istediği sorgulanıyor. Eğer dert performans sınırıysa, yalnızca dili değiştirmekle bile 20 ila 50 kat ya da daha fazla hızlanmanın mümkün olabileceği tavsiye ediliyor