Happy Fun dal tahmincisiyle alay etmeyin (2023)

 (mattkeeter.com)
1 puan yazan GN⁺ 2024-07-05 | 1 yorum | WhatsApp'ta paylaş
  • AArch64 assembly’de bir döngüdeki dallanmalardan birini azaltmaya yönelik optimizasyon, aksine 4 kat yavaşladı; nedenin bl/ret çağrı-dönüş çiftinin asimetrik kullanılarak dal tahmincisinin şaşırtılması olduğu ortaya çıktı
  • Orijinal kod her döngüde bl foo ve b loop ile iki kez dallanırken, değiştirilmiş kod tek bir bl loop ile x30’u sabitleyip birden çok ret’in aynı adrese dönmesini sağlayarak dallanma sayısını azaltmaya çalıştı
  • M1 Max’te 1024 elemanlı bir float dizisini toplama sonucunda, normal bl/ret kodu 969ns sürerken tek bir bl ve birden çok ret yapısı 3.85µs’ye yavaşladı; ret, br x30 ile değiştirildiğinde süre 913ns’ye toparlandı
  • Instruments performans sayaçları, 1 milyar elemanın toplanmasında asimetrik bl/ret yapısının dönüş dallanması tahmin hatasının yaklaşık %93 olduğunu gösterdi; FETCH_RESTART, MAP_DISPATCH_BUBBLE, MAP_REWIND de büyük ölçüde arttı
  • Daha hızlı uygulamalar foo’yu inline etmeye, Rust iter().sum() kullanımına, NEON SIMD ve manuel döngü unrolling’e doğru ilerliyor; nihai SIMD sürümü 94ns’ye kadar inse de kayan nokta toplama sırası değiştiği için sonuç farklı olabilir

AArch64 döngüsünde ortaya çıkan ters etki

  • Örnek fonksiyon, bir float dizisi üzerinde dolaşıp her değeri foo’ya ileten ve foo’nun birikimli değer g’yi güncellediği bir yapıya sahip
  • Basit AArch64 dönüşümü şu akışa sahiptir
    • Döngü başında n == 0 olup olmadığını kontrol eder
    • ldr s1, [x0], #4 ile değeri okur
    • bl foo ile alt rutini çağırır
    • foo içindeki ret, bl sonrasındaki komuta döner
    • b loop ile tekrar döngü başlangıcına gider
  • foo, üst fonksiyonla aynı stack frame’i ve register’ları kullanan, naked function’a yakın bir biçimde s1’i okuyup s0’da biriktirir

bl ve ret’in rolleri

  • bl, branch and link komutudur; belirtilen etikete atlarken bir sonraki komutun adresini link register lr ya da x30’a kaydeder
  • ret, link register’da bulunan adrese atlar
  • Orijinal yapıda bl foo ile ret birbiriyle eşleşir ve ret her zaman ilgili bl’den sonraki komuta döner

Başarısız “bir dallanma azaltma” optimizasyonu

  • Değiştirilmiş yapı, foo’yu değiştirmeden döngü içindeki bir dallanmayı azaltmaya çalışır
    • Fonksiyon başında bl loop çağrılarak x30’a loop başlangıç adresi konur
    • Döngü bitiş koşulu kontrol edildikten sonra ayrı bir dallanma olmadan foo koduna düşülür
    • foo içindeki ret, x30’da bulunan loop’a döner
  • Bu yapıda döngü gövdesinde x30 değişmediğinden, tekrarlanan ret her zaman aynı adrese döner
  • Basit foo, aşağıdaki gibi float toplayan tek satırlık bir koddur
foo:
    fadd s0, s0, s1
    ret
  • Bu durumda tüm fonksiyon, girdi float dizisinin toplamını hesaplar

