Static Search Trees: İkili Aramadan 40 Kat Daha Hızlı

 (curiouscoding.nl)
22 puan yazan GN⁺ 2025-01-02 | 2 yorum | WhatsApp'ta paylaş
  • Sıralı verilerde yüksek hızlı arama yapmak için "S+ tree" adlı statik bir arama ağacı uygulanıyor
  • Algorithmica gönderisinde önerilen kod başlangıç noktası alınarak optimize ediliyor; önerilen ek fikirler ve iyileştirmeler de kodlanıyor
  • Assembly kodu analiz edildikten sonra mümkün olan tüm komutlar optimize edilerek performans en üst düzeye çıkarılıyor
  • Birden fazla sorguyu paralel işleyerek throughput'u artıran batching uygulanıyor
  • Amaç, S+ tree ile sıralı verilerde yüksek throughput'u korurken sorguları verimli biçimde yürütmek

1. Giriş ve motivasyon

  • Problem tanımı:

    • Girdi: sıralı 32 bit işaretsiz tamsayı listesi vals: Vec<u32>
    • Çıktı: belirli bir sorgu (q) değerine eşit veya ondan büyük olan değeri döndüren, mümkün olduğunca küçük boyutlu bir veri yapısı
    • Metrik: saniye başına işlenebilen bağımsız sorgu sayısı

  • Amaç:

    • Biyoinformatikte verimli veri yapıları kurmak, özellikle DNA dizi indeksleme için suffix array aramasını hızlandırmak
    • CPU performansı ve SIMD komutlarından yararlanarak performansı en üst düzeye çıkarmak

  • Önerilen kaynaklar:

    • İkili arama ve dizi yerleşimi araştırması (“Array Layouts for Comparison-Based Searching”)
    • S+ tree ve statik B-tree tanıtım kaynakları

2. S+ tree ve optimizasyon

2.1 İkili arama ve Eytzinger yerleşimi

  • Rust standart kütüphanesindeki ikili arama önbellek açısından verimsizdir ve veri boyutu arttıkça performansı düşer
  • Eytzinger yerleşimi:
    • İkili arama ağacını dizi biçiminde saklayarak önbellek kullanımını en üst düzeye çıkarır
    • Performans: L3 önbelleğini aşan verilerde ikili aramadan en fazla 4 kat daha hızlıdır

2.2 S+ tree kavramı

  • S-tree:
    • Düğüm başına 15 sıralı değer içeren 16 dallı ağaç yapısı
    • B-tree'den daha verimlidir ve Eytzinger yerleşiminden daha iyi sıkıştırılabilir
  • S+ tree:
    • Tüm verileri yaprak düğümlerde saklar ve üst düğümlerde kopyalarını tutar
    • Basit arama ve verimli yapı sağlar

2.3 find fonksiyonunun optimizasyonu

  • Temel doğrusal arama:
    • Veriyi dolaşarak koşulu sağlayan değeri döndürür; verimsizdir
  • Otomatik vektörleştirme:
    • Dalsız koda dönüştürülür; SIMD komutları kullanılarak performans 2 kat artar
  • Elle SIMD uygulaması:
    • SIMD komutları elle kullanılarak optimize edilir, 5 komutla performans en üst düzeye çıkarılır

3. Batching ve prefetching

3.1 Batching

  • Birden fazla sorgu paralel işlenerek bellek bekleme süresi dengelenir
  • Batch boyutu artırıldıkça throughput iyileşir; en büyük kazanım batch boyutu 16 civarında doygunluğa ulaşır

3.2 Prefetching

  • Sonraki düğümü önceden belleğe alarak L3 önbelleğini aşan verilerde performansı artırır
  • Batching ile birleştirildiğinde işlem süresi 45ns/query'den 30ns/query'ye düşer

4. Veri yerleşimi ve yapı optimizasyonu

4.1 Düğüm boyutunu değiştirme

  • Düğüm başına değer sayısı 15'e düşürülerek çarpma işlemleri basitleştirilir ve önbellek verimliliği artar
  • L3 önbellek içindeki veriler için küçük bir performans artışı sağlar

4.2 Bellek yerleşimini değiştirme

  • Yerleşimi ters sırada saklama veya padding'i en aza indiren düzenler denenir
  • Ters sıra ve azaltılmış padding yerleşimlerinin ikisi de performansı belirgin biçimde etkilemez

5. Veri bölümlendirme

