Mengapa Harus Menghindari Optimasi Perpindahan Kondisional `mix()+step()` di Shader

• Di shader GPU, kode yang memilih nilai dengan operator ternary atau if sederhana biasanya diproses bukan sebagai percabangan kondisional, melainkan sebagai perpindahan kondisional (select)
• Meski diubah menjadi step() dan masking aritmetika, tidak ada branch yang hilang, sehingga asumsi yang disebut optimasi penghapusan branch itu sendiri tidak tepat
• Pada output compiler AMD dan Microsoft, yang muncul adalah perbandingan dan instruksi mask/perpindahan kondisional, tanpa instruksi jump atau branch
• Versi step() membuat mask 0.0/1.0 lalu menyusun hasil dengan perkalian dan penjumlahan, sehingga menambah operasi yang tidak perlu dibanding kode yang langsung memakai perpindahan kondisional
• Percabangan GPU yang melewati blok komputasi besar sesuai kondisi tetap berguna, tetapi untuk pemilihan nilai sederhana, lebih aman memeriksa kode mesin yang dihasilkan

---

Pemilihan nilai sederhana bukan percabangan GPU

• Fungsi contoh snap45() menghitung x = abs(v.x) dari vektor masukan, lalu mengembalikan salah satu dari tiga hasil vec2 dengan dua operator ternary
• Logika yang sama tetap berlaku meski ditulis dengan pernyataan if biasa
• “Optimasi” yang menjadi masalah adalah cara mengganti operator ternary dengan step() dan komposisi bobot
  • w0, w1, w2 dibuat dengan step()
  • res0, res1, res2 masing-masing dihitung
  • hasil akhir disusun dengan w0*res0 + w1*res1 + w2*res2
• Transformasi ini berangkat dari kesalahpahaman bahwa kode asli membuat branch kondisional
• Pemilihan nilai register sederhana tidak mengubah instruction pointer, juga tidak menyebabkan misprediksi, pipeline flush, atau invalidasi instruction cache
• Branch GPU yang sesungguhnya tetap bisa cepat dan berguna saat melewati blok komputasi besar berdasarkan kondisi
• Namun, untuk kasus seperti contoh yang hanya memilih nilai sederhana atau hasil komputasi, bisa dikatakan tidak muncul branch pada kode mesin yang dihasilkan

Perbedaan yang ditunjukkan output compiler

• Kode operator ternary GLSL asli diubah compiler AMD menjadi perbandingan dan instruksi mask kondisional
  • perbandingan: v_cmp_gt_f32, v_cmp_ngt_f32
  • mask kondisional: v_cndmask_b32
• Output compiler Microsoft juga menunjukkan struktur yang sama
  • perbandingan: lt
  • perpindahan kondisional: movc
• Pada output kedua compiler, tidak ada instruksi jump/branch

Mengapa pendekatan step() lebih mahal

• Pendekatan berbasis step() mula-mula membuat mask 0.0 atau 1.0 dengan perpindahan kondisional, lalu mem-mask beberapa hasil kandidat dengan perkalian dan penjumlahan
• Kode asli langsung memilih nilai yang diperlukan dengan perpindahan kondisional, sehingga lebih hemat dibanding pendekatan step() yang menambahkan pembuatan mask dan komposisi aritmetika
• Di berbagai hardware, versi berbasis step() dapat terukur jauh lebih lambat daripada versi asli
• Sebagian pemanggilan abs() GLSL pada kode contoh bukan instruksi GPU terpisah, melainkan masuk sebagai modifier instruksi, sehingga dalam kasus seperti ini pemanggilan abs() bisa dianggap nyaris gratis
• Menyarankan float a = mix(b, c, step(y, x)); sebagai optimasi dari float a = x < y ? b : c; adalah pendekatan yang keliru

[GN⁺]

Komentar Hacker News

• Kesimpulan TFA tampaknya benar, tetapi argumennya akan lebih kuat kalau tidak hanya menampilkan hasil code generation dari versi yang lebih baik, melainkan hasil code generation dari kedua versi
  Dalam kutipannya tertulis “versi yang diklaim telah dioptimalkan jauh lebih lambat daripada versi asli… membuang dua perkalian dan satu atau dua penjumlahan… mari lihat machine code yang dihasilkan”, tetapi yang benar-benar ditampilkan hanya versi bagus yang tidak punya perkalian atau penjumlahan
  Itu hanya membuktikan bahwa versi bagusnya baik-baik saja, belum membuktikan bahwa versi buruknya memang lebih buruk

  • Poin utamanya adalah conditional tidak menghasilkan branch sungguhan
    Kalaupun kode hasil generate dari versi lain ditampilkan, kemungkinan besar itu hanya menunjukkan bahwa kodenya lebih panjang, dan karena versi itu juga tidak diharapkan menghasilkan branch, nilainya mungkin tidak terlalu besar
  • Kode hasil generate untuk RDNA 1 ada di sini: https://shader-playground.timjones.io/5d3ece620f45091678dcee...

