Jangan Mengejek Prediktor Cabang Happy Fun (2023)

 (mattkeeter.com)
1 poin oleh GN⁺ 2024-07-05 | 1 komentar | Bagikan ke WhatsApp
  • Sebuah optimasi di assembly AArch64 yang mencoba mengurangi satu cabang dalam loop justru menjadi 4 kali lebih lambat, dan penyebabnya adalah penggunaan pasangan panggil-kembali bl/ret secara asimetris sehingga membingungkan prediktor cabang
  • Kode asli melakukan dua cabang per iterasi loop, bl foo dan b loop, tetapi kode yang diubah mencoba mengurangi jumlah cabang dengan menetapkan x30 lewat satu bl loop, lalu membuat beberapa ret kembali ke alamat yang sama
  • Di M1 Max, hasil penjumlahan array 1024 float menunjukkan kode bl/ret normal memakan 969ns, tetapi struktur satu bl dan banyak ret melambat menjadi 3.85µs; saat ret diganti dengan br x30, performa pulih menjadi 913ns
  • Penghitung performa Instruments menunjukkan bahwa pada penjumlahan 1 miliar elemen, kegagalan prediksi cabang return pada struktur bl/ret asimetris mencapai sekitar 93%, dan FETCH_RESTART, MAP_DISPATCH_BUBBLE, serta MAP_REWIND juga meningkat tajam
  • Implementasi yang lebih cepat berlanjut ke foo yang di-inline, Rust iter().sum(), serta NEON SIMD dengan unrolling loop manual; versi SIMD final turun hingga 94ns, tetapi urutan penjumlahan floating-point berubah sehingga hasilnya bisa berbeda

Efek balik yang muncul di loop AArch64

  • Fungsi contoh menelusuri array float, meneruskan tiap nilai ke foo, lalu foo memperbarui nilai akumulasi g
  • Konversi AArch64 sederhananya memiliki alur berikut
    • Di awal loop, dicek apakah n == 0
    • Nilai dibaca dengan ldr s1, [x0], #4
    • Subrutin dipanggil dengan bl foo
    • ret milik foo kembali ke instruksi setelah bl
    • Lalu b loop melompat kembali ke titik awal loop
  • foo berbentuk mendekati naked function yang memakai stack frame dan register yang sama dengan fungsi induk, membaca s1 dan mengakumulasi ke s0

Peran bl dan ret

  • bl adalah instruksi branch and link yang melompat ke label tujuan sambil menyimpan alamat instruksi berikutnya ke register link lr atau x30
  • ret melompat ke alamat yang tersimpan di register link
  • Pada struktur asli, bl foo dan ret saling berpasangan, dan ret selalu kembali ke instruksi tepat setelah bl

Optimasi “kurangi satu cabang” yang gagal

  • Struktur yang dimodifikasi mencoba mengurangi satu cabang di dalam loop tanpa mengubah foo
    • Di awal fungsi, dipanggil bl loop untuk menaruh alamat awal loop ke x30
    • Setelah memeriksa kondisi selesai loop, alur jatuh langsung ke kode foo tanpa cabang terpisah
    • ret milik foo kembali ke loop yang tersimpan di x30
  • Dalam struktur ini, x30 tidak berubah selama isi loop berjalan, sehingga ret yang berulang selalu kembali ke alamat yang sama
  • foo yang sederhana hanya berupa satu baris kode penjumlahan float seperti berikut
foo:
    fadd s0, s0, s1
    ret
  • Dalam kasus ini, seluruh fungsi menghitung jumlah semua nilai pada array float masukan

Hasil benchmark dan masalah prediksi cabang

  • Dengan criterion, array berisi 1024 elemen dibenchmark di CPU M1 Max
    • bl/ret normal: 969ns
    • Satu bl, banyak ret: 3.85µs
  • Kode yang mengurangi satu cabang justru sekitar 4 kali lebih lambat daripada kode asli yang memakai dua cabang
  • Cliff dan Dan menilai prediktor cabang menjadi bingung karena pasangan bl/ret tidak cocok
  • Menurut dokumentasi ARM, RET memungkinkan prosesor mengenali bahwa ini adalah return dari fungsi sehingga prediksi cabang bisa lebih akurat
    • BR LR juga bisa melakukan hal yang sama secara fungsional
    • Namun RET adalah instruksi terpisah yang bisa dikenali prosesor sebagai return fungsi
    • Jika prediksi cabang benar, pipeline akan berisi instruksi yang tepat dan bisa menghindari waktu tunggu pengambilan instruksi dari memori

