Mutlu Eğlenceli Dal Tahmincisiyle Alay Etmeyin (2023)

Mutlu dal tahmincisiyle alay etmeyin

• Son zamanlarda çok fazla AArch64 assembly yazıyor
• Döngüde bir sıçramayı kaldırmaya yönelik "akıllı" bir fikir performansı düşürüyor
• Başkalarının aynı hatayı yapmaması için bu hatayı açıklıyor

Kod örneği

float run(const float* data, size_t n) {
  float g = 0.0;
  while (n) {
    n--;
    const float f = *data++;
    foo(f, &g);
  }
  return g;
}

static void foo(float f, float* g) {
  // g를 수정하는 작업
}

AArch64 assembly'ye çeviri

// x0: const float* data
// x1: size_t n
// s0: 반환할 float
stp  x29, x30, [sp, #-16]!
mov s0, #0.0
loop:
  cmp x1, #0
  b.eq exit
  sub x1, x1, #1
  ldr s1, [x0], #4
  bl foo
  b loop
foo:
  // s1에서 읽고 s0에 누적
  // ...
  ret
exit:
  ldp  x29, x30, [sp], #16
  ret

Optimizasyon denemesi

• bl komutunu azaltarak performansı artırmaya çalışıyor
• Ancak performans aksine düşüyor

Performans karşılaştırması

• Orijinal kod: 969 ns
• Optimize edilmiş kod: 3.85 µs

Neden analizi

• Dal tahmincisi, bl ve ret çiftlerinin eşleşmemesi nedeniyle kafası karışıyor
• ARM belgelerine göre ret komutu, fonksiyon dönüşünü tahmin etmeye yardımcı oluyor

Çözüm yöntemi

• ret yerine br x30 kullanımı
• Performansın geri kazanılması: 913 ns

Ek optimizasyon

• foo'yu inline ederek performansı artırma
• Döngü unrolling ve SIMD komutlarını kullanma

Nihai performans

• SIMD + elle döngü unrolling: 94 ns

Sonuç

• Dal tahmincisinin kafasını karıştırmayın
• SIMD kodu daha hızlıdır, ancak kayan noktalı toplama birleşme özelliğine uymadığından sonuç farklı olabilir

GN⁺ görüşü

• Bu yazı, AArch64 assembly optimizasyonunun önemini iyi gösteriyor
• Dal tahmincisinin çalışma prensibini anlamak, performans optimizasyonu için kritik
• SIMD komutlarıyla yapılan optimizasyon çok etkili, ancak doğruluk sorunları dikkate alınmalı
• Rust gibi yüksek seviyeli diller kullanılırsa derleyici optimizasyonlarıyla performans daha kolay artırılabilir
• Benzer işlevlere sahip projeler arasında Agner Fog'un assembly optimizasyon rehberi bulunuyor

[GN⁺]

Hacker News görüşü

• Yazı, Apple II döneminden arkadaşlarla birlikte özetlenmiş

  • Optimize edilmiş kod, 1024 adet 32 bit kayan noktalı sayıyı toplamak için 94 nanosaniye harcıyor
  • 1 MHz 6502, 94 nanosaniye boyunca ilk komutun ilk baytını bellekten getirmeye çalışıyor olurdu
  • Bu kod yalnızca cache'ten çalıştığında optimize edilmiş performans gösteriyor. DRAM yavaş

• Raymond Chen neredeyse 20 yıl önce aynı konuyu ele almıştı

  • Döngünün bittiğini kontrol ettikten sonra dallanma olmadan foo fonksiyonuna geçiliyor
  • Bu, temel tahmin sezgisellerini ihlal ediyor
  • Dallanma tahmincisinin dönüş adresleri için bir gölge yığın tutması onlarca yıldır var

• SIMD kodu, kayan noktalı toplamanın birleşme özelliğine uymaması nedeniyle toplamayı farklı sırada yapabiliyor

  • Bu, derleyicinin neden SIMD komutları üretmediğini açıklıyor olabilir
  • Kayan noktalı toplama doğası gereği bir hata payına sahiptir ve bu aralıktaki tüm cevaplar geçerlidir
  • Özel kayan noktalı girdiler varsa, dil bunları açıkça kodlayabilmek için araçlar sunmalıdır

• Rust 1.78'den itibaren derleyici daha agresif loop unrolling ve bir miktar SIMD kullanıyor

  • Loop unrolling Rust 1.59'da başladı
  • GitHub kodunda Rust 1.67.0-nightly sürümü kullanılıyordu

• ARM/ARM64 assembly'de x0'ın nasıl arttığı kafa karıştırıcıydı

  • ldr s1, [x0], #4 komutu, x0'ı 4 artırırken yükleme yapıyor
  • x86_64'te aynı anda yükleyip artıran tek bir komut yok

• Assembly kodunu optimize etmek için daha az karmaşık yöntemlerin denenmemiş olması şaşırtıcıydı

  • Assembly kodu, döngünün en altında yalnızca tek bir dallanma gerekecek şekilde yeniden yazılabilir
  • foo inline edilebilir ve RET komutu atlanabilir

• Yazarın birimleri sürekli değiştirmemesi gerektiğini söyleyen bir görüş vardı