• Akan bagus kalau ada cara yang baik untuk mengetahui kapan if benar-benar memaksa branch dan kapan tidak
  Alasan orang memakai mix/lerp, yang mungkin lebih mahal, adalah karena mereka takut muncul branch meski harus menerima sedikit overhead
  Bagus bahwa kode yang paling jelas seperti v = x > y ? a : b; ternyata bekerja dengan baik, tetapi cukup menggelisahkan bahwa sintaks if yang sama kadang berarti branch dan kadang tidak
  Dalam konteks yang benar-benar tidak boleh melakukan branch, rasanya akan bagus jika ada keyword berbeda untuk branch-if dan if non-branch; keyword non-branch harus membuat kompilasi gagal jika compiler tidak bisa membuatnya tanpa branch, sedangkan keyword branch sebaiknya memberi peringatan jika bisa dibuat tanpa branch

  • Latar belakangnya adalah dokumentasi yang membingungkan dari NVIDIA dan compiler cg/CUDA
    Awalnya mereka tidak ingin menakut-nakuti programmer, jadi menyembunyikan model eksekusinya dan menjelaskannya dengan abstraksi “thread”; kemudian dalam promosi GPU pun terus memakai gaya “ada sangat banyak CUDA thread”
    Akibatnya muncul takhayul aneh dalam coding GPU
    Pada kenyataannya, sering kali bagus jika kode memiliki branch, dan branch itu sendiri cepat
    Masalahnya adalah lane SIMD tidak bisa masing-masing keluar ke branch yang berbeda, sehingga compiler, alih-alih memakai branch, mengeluarkan kode untuk kedua sisi lalu mem-mask hasilnya sesuai kondisi
    Karena itu, perhitungan berbasis input shader, vertex, indeks compute shader, dan semacamnya tidak benar-benar melakukan branch, melainkan dijalankan berurutan dengan masking
    Dalam contoh TFA juga, kedua nilai pada operator ? sama-sama dihitung, dan conditional terhadap nilai SIMD umumnya juga begitu
    Memang bisa saja ada branch pintas yang melewati perhitungan dengan cepat ketika semua lane memiliki nilai yang sama, tetapi secara umum sisi true/false sama-sama dihitung
    Hanya conditional berbasis register skalar, yaitu konstanta shader atau nilai uniform, yang menghasilkan branch sungguhan, dan branch seperti ini sangat cepat
  • Hal yang sama juga berlaku pada CPU skalar
    Misalnya, instruksi CMOV diperkenalkan pada core P6 tahun 1995
    Branch juga mahal pada arsitektur skalar, dan compiler berusaha semaksimal mungkin menentukan kapan harus memakai strategi pengganti
    Kadang salah, tetapi tidak terlalu sering
  • Di GPU, justru harus dilihat sebaliknya
    Conditional move adalah default, dan branch sungguhan adalah optimisasi performa yang hanya mungkin ketika itu adalah branch uniform, saat seluruh workgroup menuju arah yang sama
  • Bisa dibayangkan contoh seperti ini: a = f(z); b = g(z); v = x > y ? a : b;
    Jika biaya pemanggilan f() dan g() relatif besar, apakah akan mengeluarkan kode conditional atau menghitung keduanya lalu memilih hasilnya menjadi soal trade-off
    Ini bukan pilihan sederhana, dan keputusannya diambil oleh compiler
  • Akan menarik jika bahasa shader punya fitur seperti itu
    Semua fungsi dalam kode bisa dibedakan seperti diberi warna boleh branch/tidak boleh branch, dan fungsi yang ditandai non-branch dapat dibuat agar if harus dikompilasi menjadi conditional move serta hanya boleh memanggil fungsi non-branch

