İşe Yaramaz Bir `if` ile Kod Performansını 4 Kat Artırmak

 (purplesyringa.moe)
1 puan yazan GN⁺ 3 시간 전 | 1 yorum | WhatsApp'ta paylaş
  • Alana özgü bir sıkıştırıcının en iyi kodlama yolunu gezen döngüsüne tek bir koşul ifadesi ekleyerek, sentetik benchmark çalışma süresini 320µs’den 80µs’ye düşürüyor
  • Her yinelemede bellek adresi bir önceki yinelemedeki j’ye bağlı olduğundan, tek bir mov komutu bile komut düzeyi paralellikten yararlanamadan bellek erişim gecikmesine takılıyor
  • next_j[i][j]’nin çoğunlukla mevcut j ile aynı olması özelliği dal tahminine yansıtılırsa, CPU yinelemeler arasındaki bağımlılığı aşarak birden fazla yinelemeyi spekülatif olarak yürütebiliyor
  • Derleyicinin anlamsal olarak gereksiz if’i kaldırmasını önlemek için volatile cast’i kullanılıyor. LLVM’de [[unlikely]] veya __builtin_expect(..., 0) de çalışıyor, ancak volatile daha iyi kod üretiyor ve GCC tarafından da destekleniyor
  • Gerçekçi bir deneyde, LLVM’nin ideal olmayan kod üretiminden kaynaklanmış olabilecek yaklaşık 2 kat performans artışı elde edilmiş; j’yi tahmin etmek zorsa gecikmesi 1 çevrim olan pshufb alternatif olarak kullanılabiliyor

Sıkıştırıcının en iyi yolunu gezmek

  • Girdi dizgesini birden fazla parçaya bölmek ve her parça için en küçük kodlamayı seçmek gerekiyor
    • Her kodlama farklı karakterleri iyi sıkıştırdığı için parça sınırlarını hemen belirlemek zor
    • Önceki yazıdaki algoritma bu problemi bir ızgara üzerinde en kısa yol aramasına dönüştürüyor
  • Her hücrede bir sonraki gidilecek en iyi hücre kaydediliyor
    • İlk hücreden son hücreye kadar referansları takip ederek en iyi kodlama sırası elde edilebiliyor
  • next_j’yi dolduran ilk döngü SIMD ile zaten optimize edilmiş durumda
    • Asıl darboğaz, aşağıdaki gibi basit bir yol gezme döngüsü
uint8_t encoding[n_symbols];
uint8_t j = 0;

for (int i = 0; i < n_symbols; i++) {
    j = next_j[i][j];
    encoding[i] = j;
}
  • Yazmayı dışarıda bırakırsak, çekirdek işlem olan j = next_j[i][j] tek bir mov komutuna derleniyor

Tek bir komutu bile yavaşlatan bağımlılık

  • Modern CPU’lar komut düzeyi paralellikten yararlanarak birden fazla komutu ve farklı yinelemelerdeki işleri aynı anda yürütür
    • Tipik bir döngüde i < n_symbols kontrolü ve i++ maliyetinin diğer işleri engellememesinin nedeni budur
  • Ancak birbirine bağımlı komutlar aynı anda yürütülemez
    • Mevcut yinelemedeki bellek adresi next_j[i][j]’yi hesaplamak için bir önceki yinelemede elde edilen j gerekir
    • Sonraki yineleme, önceki yinelemenin sonucu çıkana kadar başlayamaz; bu yüzden veri cache’te olsa bile bellek erişim gecikmesinden etkilenir

Dal tahminini değer tahmini olarak kullanmak

  • Bu sıkıştırıcıda parça sayısının çok fazla olmayacağı beklendiğinden, next_j[i][j] çoğu durumda mevcut j ile aynıdır
  • CPU’ya j’nin korunacağını doğrudan adres tahmini olarak söylemek mümkün değildir; ancak dal tahmini kullanılarak aynı etki oluşturulabilir
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = next_j[i][j];
    }
    encoding[i] = j;
}
  • CPU if gövdesinin çalıştırılmayacağını tahmin ederse, j’yi güncelleyen yinelemeler arası bağımlılık yokmuş gibi görür ve birden fazla yinelemeyi spekülatif olarak yürütür
  • Koşul gerçekten doğruysa dal tahmini hatasından toparlanma gerçekleşir
    • Yanlış tahminle yapılan yazmalar atılır
    • Doğru j kullanılarak yürütme yeniden başlatılır
  • j neredeyse hiç değişmediği sürece döngünün darboğazı gecikmeden işlem hacmine kayar