Benchmark sonuçları ve dal tahmini sorunu

  • criterion ile M1 Max CPU üzerinde 1024 elemanlı dizi benchmark edildi
    • Normal bl/ret: 969ns
    • Tek bir bl, birden çok ret: 3.85µs
  • Bir dallanmayı azaltan kod, iki dallanma kullanan orijinal koda göre yaklaşık 4 kat daha yavaş
  • Cliff ve Dan, bl/ret çiftinin eşleşmemesi nedeniyle dal tahmincisinin karıştığını düşündü
  • ARM belgelerine göre RET, işlemcinin fonksiyon dönüşünü tanımasını sağlayarak daha doğru dal tahminini mümkün kılar
    • BR LR da işlevsel olarak aynı işi yapabilir
    • Ancak RET, işlemcinin fonksiyon dönüşü olarak tanıyabileceği ayrı bir komuttur
    • Dal tahmini doğruysa pipeline’a doğru komutlar girer ve bellekten komut bekleme süresi önlenebilir

Dönüş adresi stack’i ve br x30 deneyi

  • Dal tahmincisinin içeride fonksiyon dönüş adresi stack’i tutuyor olması muhtemeldir
    • bl çalıştırıldığında dönüş adresini stack’e push eder
    • ret gördüğünde en son bl’in dönüş adresine dönüleceğini varsayar
    • Bu adrese göre önceden getirme ve spekülatif yürütmeyi başlatıp ardından stack’ten pop eder
  • Bu yöntem, bl/ret eşleşen çiftler olduğunda iyi çalışır
  • Aynı adres birden çok ret tarafından tekrar tekrar kullanılırsa tahmin başarısız olur; işe yaramaz önceden getirme, hatalı spekülatif yürütme, pipeline durması veya flush oluşabilir
  • Dan’in önerisiyle ret, br x30 olarak değiştirildiğinde performans düşüşü ortadan kalktı
    • Normal bl/ret: 969ns
    • Tek bir bl, birden çok ret: 3.85µs
    • Tek bir bl, birden çok br x30: 913ns
  • br x30 sürümü her döngüde yalnızca bir dallanma yaptığı için orijinal koddan biraz daha hızlıdır

Instruments performans sayaçları

  • İlk iki programın performans sayaçları Instruments ile kontrol edildi
  • Ölçüm, 1 milyar elemanlı dizinin toplanması sırasında yapıldı
  • Asimetrik bl/ret’te dönüş dallanması tahmin hatası yaklaşık %93 oranında gerçekleşti
Sayaç Normal bl/ret Tek bir bl, birden çok ret
BRANCH_RET_INDIR_MISPRED_NONSPECIFIC 92 928,644,975
FETCH_RESTART 61,121 987,765,276
MAP_DISPATCH_BUBBLE 1,155,632 7,350,085,139
MAP_REWIND 6,412,734 2,789,499,545
  • Apple bu sayaçları tamamen belgelemiyor
  • Diğer sayaçların kötü dal tahmininin downstream etkileri olduğu tahmin ediliyor
    • FETCH_RESTART: muhtemelen hatalı önceden getirme
    • MAP_DISPATCH_BUBBLE: pipeline durması ile ilişkili olabilir
    • MAP_REWIND: geri sarılması gereken hatalı spekülatif yürütme olabilir

Daha hızlı hale getirmenin yolları

  • Örnek eğitim amaçlı koddur; foo’nun alt rutin olmasının nedeni de “mümkün olan en hızlı kod” değil, daha çok açıklama amaçlı yapıdır
  • foo içeriği derleme zamanında biliniyorsa ve maksimum atlama mesafesinden kısaysa bl ve ret tamamen kaldırılıp inline edilebilir
    • 969ns’den 911ns’ye, yaklaşık %6 hızlanır
  • Rust’ta basitçe f.iter().sum() kullanılırsa 833ns’ye kadar iner
pub fn sum_slice(f: &[f32]) -> f32 {
    f.iter().sum()
}