• Sebagian besar mitos “branch di GPU itu lambat” berasal dari fakta bahwa dulu, pada era PlayStation 3, hal itu memang cukup lambat
  PS3 memakai GPU NVIDIA RSX, dan setahu saya dokumentasinya menyebut branch 6 siklus, tetapi pengukuran nyata selalu keluar lebih lambat dari itu
  Itu terjadi bahkan pada branch yang sepenuhnya coherent, ketika semua thread dalam warp mengambil jalur yang sama; branch incoherent lebih lambat lagi karena instruksi IFEH memakan 6 siklus dan GPU harus menjalankan kedua sisi branch
  Menurut saya, mitos “branch GPU itu lambat” yang bertahan sampai hari ini berawal dari sana
  Branch GPU masa kini, terutama branch coherent, cukup murah

  • Kalau seseorang hanya mengatakan “branch”, sebaiknya diasumsikan maksudnya branch incoherent
    Overhead mekanisme branch masa kini mungkin sudah berkurang, tetapi batasan fisik bahwa throughput di kedua sisi branch turun sesuai rasio thread aktif tetap sama
    Jika kedua sisi branch sama-sama dieksekusi dan panjang instruksinya juga sama, performa rata-rata kedua sisi turun setidaknya menjadi separuh
    Karena itu, keyakinan bahwa branch di GPU lambat bertahan lama, dan sebenarnya memang benar
    Jika memungkinkan, layak berusaha lebih keras menyusun ulang masalah agar tanpa branch
  • Branch coherent hampir seperti “gratis”, tetapi instruksi tambahan meningkatkan tekanan register
    Alasan utama menghindari branch dinamis bukan karena branch itu sendiri pada dasarnya lambat, melainkan lebih dekat ke masalah ini

• Optimasi menghindari branching seperti ini dulu pernah efektif
  Saya pernah memprofilkannya di Xbox 360 dan GPU terintegrasi Intel lama, tetapi sekarang sebaiknya tidak melakukan itu lagi
  Ekstraksi bit dan operasi integer lain juga serupa
  Dulu menirukannya dengan matematika floating-point lebih cepat, tetapi sekarang semua GPU punya operasi integer yang cepat

  • Saya penasaran sejauh mana klaim “sekarang semua GPU punya operasi integer yang cepat” itu benar
    Misalnya, jika melihat RDNA2 ISA, arsitektur PS5 dan Xbox Series S|X, tampaknya untuk integer hanya terlihat instruksi skalar 32-bit
    [0] https://www.amd.com/content/dam/amd/en/documents/radeon-tech...
  • Setidaknya pada GPU “besar”, ini tidak sebesar masalah dulu, tetapi artikel ini sebenarnya bukan tentang menghindari branching itu sendiri
    Kode yang disajikan sudah merupakan kode tanpa branch
    Orang-orang yang memberi saran tampaknya menilai apakah suatu kode adalah kode branch hanya dari ada tidaknya sintaks yang terlihat seperti kondisional di source, lalu mengira mereka menghindarinya sebagai optimasi

• Artikel ini juga relevan: https://medium.com/@jasonbooth_86226/branching-on-a-gpu-18bf...
  “Jika bertanya ke internet cara menulis branch di GPU, mereka bisa menggambarkannya seperti membuka gerbang neraka dan membiarkan iblis masuk. Mereka akan bilang itu harus dihindari apa pun taruhannya, dan bisa dihindari dengan trik matematika aneh seperti operator ternary atau step(). Sebagian besar nasihat ini paling banter sudah usang, dan sering kali benar-benar salah. Mari kita luruskan.”

