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

• strstr, std::string::find gibi API'ler tek seferlik alt dize aramasını varsayar, ancak modern CPU'larda kısa dizeleri ve vektörleri karşılaştırmanın maliyeti düşük olduğundan SIMD yaklaşımı avantajlı olabilir
• Temel fikir, Karp-Rabin'in zayıf hash koşulunu bir vektör yüklemine dönüştürmek ve yalnızca aday konumlarda kesin alt dize karşılaştırması yapmaktır
• Genel amaçlı SIMD algoritması, adayları azaltmak için needle'ın ilk karakteri ile son karakterini paralel olarak karşılaştırır ve yalnızca eşleşme olasılığı olan konumları memcmp ile doğrular
• SSE4.1 MPSADBW ve SSE4.2 PCMPESTRM yaklaşımları da karşılaştırılır, ancak ölçüm sonuçlarına göre genel amaçlı SIMD daha tutarlı biçimde daha hızlıdır ve PCMPESTRM, MPSADBW'dan da yavaştır
• Genel amaçlı SIMD, tüm platformlarda C strstr'den daha hızlıydı; ancak girdi dizisinin dışından okuma yapabildiği için güvenli değildir ve uzunluk bilgisini önceden aldığı için karşılaştırma koşulları da tamamen aynı değildir

---

Dize aramada değişen maliyet varsayımları

• C'deki strstr, C++ std::string::find, Python dizelerindeki pos, index gibi API'ler, verilen dizide bir alt diziyi bulmaya yönelik tek seferlik arama için tasarlanmıştır
• Mevcut algoritmalar genel olarak iki büyük gruba ayrılır
  • Knuth-Morris-Pratt, Boyer Moore gibi deterministik sonlu otomat tabanlı yöntemler
  • Karp-Rabin gibi basit karşılaştırma tabanlı yöntemler
• Standart algoritmalar, bir karakter çifti karşılaştırmanın, yardımcı tabloya bakmanın ve koşullu dallanmanın ucuz; iki alt diziyi karşılaştırmanın ise pahalı olduğu varsayımına dayanır
• Modern masaüstü CPU'larda bu varsayım iyi çalışmayabilir
  • 64 bit CPU'larda 1, 2, 4 ve 8 bayt karşılaştırmanın maliyeti aynıdır
  • SIMD komutları destekleniyorsa 16, 32, 64 baytlık vektör karşılaştırmaları da tek bayt karşılaştırması kadar ucuz olabilir
  • Tablo erişimi, L1 önbellek gidiş-dönüşü düzeyinde bellek erişim maliyeti yaratır; karakter bazlı okuma da benzer maliyet taşır
  • Yanlış tahmin edilen dallanmalar yaklaşık 10~20 çevrim ceza yaratabilir
  • Karakter okuma, karşılaştırma ve koşullu dallanmadan oluşan kısa bağımlılık zinciri, CPU'nun out-of-order yürütmeden yararlanmasını zorlaştırabilir

Yaklaşım: zayıf hash yerine vektör yüklemi kullanmak

• Karp-Rabin, yalnızca hedef alt dizinin zayıf hash'i ile mevcut dize parçasının hash'i eşit olduğunda kesin karşılaştırma yapar
• SIMD yaklaşımı bu hash koşulunu bir vektör yüklemi ile değiştirir
  • Yüklem paralel hesaplanır
  • Yüklem vektöründe doğru olan her konum için kesin alt dize karşılaştırması yapılır
• Uzunluğa göre özelleştirme de performans iyileştirmesi için kullanılır
  • Genel uygulama alt dize karşılaştırması için memcmp gibi bir fonksiyon çağırır
  • Aranacak alt dizinin uzunluğu biliniyorsa, fonksiyon çağrısı belirli uzunluğa uygun birkaç CPU komutuyla, bazen tek komutla değiştirilebilir
  • Bu yöntem fonksiyon çağrısı maliyetini ve memcmp içindeki maliyeti azaltır

Algoritma 1: Genel amaçlı SIMD

• Genel amaçlı SIMD algoritması, SIMD komut kümelerinin geneline ve SWAR yaklaşımına uygulanabilir
• Temel yüklem, needle'ın ilk karakteri ile son karakterinin ikisinin de eşleşip eşleşmediğini kontrol etmektir
  • İlk karakter F yazmacına doldurulur
  • Son karakter L yazmacına doldurulur
  • Her yinelemede haystack'in mevcut ofseti i konumundan A parçası, i + k - 1 konumundan da B parçası okunur
  • F == A ve B == L hesaplanır, ardından iki sonuç birleştirilerek aday konum maskesi üretilir
  • Kesin alt dize karşılaştırması yalnızca maskede doğru olan konumlarda yapılır
