Binary search'ten daha iyisini yapabilirsiniz

(lemire.me)

1 puan yazan GN⁺ 2 시간 전 | Henüz yorum yok. | WhatsApp'ta paylaş

Sıralı dizilerde üyelik denetimi, ders kitaplarındaki binary search'ten daha hızlı hale getirilebilir; SIMD Quad, tüm ölçüm koşullarında std::binary_search'ten daha hızlıydı
SIMD Quad, 16 bit işaretsiz tamsayı sıralı dizisini 16 elemanlı bloklara böler; blok sınırlarında 4'lü enterpolasyon araması, blok içinde ise SIMD paralel karşılaştırması yapar
Modern 64 bit ARM ve x64 (Intel/AMD), tek bir komutla 8 adet 16 bit tamsayıyı karşılaştırabilir; bu da her seferinde yalnızca tek bir değeri inceleyen binary search yapısını aynen sürdürme ihtiyacını azaltır
Benchmark, boyutu 2~4096 olan 100.000 sıralı dizi ve 10 milyon üyelik sorgusuyla yapıldı; cold modu cache miss, warm modu ise cache hit durumunu simüle etti
Intel'de warm cache altında SIMD Quad, binary search'ten 2 katın üzerinde daha hızlıydı; Apple'da ise cold cache altında 2 katın üzerinde daha hızlıydı; Intel'de büyük dizilerde cold cache durumunda 4'lü yaklaşım bellek düzeyi paralelliğinden daha iyi yararlandı

Sıralı dizi üyelik denetiminin darboğazı

Sıralı bir dizide bir değerin bulunup bulunmadığını kontrol etmenin en basit yolu, değerleri tek tek tarayan doğrusal aramadır; C++'ta aynı etki std::find ile elde edilebilir
Büyük dizilerde binary search daha hızlıdır; arama aralığının ortasındaki değere göre üst ya da alt yarıyı eleyerek, değer bulunana veya aralık boşalana kadar bu işlemi tekrarlar
C++'taki std::binary_search, değerin var olup olmadığını boolean olarak döndürür
Roaring Bitmap biçimi, boyutu 1~4096 olan 16 bit tamsayı dizileri kullanır ve değer varlığı kontrolü için binary search kullanır

Modern işlemcilerin çoğunda veri paralelliği komutları olan SIMD bulunur; 64 bit ARM ve x64 (Intel/AMD), tek komutla 8 adet 16 bit tamsayıyı hedef değerle karşılaştırabilir
Bu özellik sayesinde binary search'ü 8'den küçük bloklara kadar indirmeye gerek kalmaz ve 16 veya daha fazla eleman da düşük maliyetle karşılaştırılabilir
Binary search her seferinde tek bir değeri inceler, ancak güncel işlemciler aynı anda birden fazla değeri yükleyip kontrol edebilir ve bellek düzeyi paralelliği de yüksektir
Diziyi ikiye bölmek yerine dörde ayıran 4'lü arama denenebilir; komut sayısı biraz artsa da darboğazın komut sayısı olmama ihtimali yüksektir

SIMD Quad, 16 bit işaretsiz tamsayıların sıralı dizileri için tasarlanmış bir arama algoritmasıdır; 4'lü enterpolasyon araması ile SIMD'yi birleştirir
Dizi, 16 elemanlı sabit boyutlu bloklara ayrılır; son blok istisna olabilir
Her bloğun son elemanı enterpolasyon anahtarı olarak kullanılır; hedef değerin bulunma olasılığı yüksek tek bir bloğa kadar aralık daraltılır, ardından bu bloğun 16 elemanı SIMD ile aynı anda kontrol edilir
Temel akış, blok sınırlarında enterpolasyon aramasıyla karşılaştırma sayısını azaltan ve blok içinde SIMD ile paralel karşılaştırma yapan katmanlı bir aramadır
Çalışma adımları şöyledir
- Eleman sayısı 16'dan azsa tüm dizi üzerinde basit doğrusal arama yapılır
- cardinality boyutundaki dizi, 16'şar ardışık eleman bloklarına bölünür ve toplam blok sayısı num_blocks = cardinality / 16 olur
- 16-1, 32-1 gibi konumlardaki blok son elemanları anahtar olarak kullanılır; mevcut arama aralığının 1/4 noktaları hedef pos ile karşılaştırılır ve base ayarlanır
- Enterpolasyon sonucuna göre uygun blok indeksi lo seçilir
- Geçerli bir bloksa, ARM'de NEON, x64'te SSE2 kullanılarak 16 eleman yüklenir ve hedef değerle paralel eşitlik karşılaştırması yapılır; eşleşme varsa true döndürülür
- Tam 16 elemanlı bloklara dahil olmayan kalan elemanlar doğrusal olarak aranır