• Prosesor berubah, compiler juga berubah
  Jika detail seperti ini penting, cara terbaik adalah mendistribusikan beberapa varian dan memilih versi tercepat saat runtime
  Seperti pernah saya katakan beberapa kali dulu, saya pernah menghapus assembly tulisan tangan dan menggantinya dengan C biasa atau kode serupa, lalu hasilnya jauh lebih cepat
  Assembly itu mungkin lebih cepat 10–20 tahun lalu, tetapi sekarang situasinya sudah berbeda

  • Menurut saya, mengetahui versi shader tercepat saat runtime itu sangat rumit
    Saya tidak begitu tahu game atau engine yang benar-benar melakukannya
    Secara prinsip mungkin saja bisa
    Sebagian besar API seperti D3D, GL, dan Vulkan mengekspos performance counter, dan meski keandalannya berbeda tergantung vendor, kita bisa membuat adegan uji representatif lalu memutarnya beberapa kali untuk mengukur optimasi
    Namun banyak game memakai adegan yang dibuat secara dinamis dan shader yang dibuat secara dinamis, sehingga jumlah kombinasi yang harus diuji bisa menjadi hambatan
    Bisa jadi pengguna harus diminta menunggu sampai benchmark selesai
    Jika punya hardware-nya, kita bisa mengukur lebih dulu di beberapa generasi GPU dari tiap vendor dan meng-hardcode hanya keputusan penting, tetapi saya tidak begitu tahu adanya infrastruktur yang sudah ada seperti itu
  • Menariknya, driver NVIDIA melakukan hal semacam itu sampai taraf tertentu
    Mereka mencegat shader game dan menggantinya dengan shader kustom yang dioptimalkan NVIDIA
    Karena itu di changelog driver NVIDIA muncul kalimat seperti “optimasi game X, berjalan 40% lebih cepat”
  • Kalau hanya menambahkan satu shader lagi mungkin tidak masalah, tetapi dalam API grafis “modern” kadang dibutuhkan ribuan permutasi untuk shader yang sama, dan setiap menambahkan satu varian jumlahnya menjadi 2 kali lipat
    Kita juga tidak bisa menghabiskan waktu tak terbatas untuk tiap shader
    Profilkan pada hardware yang Anda pedulikan, dan kalau pilihan tersebut lebih lambat di prosesor masa depan hipotetis, ya mau bagaimana lagi
    Semoga saja prosesor itu cukup cepat sehingga tidak menjadi masalah

• Tampaknya kesalahan dan kebingungan yang ingin diluruskan artikel ini juga terulang di sini
  Artikel ini tidak mengklaim bahwa branch kondisional itu gratis
  Menurut saya, artikel ini juga bukan membahas biaya performa kode branch
  Inti artikelnya adalah bahwa logika kondisional dalam bentuk yang disajikan tidak dikompilasi menjadi kode branch kondisional
  Dan bahwa kita tidak boleh terus menyebarkan saran merugikan untuk memaksakan penyamaran semua ekspresi kondisional yang terlihat
  Untuk kode branch yang sebenarnya, sudah jelas menjalankan kode branch itu lebih kompleks
  Tidak ada branch yang gratis, dan menghindari branch dalam batas yang masuk akal kemungkinan dapat membuat kode apa pun lebih cepat
  Untungnya, kode aslinya sudah merupakan kode tanpa branch
  Seperti biasa, tidak ada tolok ukur universal yang memberi tahu apakah suatu optimasi layak dilakukan
  [0] Di sini, “yang terlihat” itu penting. Maksudnya kasus ketika orang tidak peduli pada kode yang dihasilkan, hanya peduli apakah source code terlihat seperti kondisional atau tidak
  [1] Tentu saja ini bukan sekadar kebetulan. Saya menduga seseorang mengirimkan kepada IQ usulan perbaikan shader code yang tampak jelas, tetapi keliru

• Kalau begitu, mengapa compiler tidak cukup pintar untuk mengenali bahwa versi yang “dioptimalkan” itu adalah kode yang sama?
  Bukankah compiler seharusnya memahami step() dan bisa mengoptimalkan secara terpisah kasus step() = 0.0 dan step() == 1.0?
  Setidaknya satu perkalian bisa dihilangkan, jadi biasanya akan selalu menguntungkan meski akhirnya berubah menjadi load/store kondisional atau hal lain

  • Dalam praktiknya, bisa saja begitu
    Sebagian compiler dalam sebagian kasus sangat mungkin melakukan optimasi semacam ini, tetapi jelas juga mungkin menulis versi yang tidak dipahami compiler
  • Masalah lain dari optimasi adalah tidak boleh terlalu lama untuk mencoba semua kemungkinan
    Sebagian besar optimasi terjadi di sisi driver, dan pekerjaan yang terlalu lama akan muncul sebagai stutter saat kompilasi shader
    Saya tidak bisa mengatakan apakah optimasi ini benar-benar dilakukan atau tidak sekarang, tetapi itu selalu menjadi faktor yang harus dipertimbangkan