• "cat" örneğinin "a_cat_tries" içinde aranmasında, ilk karakter c ve son karakter t yalnızca indeks 2'de birlikte tuttuğu için kesin karşılaştırma da sadece bir kez yapılır
• İlk ve son karakteri seçmek her zaman iyi bir tercih değildir
  • Girdi dizisi büyük ölçüde 'A' içeriyor ve needle "AjohndoeA" ise çok sayıda aday oluşabilir
  • Uygulama, son karakter yerine ilk karakterden farklı olan en uzak karakteri seçebilir
  • Needle'ın tüm karakterleri aynıysa "AAAAA" gibi desenler için özel bir prosedür kullanılabilir

Uygulamalar arasındaki farklar

• SSE ve AVX2 uygulamaları yapı olarak neredeyse aynıdır ve en az sayıda komut kullanır
  • İlk ve son karakterin zaten eşit olduğu bilindiğinden, memcmp içinde bu karakterleri yeniden karşılaştırmaya gerek yoktur
• SWAR yaklaşımı, XOR sonucunun 0 olması halinde baytların eşit olduğu özelliğinden yararlanır
  • SSE/AVX2'deki gibi ara sonuçları AND ile birleştirmek yerine OR kullanır
  • 0 bayt konumlarını bulma süreci daha fazla iş gerektirir
  • 64 bit vektörler için C++ uygulaması doğru bayt maskesini hesaplar
• AVX512F'te bayt işlemleri yoktur ve en küçük vektör öğesi 32 bit sözcük olduğundan SWAR tekniği gerekir
  • İki XOR ve bir OR, AVX512F komutlarıyla hesaplanır
  • 32 bit öğeler içinde 0 bayt içeren öğeler bulunur
  • İlgili her 32 bit öğe için 4 aday alt dize kontrol edilir
• ARM Neon 32 bit uygulaması 128 bit SIMD yazmaçları kullanır
  • Neon biriminden CPU'ya geri dönüşteki uzun gidiş-dönüş darboğaz oluşturur
  • Karşılaştırma sonuçları işlenmek üzere belleğe 64 bit sözcükler olarak yazılır
  • İç döngünün 2 kez unroll edilmesi yaklaşık 1.2 kat hız sağlar
• AArch64 uygulaması ARM Neon prosedürüyle neredeyse aynıdır, ancak SIMD yazmaç lane'lerini doğrudan okuma işlemi daha hızlıdır

Algoritma 2: SSE4.1 MPSADBW

• SSE4.1 ve AVX2'deki MPSADBW, bir yazmacın 4 baytlık alt vektörü ile başka bir yazmacın ardışık 8 adet 4 baytlık alt vektörü arasındaki Manhattan uzaklığını hesaplar
• İki alt vektör eşitse L1 uzaklığı 0 olur; bu da aday konum aramada kullanılabilir
  • Bu yaklaşım yüklem olarak ilk 4 karakterin eşitliğini kullanır
• İlk 4 karakter karşılaştırıldığı için, bu yöntem ilk ve son karakter karşılaştırmasından daha güçlü görünse de en kötü durumda ikinci dereceden karmaşıklığı önleyemez
  • Haystack "a" ile dolu, needle ise "aaaabcde" ise yüklem tüm girdi karakterlerinde doğru olur
• MPSADBW yaklaşımının bazı kısıtları vardır
  • Temelde uzunluğu 4'ten kısa alt dizeler için uygun değildir
  • Uzunluk 3 için kullanılabilir, ancak ek kod gerekir
  • SSE MPSADBW aynı anda yalnızca 8 bayt işler
  • AVX2 MPSADBW, tam 256 bit yerine 128 bit lane bazında çalıştığı için ek yükleme kodu gerektirir
  • Komut gecikmesi CPU'ya bağlı olarak 5~7 çevrim ile yüksektir, ancak throughput 1~2 çevrim olduğu için döngü unrolling ile gecikme gizlenebilir
• AVX512F'te MPSADBW yoktur; ancak 32 bit öğeler doğal olarak desteklendiğinden 4 baytlık prefix eşitliği yüklemi taklit edilebilir
  • Her yinelemede, olası 4 baytlık prefix'leri içeren 4 AVX512 vektörü oluşturulur
  • Her vektör kurulumu için 2 shift ve 1 OR gerekir
  • Karşılaştırma döngüsü karmaşıklaşır ve son öğeyi doldurmak için vektörün ötesinden 4 bayt gerekir

Algoritma 3: SSE4.2 PCMPESTRM

• SSE4.2, dize işlemleri için yapı taşları olmayı hedefleyen STNI komut kümesini tanıttı
• Intel daha sonraki işlemcilerde STNI'yi fiilen bırakmış, AVX2 sürümünü de sunmamış ve bu komutlar oldukça yavaş kalmıştır
  • 11 çevrim gecikme kabul edilemez olarak değerlendirilir
