Jangan Mengejek Branch Predictor yang Bahagia dan Menyenangkan (2023)

Jangan mengejek branch predictor yang bahagia

• Baru-baru ini sering menulis assembly AArch64
• Ide "cerdas" untuk menghapus satu lompatan dalam loop justru menurunkan performa
• Kesalahan ini dijelaskan agar orang lain tidak mengulangi kesalahan yang sama

Contoh kode

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를 수정하는 작업
}

Diterjemahkan ke assembly AArch64

// 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

Percobaan optimasi

• Mencoba meningkatkan performa dengan mengurangi instruksi bl
• Namun performanya justru menurun

Perbandingan performa

• Kode asli: 969 ns
• Kode teroptimasi: 3.85 µs

Analisis penyebab

• Branch predictor menjadi bingung karena pasangan bl dan ret tidak cocok
• Menurut dokumentasi ARM, instruksi ret membantu memprediksi pengembalian fungsi

Cara mengatasinya

• Gunakan br x30 alih-alih ret
• Performa pulih: 913 ns

Optimasi tambahan

• Inline foo untuk meningkatkan performa
• Gunakan loop unrolling dan instruksi SIMD

Performa akhir

• SIMD + loop unrolling manual: 94 ns

Kesimpulan

• Jangan membuat branch predictor bingung
• Kode SIMD lebih cepat, tetapi hasilnya bisa berbeda karena penjumlahan floating-point tidak mengikuti sifat asosiatif

Opini GN⁺

• Artikel ini menunjukkan dengan baik pentingnya optimasi assembly AArch64
• Memahami cara kerja branch predictor sangat penting untuk optimasi performa
• Optimasi dengan instruksi SIMD sangat efektif, tetapi masalah akurasi perlu dipertimbangkan
• Menggunakan bahasa tingkat tinggi seperti Rust dapat mempermudah peningkatan performa melalui optimasi kompiler
• Proyek dengan fungsi serupa antara lain panduan optimasi assembly dari Agner Fog

[GN⁺]

Pendapat Hacker News

• Meringkas artikelnya bersama teman-teman dari era Apple II

  • Kode yang dioptimalkan membutuhkan 94 nanodetik untuk menjumlahkan 1024 angka floating point 32-bit
  • 6502 1 MHz akan berusaha mengambil byte pertama dari instruksi pertama dari memori selama 94 nanodetik itu
  • Kode ini hanya menunjukkan performa optimal saat dijalankan dari cache. DRAM lambat

• Raymond Chen membahas topik yang sama hampir 20 tahun lalu

  • Setelah memeriksa akhir loop, eksekusi berlanjut ke fungsi foo tanpa cabang
  • Ini melanggar heuristik prediksi dasar
  • Prediktor cabang yang mempertahankan shadow stack untuk alamat return sudah ada selama beberapa dekade

• Pada kode SIMD, penjumlahan floating point dapat dilakukan dalam urutan berbeda karena penjumlahan floating point tidak memenuhi sifat asosiatif

  • Ini mungkin alasan kompiler tidak menghasilkan instruksi SIMD
  • Penjumlahan floating point pada dasarnya memiliki rentang galat, dan semua jawaban dalam rentang itu valid
  • Jika ada input floating point khusus, bahasa harus menyediakan cara untuk mengenkodekannya secara eksplisit

• Sejak Rust 1.78, kompiler menggunakan loop unrolling yang lebih agresif dan sedikit SIMD

  • Loop unrolling dimulai di Rust 1.59
  • Di kode Github, yang digunakan adalah Rust 1.67.0-nightly

• Bingung bagaimana x0 bertambah di assembly ARM/ARM64

  • Instruksi ldr s1, [x0], #4 melakukan load sambil menaikkan x0 sebesar 4
  • x86_64 tidak memiliki instruksi tunggal untuk load dan increment sekaligus

• Mengejutkan bahwa tidak dicoba cara yang kurang kompleks untuk mengoptimalkan kode assembly

  • Kode assembly bisa ditulis ulang agar hanya memerlukan satu cabang di bagian bawah loop
  • foo bisa di-inline dan instruksi RET bisa dihilangkan

• Ada pendapat bahwa sebaiknya penulis tidak terus-menerus mengganti satuan