Derleyicinin if’i kaldırmasını engellemek

  • Derleyici açısından koşul ifadesi eklenmiş kod ile özgün kodun anlamı aynıdır
    • j bellekte olsaydı gereksiz yazmaları veya salt okunur belleğe yazmayı önleyebilirdi; ancak burada bu bir register değeri
    • Ortak alt ifade eleme (CSE) gibi optimizasyonlar koşulu ve yinelenen erişimi kaldırabilir
  • Yaygın derleyici ipuçları dalları ortadan kaldırmak için kullanılır; burada ise tam tersine, dalsız kodu dallı kod olarak korumak gerekir
  • Koşul kontrolü ile atamanın bellek erişimleri bağımsızmış gibi görünsün diye atama tarafına volatile cast’i uygulanıyor
for (int i = 0; i < n_symbols; i++) {
    if (j != next_j[i][j]) {
        j = *(uint8_t volatile *)&next_j[i][j];
    }
    encoding[i] = j;
}
  • 13 Temmuz’daki ek doğrulamada, ibookstein’ın bulduğu yöntem gibi [[unlikely]] veya __builtin_expect(..., 0) kullanıldığında da LLVM’de aynı etkinin elde edilebildiği görüldü
  • volatile yöntemi daha iyi kod üretiyor ve GCC’de de çalışıyor

Benchmark’ta gözlenen performans değişimi

  • Sentetik benchmark’ta döngünün çalışma süresi 320µs’den 80µs’ye düştü; yani 4 kat hızlandı
    • Tek bir çalıştırmadaki süre farkı küçük olsa da, sıkıştırma sürecinde döngü birden çok kez çalıştığı için toplam maliyete ekleniyor
  • Daha gerçekçi deneylerde yaklaşık 2 kat performans artışı kaydedildi
    • Bunun LLVM’nin ideal olmayan kod üretmesinden kaynaklanmış olması mümkün, ancak yine de uygulanmaya değer bir düzeydeydi

Bit maskesi tabanlı gösterim alternatifi

  • Bu algoritmada next_j[i][j] yalnızca iki değerden birini alabiliyor
    • Çoğunlukla mevcut j
    • Diğeri ise j’den bağımsız, yalnızca i’ye bağlı bir değer
  • 8 öğeli dizi olan next_j[i], alternatif değer ve bit maskesi çiftine dönüştürülebilir
    • Bu gösterimde if anlamsal olarak gerekli olduğundan volatile geçici çözümünü kullanmaya gerek kalmaz
    • Ancak x86’da değişken konumdaki bir biti test eden işlem karşılaştırmadan daha yavaş olabileceği için genel performansın aksine düşme ihtimali var

j tahmin edilemediğinde

  • Bağlı liste gezinimini değer tahminiyle hızlandıran yazı da aynı yaklaşımla performansı artırma yöntemini ele alıyor
  • j’yi tahmin etmek zorsa vektör indeks işlemi olan pshufb kullanılabilir
    • pshufb’nin gecikmesi 1 çevrim olduğundan spekülatif yürütme olmadan daha da azaltmak zordur
    • Vektör işlemiyle olası her başlangıç j değeri için yol paralel olarak hesaplanabilir
    • İşi birden fazla thread’e bölüp sonuçları birleştirme yöntemi de mümkündür

İlgili okumalar

1 yorum

 
GN⁺ 3 시간 전
Lobste.rs görüşleri

  • C++20'nin [[unlikely]] özniteliğini if ifadesine eklemek, clang'in ilgili kodu ortadan kaldıramamasını sağlamak için yeterli görünüyor: https://clang.godbolt.org/z/r4xYWfPfe
    Diğer derleyicilerde kontrol edemedim

    • Tekrar baktığımda LLVM'de gerçekten çalıştığını gördüm; sanırım ilk başta etkisi olmayan GCC ile yanlış test etmiştim
      Ancak [[unlikely]], kodu hızlı yolun dışına taşır, bu yüzden LLVM aşağıdaki gibi biraz verimsiz kod üretiyor 
              cmp     r8b, dl  
        jne     not_equal  