SIMD ve manuel döngü unrolling

  • Manuel AArch64 SIMD uygulaması üç döngüden oluşur
    • loop: Kalan değer sayısı 4’ün katı olana kadar tekil değerleri s0’a ekler
    • simd: 4 değeri tek seferde v1 vektör register’ına ekler ve kalan değer sayısı 8’in katı olana kadar tekrar eder
    • simd2: simd’i 2 kat unroll ederek her iterasyonda 8 değeri işler ve v1 ile v2’de toplar
  • Fonksiyon sonunda v1 ve v2 değerleri s0’a eklenip döndürülür
  • Type punning, float* olan x0’ı double* gibi ele alarak 128 bit, yani 4 adet float’ı d3 ve d4 olarak okuma yöntemidir
    • mov v3.d[1], v4.d[0] ile d4’ün 64 bit’i v3’ün üst 64 bit’ine taşınır
    • fadd v1.4s, v1.4s, v3.4s içinde .4s sonekiyle dört adet float gibi işlenir
  • Bu SIMD uygulaması 94ns’de çalışır ve önceki en iyi Rust sürümü olan 833ns’den yaklaşık 8,8 kat daha hızlıdır

Genel performans özeti ve dikkat edilmesi gerekenler

Uygulama Süre
Normal bl/ret 969ns
Tek bir bl, birden çok ret 3.85µs
Tek bir bl, birden çok br x30 913ns
b kullanan sıradan döngü 911ns
Rust ile yeniden yazım 833ns
SIMD + manuel döngü unrolling 94ns
  • SIMD kodu kayan nokta toplama sırasını değiştirir
  • Kayan nokta toplamada birleşme özelliği geçerli olmadığından SIMD sürümü düz kodla aynı sonucu üretmeyebilir
  • Derleyicinin toplam için SIMD komutları üretmemesinin nedeni de muhtemelen budur
  • Tüm kod GitHub’da açık olarak yayımlanmıştır
  • ARM64 makinede cargo bench çalıştırılarak benchmark yeniden üretilebilir

İlgili okumalar