• PCMPxSTRx komutlarının, dize uzunluğunu belirleme şekline ve sonucu saklama biçimine göre dört varyantı vardır
  • Uzunluk açıkça verilebilir ya da geleneksel C dizelerinde olduğu gibi ilk 0 bayt son kabul edilebilir
  • Sonuç bit/bayt maskesi veya maskede ayarlı ilk/son bitin numarası olarak saklanabilir
• Burada range ordered karşılaştırma modu kullanılır
  • Adına rağmen, alt dize ya da yazmaç genişliğini aşan durumlarda onun prefix'ini bulur
  • Örnekte "ABCD", "ABCD_ABC_ABCD_AB" içinde aranırken suffix "AB" de eşleşme olarak değerlendirilebilir
  • Bu nedenle güvenle varsayılabilecek tek şey ilk karakter eşleşmesidir; geri kalanı memcmp ile doğrulanmalıdır

Performans ölçüm ortamı

• Farklı SIMD uygulamalarının performansı ölçüldü; kısa alt dizeler için çalışma zamanı özelleştirmesi de buna dahildi
• Karşılaştırma için C strstr de kullanıldı, ancak GNU libc içindeki std::string::find performans hatası nedeniyle x64 tablolarına eklenmedi
• Testlerde her program üç kez çalıştırıldı
• x64 test ortamı
  • Westmere i5 M540, GCC 6.2.0
  • Bulldozer FX-8150, GCC 4.8.4
  • Haswell i7 4470, GCC 5.4.1
  • Skylake i7 6700, GCC 5.4.1
  • Knights Landing 7210, GCC 5.3.0
• ARM test ortamı
  • ARMv7 Raspberry Pi 3, 32 bit kod, GCC 4.9.2
  • ARMv8 ARM Cortex A57 / AMD Opteron A1100, 64 bit kod, Clang 3.8.0

x64 sonuçları

• Genel SIMD uygulaması x64'te strstr'ye kıyasla en büyük hız artışını gösterdi
  • Westmere'de SSE2 generic 0.74589 saniye, strstr ise 0.82246 saniye
  • Haswell'de AVX2 generic 0.38653 saniye, strstr ise 0.52786 saniye
  • Skylake'te AVX2 generic 0.36309 saniye, strstr ise 0.66148 saniye
  • KNL'de AVX512F generic 1.14057 saniye, strstr ise 4.94606 saniye
• En yüksek hızlanma Westmere'de 1.10 kat, Haswell'de 1.37 kat, Skylake'te 1.82 kat, KNL'de 4.33 kat oldu
• Bulldozer'deki strstr performansı 9.37792 saniye ile çok kötüydü ve sağlam bir referans olarak kullanmak zordu
• MPSADBW yaklaşımı Skylake dışında genel olarak iyi sonuç vermedi; KNL'de özellikle kötüydü
• PCMPESTRM yaklaşımı MPSADBW'dan da daha yavaştı

ARM sonuçları

• ARMv7'de std::strstr 7.30405 saniye, std::string::find ise 4.17131 saniyeydi
• ARMv7'de ARM Neon 32 bit generic 1.29861 saniye ile std::string::find'e göre en fazla 3.1 kat daha hızlıydı
• ARMv8'de std::strstr 3.37546 saniye, std::string::find ise 1.81368 saniyeydi
• ARMv8'de AArch64 64 bit generic 0.27897 saniye ile std::string::find'e göre en fazla 6.5 kat daha hızlıydı
• ARMv8'de SWAR 64 bit generic 0.46269 saniye ile 32 bit SIMD prosedürüne yakın performans gösterdi

Sonuç ve sınırlamalar

• Genel SIMD algoritması tüm platformlarda C strstr'den daha hızlıydı
• Uygulamada, belirli CPU'da kullanılabilen en yüksek SIMD sürümünü seçmek en iyisidir
• MPSADBW, Skylake istisnası dışında iyi performans göstermedi ve Knights Landing'de çok kötüydü
• PCMPESTRM, MPSADBW'dan daha düşük performans verdi
• ARM Neon performansı, SWAR uygulaması da dahil olmak üzere iyiydi
  • SWAR sürümü string::find'den 1.7 kat daha hızlıydı
  • SIMD sürümü string::find'den 3.1 kat daha hızlıydı
• strstr ile karşılaştırma tamamen adil olmayabilir
  • strstr, uzunluğu bilinmeyen dizeleri işler
  • Bu uygulamalar uzunluğu parametre olarak alır ve bundan yararlanır
• Uygulama güvenli değildir
  • Girdi dizisinin dışındaki verileri okuyabilir
  • Dize, eşlenmemiş belleğin hemen öncesindeyse erişim ihlali oluşabilir
  • Address sanitizer da sorun bildirebilir
  • Güvenli hale getirmek mümkündü, ancak amaç bu değildi
• Tüm uygulamalar ve test programları GitHub üzerinde bulunabilir