Stack alamat return dan eksperimen br x30

  • Prediktor cabang kemungkinan memelihara stack alamat return fungsi secara internal
    • Saat bl dieksekusi, alamat return di-push ke stack
    • Saat melihat ret, prosesor mengasumsikan ia akan kembali ke alamat return dari bl terbaru
    • Berdasarkan alamat itu, prosesor memulai prefetch dan eksekusi spekulatif lebih dulu, lalu melakukan pop dari stack
  • Pendekatan ini bekerja baik saat bl/ret memang merupakan pasangan yang cocok
  • Jika banyak ret berulang memakai alamat yang sama, prediksi bisa gagal, menyebabkan prefetch yang sia-sia, eksekusi spekulatif yang keliru, serta stall atau flush pada pipeline
  • Sesuai saran Dan, ketika ret diganti menjadi br x30, penurunan performa pun hilang
    • bl/ret normal: 969ns
    • Satu bl, banyak ret: 3.85µs
    • Satu bl, banyak br x30: 913ns
  • Versi br x30 sedikit lebih cepat dari kode asli karena hanya melakukan satu cabang per iterasi loop

Penghitung performa Instruments

  • Penghitung performa untuk dua program pertama diperiksa dengan Instruments
  • Pengukuran dilakukan saat menjumlahkan array dengan 1 miliar elemen
  • Pada bl/ret asimetris, kegagalan prediksi cabang return terjadi sekitar 93%
Counter bl/ret normal Satu bl, banyak 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 tidak mendokumentasikan counter-counter ini secara lengkap
  • Counter lain diduga merupakan efek lanjutan dari prediksi cabang yang buruk
    • FETCH_RESTART: kemungkinan prefetch yang salah
    • MAP_DISPATCH_BUBBLE: kemungkinan terkait pipeline stall
    • MAP_REWIND: kemungkinan eksekusi spekulatif keliru yang harus diputar balik

Cara membuatnya lebih cepat

  • Contoh ini adalah kode edukatif, dan alasan foo dijadikan subrutin lebih dekat ke struktur penjelasan daripada “kode tercepat yang mungkin”
  • Jika isi foo diketahui saat build dan jaraknya masih dalam batas lompatan maksimum, bl dan ret bisa dihapus sepenuhnya dengan inline
    • Dari 969ns menjadi 911ns, sekitar 6% lebih cepat
  • Jika cukup menulis f.iter().sum() di Rust, waktunya turun hingga 833ns
pub fn sum_slice(f: &[f32]) -> f32 {
    f.iter().sum()
}

SIMD dan loop unrolling manual

  • Implementasi SIMD AArch64 manual terdiri dari tiga loop
    • loop: menambahkan nilai satu per satu ke s0 sampai jumlah nilai tersisa menjadi kelipatan 4
    • simd: menambahkan 4 nilai sekaligus ke register vektor v1, lalu berulang sampai jumlah nilai tersisa menjadi kelipatan 8
    • simd2: versi simd yang di-unroll 2 kali sehingga memproses 8 nilai per iterasi dan mengakumulasi ke v1 dan v2
  • Saat fungsi selesai, nilai dalam v1 dan v2 diakumulasikan ke s0 lalu dikembalikan
  • Type punning dilakukan dengan memperlakukan x0 yang berupa float* seolah double*, sehingga 128 bit, yaitu 4 buah float, dibaca sebagai d3 dan d4
    • mov v3.d[1], v4.d[0] memindahkan 64 bit dari d4 ke 64 bit atas v3
    • Di fadd v1.4s, v1.4s, v3.4s, sufiks .4s membuatnya diperlakukan sebagai empat float
  • Implementasi SIMD ini berjalan dalam 94ns, sekitar 8.8 kali lebih cepat daripada versi Rust sebelumnya yang membutuhkan 833ns

Ringkasan performa keseluruhan dan hal yang perlu diperhatikan