continue:  
        ...  
not_equal:  
        mov     ecx, edx  
        jmp     continue
      Şu biçim daha makul görünüyor 
              cmp     r8b, dl  
        je      skip  
        mov     ecx, edx  
skip:  
        ...
      Ayrıca bellekten değeri birden fazla kez okumamayı optimize ederken sıcak döngüye bir komut daha ekliyor. Bu yüzden volatile kullanan teknik hâlâ faydalı, ama özgün kodun da olduğu gibi çalışabilmesi sevindirici

  • Bu teknik başka yerlerde değer spekülasyonu (value speculation) olarak adlandırılıyor: https://mazzo.li/posts/value-speculation.html

    • Bu yöntemi yeniden düşününce, arena'da tutulan bağlı listeye de uygulanabileceğini ilk kez fark etmiştim; bağlantı verilen yazı tam olarak bundan söz ettiği için kendi yazıma da link ekledim

  • Önümüzdeki 2-3 yıl içinde geliştiriciler LLM çıktısına giderek daha kayıtsız kalacak gibi görünüyor; yine de bu tür blog yazılarına ilgi gösterip göstermeyeceklerini merak ediyorum

    • Şu anda bile buna ilgi duyan çok az kişi var; genel programlama alanı içinde niş bir bilgi
      Yine de ilgilenenler için hâlâ çok yararlı ve iyi bir yazı
    • Godbolt çok popüler. Kod okumama alışkanlığı eleştirildiğinde LLM etkisindeki geliştiriciler “assembly'ye kadar mı bakıyorsun?” diye bunu büyük bir karşı argüman gibi sunuyor, ama ben gerçekten assembly'yi kontrol ediyorum ve etmeye de devam edeceğim
      Ayrıntıların önemli olmadığını düşünen bir geliştiricinin iyi bir geliştirici olması zordur. Nasıl ki iyi bir inşaat mühendisi büyük bir projedeki civata ve somunlara kadar önem verirse, iyi bir geliştirici de küçük ayrıntıların dibine kadar inmeli. Bütün, ayrıntılardan oluşur; bu yüzden ortaya çıkardığın şeyi önemsiyorsan bundan kaçamazsın
    • Bunun bugünden temelde farklı olduğunu düşünmüyorum. Bugün de çoğu insan, insan tarafından yazılmış kodun derleyici çıktısıyla ilgilenmiyor
      Yapay zeka tarafından yazılmış kodun derleyici çıktısına bakan kişi sayısı daha da azalabilir, ama temel tablo değişmeyecek gibi
    • Değişen şey, ilginin varlığı ya da yokluğundan çok optimizasyon önceliklerinin yeniden sıralanması gibi
      10 yıl önce biraz yavaş çalışan bir Bash betiği için önce komut düzeyi paralellik ya da CPU dal tahmini üzerine kafa yorulmazdı. Derlenebilen ve optimize edilebilen bir dilde yazılmış performans açısından kritik bir bölüm vardır; onun içinde ayrıntılı incelenmeye değer sıcak bir yol bulunur; onun da içinde vektörleştirme ya da modern CPU'ların çalışma farklarını kontrol etmeye değecek bir ya da iki sıcak döngü olabilir
      LLM kullansan bile performans açısından en sıcak noktalar istisnai olarak elle incelenmeye değer kalır. Çıktının düşük kalitesini bilinçli olarak kabullenmek ya da LLM ile %70'ini üretip kalan %30'u elle düzeltmek yaklaşımı zamanla 85:15'e iyileşse bile, bu yazı yine de ilk %1'lik düzeydeki ayrıntılı bir alanı ele alıyor
    • C++ yazmadığım için o anlamda şimdi de doğrudan ilgi alanım değil, ama yine de keyifle okudum ve 2-3 yıl sonra da bu tür şeylerin ilginç gelmeye devam edeceğini düşünüyorum