• Alasan versi “optimasi” yang bermasalah itu lebih lambat adalah karena fungsi step() sebenarnya diimplementasikan seperti ini:
  float step( float x, float y ) { return x < y ? 1.0 : 0.0; }
  Bagaimana kita tahu apakah fungsi OpenGL memanggil primitif GPU, atau justru diemulasi?

  • Satu-satunya cara adalah, seperti di tulisan asli, mengompilasi shader, mendisassemble-nya, lalu membaca assembly-nya
    Saya sering melakukannya dengan shader HLSL, dan banyak belajar tentang set instruksi virtual
    Misalnya, menarik bahwa GPU punya instruksi sincos, tetapi fungsi trigonometri invers diemulasi saat kompilasi
  • Mengapa perlu tahu, itu tergantung tujuannya
    Jika performa penting, mungkin perlu mengetahuinya
    Namun fakta bahwa step diimplementasikan sebagai fungsi library di atas conditional, bukan instruksi khusus, tidak dengan sendirinya memberi tahu performanya dibanding instruksi khusus, jadi tidak perlu terlalu terpaku pada implementasinya sendiri
    Jika penasaran dengan arsitektur GPU, lihatlah disassembly, kode driver open source, LLVM, dan dokumentasi ISA
  • Selain fungsi-fungsi yang mungkin terlihat di assembly ala PC, saya belum pernah melihat GPU punya primitif khusus
    Setiap kali melihat shader yang didekompilasi, umumnya mirip dengan apa yang kita bayangkan di C
    Spesifikasi seperti OpenGL menetapkan perilaku banyak fungsi bawaan, dan implementasi memenuhinya dengan instruksi assembly standar
    Coba cari situs online yang dapat mendekompilasi ke berbagai arsitektur
  • Ini pertanyaan bagus yang sering muncul di pemrograman secara umum, dan juga alasan utama mengapa saat mengoptimalkan harus mengukur terlebih dahulu
    Biasanya kita tidak perlu tahu atau peduli bagaimana fungsi bawaan diimplementasikan
    Jika sudah memedulikannya, mungkin Anda sedang memikirkan optimasi, dan saat itu jawabannya adalah “ukur dan pastikan mana yang lebih baik”
  • Titik yang membuat saya bingung tampaknya adalah bahwa “branch” punya makna yang lebih terdefinisi secara hardware daripada makna yang saya pelajari dulu
    Dalam makna yang saya pelajari, conditional adalah branch
    Pada level machine code, karena control flow dipilih saat runtime, conditional jump menurut definisi adalah branch
    Menggunakan step() menurut saya bukan mengubah logika menjadi aritmetika, melainkan hanya menyembunyikan logika di dalam pemanggilan fungsi library
    Fakta bahwa step() adalah fungsi bawaan atau fungsi yang muncul di makalah matematika tidak mengubah apa pun
    Dalam matematika, definisi step() pun secara harfiah adalah conditional
    Jika ingin mengoptimalkan dengan benar tanpa conditional, kita harus memilih fungsi kontinu yang mirip dengan hasil yang diinginkan, lalu menyesuaikan parameternya agar sedekat mungkin dengan target
    Biasanya kita memilih polinomial, menjalankan metode aproksimasi iteratif standar, lalu menghasilkan f(x) yang tanpa branch dan hanya berisi penjumlahan, perkalian, serta konstanta yang “anehnya spesifik”
    Saya kurang memahami bagian ketika penulis dengan tegas mengatakan conditional move bukan “branch”
    abs() bisa turun bukan sebagai instruksi GPU melainkan sebagai modifier instruksi dan menjadi gratis, karena representasi komplemen dua pada integer dan representasi floating point IEEE-754 memungkinkan bit tanda diperlakukan sebagai bit paling signifikan
    Jadi abs() cukup selalu membuat bit paling signifikan menjadi 0, atau sekadar memask-nya pada instruksi yang membaca
    Namun step(), operasi ternary arbitrer, dan sejauh yang saya tahu instruksi conditional move, bukanlah kasus khusus seperti itu
    Hal-hal dasar seperti abs(), sqrt(), dan fungsi trigonometri kurang lebih termasuk pengetahuan standar, sedangkan sisanya rasanya belum tentu penting
    step() mau tidak mau harus memiliki conditional di suatu tempat, dan apakah kita melakukannya sendiri, menyerahkannya ke library, atau menyerahkannya ke hardware, sifat dasarnya tidak berubah

• Saya pernah terjebak dalam hal ini
  Claude atau ChatGPT juga sering menyarankannya sebagai optimasi
  Namun setiap kali diukur, performanya turun, kadang cukup besar

  • Itu bukan hal aneh
    LLM hanya mengulang isi korpus latihannya
    Jika sebagian besar internet merekomendasikan hal yang keliru seperti “optimasi” conditional move ini, LLM juga akan merekomendasikannya
  • LLM mengulang apa yang dikatakan orang-orang di internet, dan orang sering keliru