Implementasi Waktu
bl/ret normal 969ns
Satu bl, banyak ret 3.85µs
Satu bl, banyak br x30 913ns
Loop biasa dengan b 911ns
Ditulis ulang dalam Rust 833ns
SIMD + loop unrolling manual 94ns
  • Kode SIMD mengubah urutan penjumlahan floating-point
  • Penjumlahan floating-point tidak memenuhi sifat asosiatif, jadi versi SIMD mungkin tidak menghasilkan hasil yang sama dengan kode lurus
  • Ini juga bisa menjadi alasan compiler tidak menghasilkan instruksi SIMD untuk penjumlahan tersebut
  • Semua kode dipublikasikan di GitHub
  • Benchmark bisa direproduksi di mesin ARM64 dengan menjalankan cargo bench

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-05
Komentar di Hacker News

  • Kode optimasi terakhir menyelesaikan penjumlahan array berisi 1024 bilangan floating-point 32-bit dalam 94 ns.
    Selama 94 ns itu, teman lama kita 6502 1 MHz mungkin baru mulai mempertimbangkan apakah perlu memberi sinyal ke chip memori untuk mengambil byte pertama dari instruksi pertama program.
    Namun kode ini sepenuhnya bergantung pada asumsi bahwa ia berjalan di dalam cache. Kalau tidak, bahkan M1 Max yang kuat seperti disebut di artikel pun akan terhenti menunggu pengambilan memori pertama. DRAM itu lambat.

    • Kita beruntung karena sekarang ukuran cache L1 secara keseluruhan sudah sebesar seluruh memori yang dulu bisa dialamati oleh 6502. Kita benar-benar hidup di zaman yang menakjubkan.

  • Raymond Chen sudah membahas hal yang sama hampir 20 tahun lalu: https://devblogs.microsoft.com/oldnewthing/20041216-00/?p=36...

    • Sebagai orang yang memiliki buku cetak referensi instruksi arsitektur x86/64 Intel, yang disebut buku biru tebal, dan membaca datasheet serta dokumentasi dengan saksama, saya selalu berhati-hati setiap kali mendengar pernyataan “secara intuitif sepertinya X, tetapi yang terjadi Y”.
      Selain pemahaman dasar tentang sifat semikonduktor silikon dan doping, hampir tidak ada yang intuitif di sini. Jika Anda belum melihat diagram rangkaian die, wiring, dan jalurnya, hampir tidak ada alasan untuk berharap A lebih cepat daripada B kecuali para engineer dan datasheet menyatakannya secara eksplisit. Saya rasa ini terutama berlaku pada ARM.
    • Tulisan Raymond Chen sangat bagus, dan memberi konteks yang baik untuk menafsirkan artikel ini.
      Yang ditambahkan artikel ini adalah koreksi sederhana dengan mengganti ret menjadi instruksi br lain. Dengan begitu pasangannya kembali “simetris”, dan kita bisa mendapatkan kode yang sedikit lebih cepat tanpa merusak branch predictor.
    • Raymond Chen benar-benar sosok yang berharga. Saya bersyukur Microsoft memberinya keleluasaan untuk terus menulis blog, dan saya belajar sangat banyak dari sana.
    • Tampaknya ini tidak lagi benar pada prosesor x86 terbaru: https://news.ycombinator.com/item?id=40767676

  • Tentu saja apa pun mungkin, dan loop biasa untuk menjumlahkan array memang berbentuk instruksi yang menyuruh komputer mengakumulasi elemen satu per satu.
    Namun, misalnya, membuat empat nilai akumulasi secara paralel dengan SIMD lalu menjumlahkannya di akhir sulit dibilang lebih salah daripada menambahkan elemen satu per satu.
    Penjumlahan floating-point pada dasarnya harus dianggap memiliki rentang galat, dan jawaban dalam rentang itu seharusnya valid. Jika ada pengetahuan khusus tentang floating-point input, bahasa seharusnya menyediakan cara untuk menyatakan maksud itu secara eksplisit. Karena loop paling dasar menjadi default, menurut saya semestinya secara default ia memberikan performa terbaik.

    • Bahkan untuk tugas sederhana menjumlahkan daftar angka, ternyata ada beberapa algoritma penjumlahan.
      Cara naif menambahkan satu per satu dalam loop memang obvious, tetapi ada metode yang lebih canggih yang memberi batas lebih baik atas total galat akumulasi, dan penjumlahan Kahan adalah contoh yang terkenal: https://en.wikipedia.org/wiki/Kahan_summation_algorithm
      Jika datanya streaming, mungkin memang hanya bisa menambahkan satu per satu. Namun jika bisa memakai N buffer berukuran tetap, muncul persoalan seperti subset mana yang dijadikan jumlah parsial saat angka baru masuk, bagaimana menambahkannya ke jumlah akumulasi, dan apakah pilihan itu memiliki perbaikan galat yang dapat dibuktikan.
    • Ini menjadi masalah serius jika perbedaan magnitudo nilai floating-point besar.
      Misalnya, menghitung [1e50, -1e50, 1e3, 1e3] sebagai (((1e50 + -1e50) + 1e3) + 1e3) menghasilkan 2e3, tetapi menghitungnya sebagai ((1e50 + 1e3) + (-1e50 + 1e3)) menghasilkan 0.
      Hal serupa terjadi saat menambahkan banyak nilai kecil ke satu nilai besar, sehingga (((1e3 + 1e3) + 1e3) ... + 1e50) dan (((1e50 + 1e3) + 1e3) ... + 1e3) cukup berbeda.
    • Banyak sekali “seharusnya begitu”, tetapi dalam praktiknya hampir tidak pernah begitu. Informasi yang diberikan oleh ekspresi asal hanyalah urutan operasi aritmetika.
      Jika hasil aritmetika tidak stabil antar-build, itu benar-benar menjadi mimpi buruk. Saat software dibangun ulang dengan input yang sama lalu dijalankan, hasilnya tidak boleh berbeda.
      Dulu saya juga pernah mengalami kasus khas Intel: FPU secara internal memakai register 80-bit sementara memori memakai 64-bit, sehingga ketika waktu pengisian/pengosongan register berubah, waktu pembulatan juga berubah dan hasilnya ikut berbeda. Kita bisa mengatur flag FPU global saat program dimulai untuk memaksa pembulatan pada setiap operasi.
    • Mengurutkan nilai floating-point mengurangi galat. Jadi saya rasa memakai banyak accumulator bisa menurunkan akurasi. Data yang sudah terurut juga bukan hal langka.
      Selalu ada jawaban yang benar, dan menurut saya compiler setidaknya secara default tidak boleh melakukan perubahan yang salah. Namun cara bagi programmer untuk mengekspresikan maksudnya dengan lebih jelas selalu disambut baik.
    • Banyak kode bergantung pada fakta bahwa operasi floating-point bersifat deterministik di dalam arsitektur set instruksi tertentu.
      Menerapkan SIMD pada loop floating-point bisa saja menjadi default, tetapi karena itu akan merusak banyak kode lama dan output sering berubah menjadi non-deterministik, fitur ini menjadi sesuatu yang harus dipilih secara eksplisit oleh programmer.
      Selain itu, banyak programmer mungkin tidak mengetahui fakta ini, sehingga jika float Sum(float[] values) mulai mengembalikan nilai yang berbeda, mereka mungkin tidak punya cara untuk mengetahui bahwa penyebabnya adalah vektorisasi. Karena itu, misalnya, pustaka standar .NET memakai SIMD untuk integers.Sum(), tetapi tidak untuk floats.Sum().

  • Setelah hanya membaca baris “setelah memeriksa akhir loop, eksekusi jatuh langsung ke dalam fungsi foo tanpa branch”, saya langsung berpikir, “Ah, itu masalahnya”
    Saya kira ini akan menjadi pembahasan mendalam tentang heuristik branch predictor yang canggih, tetapi pada akhirnya ini hanyalah pelanggaran heuristik dasar
    Jangan mengira Anda bisa mendapatkan peningkatan kecepatan luar biasa dengan memakai instruksi call/ret yang tidak berpasangan. Branch predictor sudah mempertahankan shadow stack untuk alamat return sejak puluhan tahun lalu

    • Memahami cara kerja branch predictor memang bagus, tetapi banyak orang tidak memahaminya, dan bagi mereka ini bisa menjadi informasi baru dan mungkin berguna. Artikel ini memang bukan untuk Anda, dan itu tidak apa-apa
    • Pada sistem yang memiliki shadow call stack tingkat arsitektur sebagai fitur keamanan, ini bisa merusak eksekusi program secara lebih fundamental, yaitu menyebabkan crash
    • Di sisi lain, tujuan desain RISC adalah meningkatkan performa kode terkompilasi dengan mengorbankan sebagian besar faktor lain
      Jadi risiko semacam ini memang harus didokumentasikan, tetapi perancang seharusnya boleh berasumsi bahwa orang yang menulis assembly secara langsung telah membaca dokumentasinya
      Di sisi lain, Sophie Wilson menulis implementasi BBC BASIC asli untuk ARM, tetapi saat itu belum ada branch predictor. Meski karena 32-bit aturannya berbeda, saya penasaran bagaimana AArch64 membuat kode melambat ketika asumsi arsitektural berubah
    • Meski begitu, artikel ini tetap bermanfaat karena juga menunjukkan bagaimana optimisasi ini dan optimisasi lain dicapai dalam praktik

  • Ini referensi SNL klasik “Do not taunt happy fun ball”: https://www.youtube.com/watch?v=GmqeZl8OI2M

    • Jika happy fun branch predictor mulai mengeluarkan asap, Anda harus segera mengungsi
    • Melihat kalimat “Happy Fun Ball telah dikirim ke prajurit kita di Arab Saudi, dan juga sedang dijatuhkan dari pesawat tempur di atas Irak” membuat rasanya seperti, “Ini sebenarnya tahun berapa!?”
    • Masih legal di 16 negara bagian: https://www.youtube.com/watch?v=2AzAFqrxfeY

  • Jangan sampai terlewat bahwa ini artikel tahun 2023. Sekarang sudah agak usang, dan sejak Rust 1.78 compiler memakai loop unrolling yang lebih agresif dan sedikit SIMD: https://godbolt.org/z/zhbobW7rr
    Artikel asli mengatakan “melihat assembly-nya, terlihat loop unrolling” dan menautkan https://godbolt.org/z/Kv77abW6c, tetapi itu memakai “Rust Nightly” yang terus berubah. Sekarang loop unrolling-nya lebih banyak
    Loop unrolling mulai muncul sejak Rust 1.59: https://godbolt.org/z/5PTnWrWf7
    Dari kode GitHub, versi yang dipakai adalah Rust 1.67.0-nightly, versi 2022-11-27

    • Tautannya telah diperbarui agar secara eksplisit memilih Rust 1.67
    • Rust 1.67.0 yang tampaknya dilihat penulis asli menghasilkan keluaran seperti ini: https://godbolt.org/z/4Y61d9seh
      Saya menjalankan benchmark sendiri pada hardware yang sama dengan nightly Rust 1.81 terbaru yang memiliki loop unrolling agresif, tetapi tidak ada perbedaan; kecepatannya sama seperti 1,5 tahun lalu

  • Ini artikel tahun 2023. Diskusi saat itu: https://news.ycombinator.com/item?id=34520498

    • Lebih lengkapnya, itu diskusi Januari 2023 untuk “Do not taunt happy fun branch predictor”, dengan 171 komentar: https://news.ycombinator.com/item?id=34520498
      Tidak masalah jika diposting ulang sekitar setahun kemudian, dan tautan ke thread lama ini untuk pembaca yang ingin tahu lebih jauh

  • Karena saya tidak terlalu akrab dengan assembly ARM/ARM64, saya sempat bingung bagaimana x0 bertambah
    const float f = *data++; menjadi ldr s1, [x0], #4, dan instruksi ini tampaknya membaca nilai sekaligus menambah x0 sebesar 4
    Sepertinya nilai negatif juga bisa dipakai, jadi traversal mundur pun mungkin. Cukup keren. Di x86_64 sepertinya tidak ada satu instruksi tunggal yang membaca sekaligus menambah

    • lods dan stos masing-masing melakukan baca/tulis sekaligus increment pada rsi atau rdi. Ada juga movs yang menyalin antara dua alamat memori sambil melakukan increment
      Biasanya dipakai bersama rep untuk mengulang sebanyak rcx kali. Misalnya memset 10 byte bisa berbentuk mov rcx, 10, mov rdi, dest, mov rax, 0, rep stosb
      Jika memakai sufiks w, d, q, masing-masing akan maju 2, 4, dan 8 byte

  • Artikelnya bagus, tetapi sayang tabelnya terus berganti antara satuan µs dan ns, sehingga sulit dipindai untuk dibandingkan

    • Peralihan dari C ke Rust di tengah artikel juga agak membingungkan

  • Saya terkejut mereka tidak mencoba cara yang kurang cerdik terlebih dahulu sebelum mengoptimalkan kode
    Jika assembly ditulis ulang, di bagian bawah loop hanya dibutuhkan satu branch, dan untuk X1 pun pengurangan untuk perbandingan serta decrement terpisah bisa diganti dengan satu operasi ALU
    Lebih jauh lagi, foo bisa saja di-inline, dan instruksi RET juga bisa dihilangkan tanpa trik BL/RET yang tidak berpasangan. Saya belum menjalankan benchmark sendiri, jadi tidak tahu seberapa cepat hasilnya dalam praktik

    • Ada typo. Baris yang ditulis cbnz seharusnya cbz. CBZ melakukan branch ke label jika register bernilai 0, sedangkan CBNZ melakukan branch jika bukan 0