Benchmark, her biri 2~4096 boyutunda olacak şekilde 100.000 adet 16 bit işaretsiz tamsayı sıralı dizi üretti
Her boyut için iki modda 10 milyon üyelik sorgusu çalıştırıldı
- cold modu: her sorgu farklı bir dizide arama yaparak cache miss durumunu simüle etti
- warm modu: sorgular dizi bazında gruplandı ve aynı dizi art arda 100 kez aranarak cache hit durumu simüle edildi
Ölçülen değer ortalama sorgu süresiydi; karşılaştırılan algoritmalar doğrusal arama (std::find), binary search (std::binary_search) ve SIMD Quad oldu
Ölçüm sistemleri Apple M4 ile Apple LLVM, ayrıca Intel Emerald Rapids işlemci ile GCC idi

Doğrusal arama ile binary search karşılaştırıldığında, dizi büyüdükçe binary search doğrusal aramayı geçti
cold cache durumunda daha fazla veri erişimi cache başarısızlıklarını artırdığı için doğrusal arama görece daha dezavantajlıydı
Binary search genel olarak doğrusal aramadan üstün geldikten sonra SIMD Quad ile karşılaştırıldı
Intel ve Apple platformlarındaki sonuçlar belirgin biçimde farklıydı
- Intel platformunda warm cache altında SIMD Quad, binary search'ten 2 katın üzerinde daha hızlıydı
- Intel platformunda cold cache altında kazanım daha küçüktü
- Apple platformunda ise tersine, cold cache altında SIMD Quad 2 katın üzerinde daha hızlıydı; warm cache altında kazanım daha sınırlıydı
Tüm durumlarda SIMD Quad, binary search'ten daha hızlıydı
SIMD kısmı özel komutlarla işi azaltır; daha az komut ve dallanma kullandığı için hızlanmayı anlamak kolaydır

SIMD optimizasyonu korunup 4'lü enterpolasyon araması standart binary search ile değiştirilen SIMD binary sürümü de karşılaştırıldı
Apple platformunda 4'lü yaklaşımın etkisi küçüktü
Intel platformunda büyük dizilerde cold cache durumunda 4'lü yaklaşım anlamlı bir optimizasyondu
Intel sunucusunda 4'lü arama, bellek düzeyi paralelliğinden daha iyi yararlandı

simd_quad fonksiyonu, uint16_t dizisini, eleman sayısı cardinality ve aranacak değer pos ile alır, boolean döndürür
gap 16'ya sabitlenmiştir; cardinality < gap ise basit bir döngüyle değer aranır
Blok arama döngüsü, n > 3 olduğu sürece 1/4, 2/4, 3/4 noktalarındaki blok son değerlerini okuyup bunların pos'tan küçük olup olmadığını karşılaştırır ve üç karşılaştırmanın toplamıyla base'i ilerletir
Sonrasında n > 1 olduğu sürece yarı eşik karşılaştırması yapılarak kalan aralık daraltılır ve en sonunda lo bloğu seçilir
Seçilen blok, ARM NEON'da vceqq_u16 veya x64 SSE2'de _mm_cmpeq_epi16 ile 16 elemanı iki grup halinde karşılaştırır
Kalan eleman aralığında, v >= pos olan noktada v == pos sonucu döndürülür; sona kadar bulunamazsa false döndürülür

Ders kitabı tarzı binary search iyi bir algoritma olsa da, gerçek performans açısından anlamlı biçimde daha hızlı hale getirilebilir
Standart algoritmalar çoğu zaman günümüz bilgisayarlarının yüksek paralellik düzeyi varsayımıyla tasarlanmamıştır
SIMD Quad, hem bellek düzeyi paralelliğinden hem de veri paralelliğinden yararlanmayı amaçlayan bir yaklaşımdır
Daha iyi algoritmalar da mümkün olabilir; daha yaratıcı yaklaşımlara ihtiyaç vardır
Kaynak kod
shotgun ile sıralı diziler arasında daha hızlı kesişimler