1 yorum

 
GN⁺ 2024-07-05
Hacker News görüşleri

  • Son optimize edilmiş kod, 1024 elemanlı 32 bit kayan noktalı sayı dizisinin toplamını 94 ns’de bitiriyor.
    O 94 ns içinde eski dostumuz 1 MHz 6502, programın ilk komutunun ilk baytını getirmesi için bellek çipine sinyal gönderip göndermemeyi daha yeni düşünmeye başlamış olurdu.
    Ancak bu kod tamamen önbellek içinde çalıştığı varsayımına dayanıyor. Aksi halde yazıda geçen güçlü M1 Max bile ilk bellek getirmesini beklerken durmuş olurdu. DRAM yavaş.

    • Artık toplam L1 önbellek boyutunun, 6502’nin adresleyebildiği toplam bellek kadar büyük olması şans. Gerçekten inanılmaz bir çağda yaşıyoruz.

  • Raymond Chen neredeyse 20 yıl önce aynı konuyu ele almıştı: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...

    • Intel’in x86/64 mimarisi komut başvuru kitabının basılı hâline, yani kalın mavi kitaplara sahip olan ve veri sayfalarıyla dokümantasyonu dikkatle okuyan biri olarak, “sezgisel olarak X olacak gibi duruyor ama Y oluyor” dendiğini her duyduğumda hep temkinli davranıyorum.
      Silisyumun yarı iletken özellikleri ve katkılama konusunda temel bir anlayış dışında, burada sezgisel olan pek bir şey yok. Kalıp devre şemasını, kablolamayı ve yolları görmediyseniz, mühendisler ve veri sayfaları açıkça söylemedikçe A’nın B’den hızlı olmasını beklemek için pek neden yok. Özellikle ARM için bunun daha da geçerli olduğunu düşünüyorum.
    • Raymond Chen’in yazısı harika ve bu yazıyı yorumlamak için iyi bir bağlam sunuyor.
      Bu yazının eklediği şey, reti başka bir br komutuyla değiştiren basit bir düzeltme. Böylece çift yeniden “simetrik” hâle geliyor ve dal tahmincisini bozmadan biraz daha hızlı kod elde edilebiliyor.
    • Raymond Chen gerçekten hazine gibi biri. Microsoft’un ona blog yazmaya devam edebilmesi için takdir alanı tanımasına minnettarım; oradan gerçekten çok şey öğrendim.
    • Son x86 işlemcilerde artık doğru değil gibi görünüyor: https://news.ycombinator.com/item?id=40767676

  • Elbette her şey mümkün ve bir dizinin toplamını alan sıradan bir döngü, gerçekten de bilgisayara elemanları tek tek biriktirmesini söyleyen bir biçimde yazılır.
    Ama örneğin SIMD ile dört birikim değerini paralel oluşturup sonunda toplamanın, elemanları tek tek toplamaktan daha yanlış olduğunu söylemek zor.
    Kayan noktalı toplama işlemlerinde temelde bir hata aralığı olduğu varsayılmalı ve bu aralıktaki cevaplar geçerli olmalı. Girdi kayan noktalı sayıları hakkında özel bir bilginiz varsa, dil bu niyeti açıkça ifade edecek bir araç sunmalı. En temel döngü varsayılan olduğuna göre, varsayılan olarak en iyi performansı vermesi gerektiğini düşünüyorum.

    • Sayı listesini toplamak gibi basit bir işte bile şaşırtıcı derecede çok toplama algoritması var.
      Döngüde tek tek toplamak bariz yöntem, ancak birikimli hatanın toplamı için daha iyi sınırlar veren daha sofistike yöntemler var; Kahan toplamı iyi bilinen bir örnek: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
      Akış verisiyse tek tek toplamaktan başka seçeneğiniz olmayabilir; ama sabit boyutlu N adet arabellek kullanabiliyorsanız, yeni bir sayı geldiğinde hangi alt kümeyi kısmi toplam yapacağınız, bunu birikimli toplama nasıl ekleyeceğiniz ve bu seçimin kanıtlanabilir bir hata iyileştirmesi olup olmadığı gibi sorular ortaya çıkar.
    • Kayan noktalı değerlerin büyüklük farkı büyükse bu ciddi bir sorun olur.
      Örneğin [1e50, -1e50, 1e3, 1e3] değerlerini (((1e50 + -1e50) + 1e3) + 1e3) şeklinde hesaplarsanız 2e3 çıkar; ((1e50 + 1e3) + (-1e50 + 1e3)) şeklinde hesaplarsanız 0 olur.
      Küçük değerlerin çoğunu tek bir büyük değere eklerken de benzer bir durum vardır; (((1e3 + 1e3) + 1e3) ... + 1e50) ile (((1e50 + 1e3) + 1e3) ... + 1e3) oldukça farklıdır.
    • “Böyle olmalı” türünden çok şey söyleniyor ama pratikte neredeyse hiç öyle olmuyor. Özgün ifadenin sağladığı tek bilgi aritmetik işlem sırasıdır.
      Derlemeler arasında aritmetik sonuçlar kararlı değilse bu tam bir kâbusa dönüşür. Aynı girdilerle yazılımı yeniden derleyip çalıştırdığınızda farklı sonuçlar çıkmamalı.
      Eskiden Intel’e özgü bir örnek de yaşamıştım: FPU içeride 80 bit kayıtlar, bellekte ise 64 bit kullanıyordu; bu yüzden kayıtların doldurulup boşaltılma zamanı değiştiğinde yuvarlama zamanı da değişiyor, sonuç da farklılaşıyordu. Program başlangıcında genel FPU bayrağı ayarlanarak her işlemde yuvarlama zorlanabiliyor.
    • Kayan noktalı değerleri sıralamak hatayı azaltır. Bu yüzden birden çok akümülatör kullanmanın doğruluğu düşürebileceğini düşünüyorum. Sıralı veri de hiç nadir değil.
      Her zaman doğru bir cevap vardır ve derleyicinin en azından varsayılan olarak yanlış bir değişiklik yapmaması gerektiğini düşünüyorum. Bununla birlikte programcının niyetini daha açık ifade edebilmesinin yolları her zaman memnuniyet verici.
    • Birçok kod, belirli bir komut kümesi mimarisi içinde kayan noktalı işlemlerin deterministik olmasına dayanır.
      Kayan noktalı döngülere SIMD uygulamak varsayılan olabilirdi, ancak mevcut birçok kodu bozacağı ve çıktıyı sık sık deterministik olmayan biçimde değiştireceği için programcının açıkça seçmesi gereken bir özellik hâline geldi.
      Üstelik birçok programcı bunu bilmiyor olabilir; bu yüzden float Sum(float[] values) farklı değer döndürmeye başlasa bile nedeninin vektörleştirme olduğunu anlamanın bir yolu olmayabilir. Bu nedenle örneğin .NET standart kütüphanesi integers.Sum() için SIMD kullanır, ama floats.Sum() için kullanmaz.

  • Yalnızca “döngü çıkışını kontrol ettikten sonra, dallanma olmadan doğrudan foo fonksiyonunun içine düşüyor” satırını okuyunca “ha, sorun buymuş” diye düşündüm.
    Gösterişli dal tahmincisi sezgiselleri hakkında derin bir konu olacağını sanmıştım ama sonuçta temel sezgiselin ihlaliymiş.
    Eşleşmeyen call/ret komutları kullanarak muazzam hız artışı elde edebileceğinizi düşünmemek gerekir. Dal tahmincisinin dönüş adreslerinin gölge yığınını tutması onlarca yıldır var olan bir yöntem.

    • Dal tahmincisinin nasıl çalıştığını iyi bilmek güzel, ama pek çok kişi bunu bilmiyor; onlar için yeni ve belki yararlı bir bilgi olabilir. Bu yazı sadece sizin için yazılmamıştı, bunda da sorun yok.
    • Güvenlik özelliği olarak mimari düzeyde gölge çağrı yığını bulunan sistemlerde programın çalışmasını daha kökten bozabilir; yani çökmeye neden olabilir.
    • Bir yandan RISC’in tasarım hedefi, çoğu başka unsuru feda ederek derlenmiş kodun performansını artırmaktır.
      Bu yüzden bu tür riskler belgelenmeli, ancak tasarımcılar assembly’yi doğrudan yazan kişinin belgeleri okuduğunu varsayabilmelidir.
      Öte yandan Sophie Wilson başlangıçta ARM için BBC BASIC uygulamasını yazmıştı, ama o zaman dal tahmincisi yoktu. 32 bit olduğu için kurallar farklı olsa da, mimari varsayımlar değiştiğinde AArch64’ün kodu nasıl yavaşlattığını merak ediyorum.
    • Yine de pratikte bu optimizasyonun ve diğer optimizasyonların nasıl başarıldığını da gösterdiği için faydalı bir yazı.

  • Klasik SNL göndermesi olan “Do not taunt happy fun ball”: https://www.youtube.com/watch?v=GmqeZl8OI2M

    • happy fun dal tahmincisinden duman çıkmaya başlarsa derhal tahliye etmelisiniz.
    • “Happy Fun Ball Suudi Arabistan’daki askerlerimize gönderildi ve Irak üzerindeki savaş uçaklarından da atılıyor” ifadesini görünce “şu an hangi yıldayız yahu!?” hissi geliyor.
    • Hâlâ 16 eyalette yasal: https://www.youtube.com/watch?v=2AzAFqrxfeY

  • Bunun 2023 tarihli bir yazı olduğu gözden kaçmamalı. Şu an biraz eskidi bile; Rust 1.78’den itibaren derleyici daha agresif döngü açma ve bir miktar SIMD kullanıyor: https://godbolt.org/z/zhbobW7rr
    Orijinal yazı “assembly’ye bakınca döngü açma yaptığını görüyorum” deyip https://godbolt.org/z/Kv77abW6c bağlantısını vermişti; bu ise sürekli değişen “Rust Nightly” kullanıyordu. Şimdi döngü açma daha fazla.
    Döngü açma Rust 1.59’dan itibaren başlamıştı: https://godbolt.org/z/5PTnWrWf7
    GitHub koduna göre Rust 1.67.0-nightly, 2022-11-27 sürümünü kullanıyordu.

    • Bağlantıyı Rust 1.67 açıkça seçilecek şekilde güncelledim.
    • Orijinal yazının görmüş gibi göründüğü Rust 1.67.0 şu sonucu üretiyor: https://godbolt.org/z/4Y61d9seh
      Aynı donanımda güncel nightly Rust 1.81’in agresif döngü açmasıyla benchmark’ı kendim çalıştırdım, ama fark yoktu; hız 1,5 yıl öncekiyle aynıydı.

  • 2023 tarihli bir yazı. O zamanki tartışma: https://news.ycombinator.com/item?id=34520498

    • Açarsak, “Do not taunt happy fun branch predictor”ın Ocak 2023 tartışmasıydı ve 171 yorum vardı: https://news.ycombinator.com/item?id=34520498
      Yaklaşık 1 yıl sonra yeniden paylaşılması sorun değil; geçmiş konu bağlantısı daha fazlasını merak eden okurlar için.

  • ARM/ARM64 assembly’ye çok aşina olmadığım için x0’ın nasıl artırıldığını karıştırdım.
    const float f = *data++; ifadesi ldr s1, [x0], #4 oluyor; bu komut değeri okurken aynı anda x0’ı 4 artırıyor gibi görünüyor.
    Negatif değer de kullanılabildiğinden geriye doğru gezinmek de mümkün olmalı. Oldukça hoş. x86_64’te okuma ve artırmayı tek seferde yapan tek bir komut yok gibi.

    • lods ve stos sırasıyla rsi veya rdi üzerinde okuma/yazma ile artırmayı birlikte yapar. İki bellek adresi arasında kopyalarken artıran movs da var.
      Genellikle rcx kez yineleyen rep ile birlikte kullanılır. Örneğin 10 baytlık bir memset, mov rcx, 10, mov rdi, dest, mov rax, 0, rep stosb biçiminde yapılabilir.
      w, d, q soneklerini kullanırsanız sırasıyla 2, 4, 8 bayt ilerler.

  • Yazı iyiydi, ama tablolara göz atıp karşılaştırmayı zorlaştıracak şekilde µs ve ns birimleri arasında sürekli gidip gelmesi hoş değildi.

    • Yazının ortasında C’den Rust’a geçilmesi de biraz şaşırtıcıydı.

  • Kodu optimize etmeden önce daha az akıllıca bir yöntemin denenmemiş olması şaşırtıcı.
    Assembly yeniden yazılırsa döngünün sonunda yalnızca bir dal gerekir; ayrıca X1 için karşılaştırma amaçlı çıkarma ve azaltmayı ayrı ayrı yapmak yerine tek bir ALU işlemi ile halledilebilir.
    Daha da ileri gidilirse foo doğrudan inline edilebilir ve eşleşmeyen BL/RET hilesi olmadan RET komutu da atlanabilir. Kendim benchmark yapmadığım için gerçekte ne kadar hızlanacağını bilmiyorum.

    • Bir yazım hatası var. cbnz yazan satır cbz olmalı. CBZ, kayıt 0 ise etikete dallanır; CBNZ ise 0 değilse dallanır.