5.1 Önek tabanlı bölümlendirme

  • Veriler, üst bitlerine göre parçalara ayrılır
  • Küçük veri kümelerinde performansı artırır, ancak bellek ek yükü oluşturur

5.2 Sıkıştırılmış alt ağaçlar

  • Her alt ağaç paketlenerek alan verimliliği artırılır
  • Parça boyutlarının izlenmesi gerekir, sorgu hızı ise bir miktar düşer

6. Çok iş parçacıklı karşılaştırma

  • 6 iş parçacığı kullanıldığında sorgu süresi 27ns → 7ns olur
  • Darboğaz RAM bant genişliği sınırıdır

7. Sonuç ve gelecekteki çalışmalar

  • İkili aramaya kıyasla 40 katın üzerinde performans artışı (1150ns/query → 27ns/query)
  • Gelecek çalışmalar:
    • Veri dengesini optimize etmek ve RAM erişimini azaltmak
    • Aralık sorguları ve sıralama sorgularını işlemek
    • Suffix array aramasıyla entegrasyon

İlgili okumalar

2 yorum

 
beenzinozino 2025-01-04

Vay be... Çeşitli dillerin yerleşik kütüphanelerine uygulanırsa etkisinin oldukça büyük olacağını düşünüyorum.
 
GN⁺ 2025-01-02
Hacker News görüşleri

  • Rust'ın algoritmalarla ilgili düşük seviyeli içeriklerde giderek daha fazla kullanıldığını gözlemliyorum. Eskiden ağırlıkla C(++) veya bilimsel sözde kodla yazılmış içerikler olurdu. Rust kullanımının artmasını olumlu buluyorum

    • Rust'ı iyi bilmiyorum ama Rust ile yazılmış içeriği anlayabildim. Bu, C ile yazılmış algoritma örneklerini bir Rust programcısının anlayabilmesine benziyor
    • Rust'ın standartlaşmasını tercih ederim; buna ek olarak Zig'in de birlikte kullanılması iyi olur diye düşünüyorum

  • Sorguları partilere ayırma yöntemi incelenmemiş. Asıl maliyet, önbellek dışındaki tablolarda arama yapmak

    • Yeterince çok sorgu olduğunda, ağacın birden fazla seviyesini tek seferde çözmek mümkün olabilir
    • Sonuçları doğru çıktı sırasına göre sıralama sorunu ortaya çıkabilir

  • int32 değerlerinin sayısı çok fazla değil ve tam bit kümesi 512MB. Genel amaçlı veri yapısı olarak Roaring Bitmaps öneririm

    • Yalnızca basit arama gerekiyorsa, minimal perfect hash function değerlendirmeye değer olabilir

  • Rust'ta düşük seviyeli verimliliği artırma yolları beni şaşırttı. Bunu C++ uygulamasıyla karşılaştırmak isterdim

  • Eytzinger ağacının avantajı, düğüm indekslerini orta sıralı dolaşım konumuna dönüştüren bir formül olması

    • Temel anahtar deposu sıralı bir anahtar kümesiyse faydalı
    • Eytzinger kullanıldığında döngünün birden fazla yinelemesi önceden tahmin edilebilir

  • 4GB bellekte u32 ararken yaklaşık 27ns ek yük oluşması şaşırtıcı

    • Parti boyutu 8 iken optimizasyonun nasıl ilerlediğini merak ediyorum
    • Çok iş parçacıklı sonuçlar da ilginç. 1 iş parçacığından 6 iş parçacığına geçildiğinde ek yük 4 kat iyileşiyor

  • Rust ve C++ hakkında çok konuşuluyor ama ben Common Lisp'te SIMD'yi koruyarak bunu nasıl uygulayabileceğimi düşünüyorum

  • Düşük seviyeli optimizasyonlarla ilgili bir yazı okuduğumda, yazarın nanosaniyeler kazandırmak için zaman harcamış olmasına her seferinde minnet duyuyorum

    • Bu tür optimizasyonlar birikince insanlığın toplamda ne kadar zaman kazandığını merak ediyorum

  • 1.7 Şekil 3'te bir hata olduğunu düşünüyorum. 1.3 Şekil 1'deki y ekseni etiketinin "ters aktarım miktarı" olması gerektiğini öneriyorum

  • Ara sıra yazma desteği gerekiyorsa, büyük bir statik arama ağacı ile küçük bir yazılabilir ağaç birlikte kullanılabilir

    • Yeterli değişiklik olduğunda, değişiklikler statik ağacın yeni sürümüne aktarılabilir