Jangan Lewatkan Struct Lebih Besar dari 16 Byte di AMD64

• Kenaikan peringkat Neat dalam benchmark related_post_gen bukan berasal dari optimisasi tingkat tinggi, melainkan dari perubahan kecil pada ABI: meneruskan array sebagai 3 argumen pointer alih-alih struct 24 byte
• Karena penghitung referensi, array Neat membutuhkan pointer berbasis objek array selain pointer awal dan akhir; berbeda dari array D yang berukuran 16 byte, ini masuk ke jalur penerusan lewat memori pada SystemV AMD64 ABI
• Aggregate tertentu yang lebih besar dari 16 byte saat pemanggilan disalin nilainya ke stack lalu diteruskan sebagai pointer, sehingga kehilangan keuntungan penerusan lewat register dan menambah besar biaya shuffle stack
• Dalam benchmark contoh, meneruskan struct Vector { double x, y, z; } sebagai struct membuat 1 miliar eksekusi memakan waktu 12,3 detik, sedangkan meneruskan field sebagai argumen terpisah menurunkannya menjadi 5,3 detik
• C API harus mengikuti C ABI, tetapi untuk tipe seperti array, tuple, dan sumtype di dalam runtime bahasa, ketika ukurannya melebihi 16 byte, penerusan dengan memisahkan field layak di-benchmark

---

Bottleneck yang Terlihat di Neat

• Neat naik beberapa peringkat dalam benchmark related_post_gen
• Peningkatan performa ini bukan hasil pass optimisasi tingkat tinggi baru, melainkan akibat mengubah cara penerusan array
  • Sebelumnya: argumen struct yang berisi 3 pointer
  • Sesudahnya: meneruskan 3 pointer masing-masing sebagai argumen
• Dibandingkan D, Neat lebih lambat dari perkiraan, dan profiler menunjukkan operasi memindahkan area besar di stack untuk pemanggilan fungsi
• Bottleneck-nya lebih dekat ke biaya penataan ulang stack pada saat pemanggilan daripada komputasi itu sendiri

Mengapa Array Neat Menjadi 24 Byte

• Berbeda dari array D, Neat menggunakan penghitung referensi
• Array Neat berisi 3 pointer berikut
  • Pointer awal
  • Pointer akhir
  • Pointer berbasis objek array tempat reference count disimpan
• Tiga pointer berukuran 24 byte, sehingga mengambil jalur berbeda dalam aturan penerusan argumen AMD64 dibanding array 16 byte yang terdiri dari dua pointer
• Alasan array D cepat dan array Neat lambat adalah karena ukurannya menjadi 24 byte dan melewati batas 16 byte

Batas 16 Byte pada SystemV AMD64 ABI

• Spesifikasi SystemV AMD64 ABI menetapkan bahwa jika ukuran aggregate tertentu melebihi dua eightbyte, seluruh argumen diteruskan lewat memori
• Untuk meneruskan struct lewat memori, sisi pemanggil perlu melakukan hal berikut
  • Mengalokasikan ruang sebesar ukuran struct di stack
  • Mengisi ruang itu dengan nilai yang akan diteruskan
  • Meneruskan pointer ke lokasi struct tersebut ke fungsi
• Dalam kasus ini, nilai harus berada di stack, sehingga ruang optimisasi LLVM menjadi lebih kecil
• Nilai harus disalin dari register ke stack, dan perlu juga dilacak bagian stack mana yang sedang digunakan serta bagian mana yang dapat digunakan kembali
• LLVM menunjukkan hasil yang kurang baik dalam pelacakan penggunaan ulang stack ini

Benchmark Vektor 3 double

• Benchmark menggunakan vektor 3 field berbentuk struct Vector { TYPE x, y, z; };
• TYPE didefinisikan sebagai double
• Dua fungsi melakukan penjumlahan yang sama, tetapi cara meneruskan argumennya berbeda
  • vector_add_struct(struct Vector left, struct Vector right) menerima struct besar sebagai argumen
  • vector_add_fields(...) menerima left_x, left_y, left_z, right_x, right_y, right_z sebagai argumen terpisah
• mode dan panjang eksekusi diterima sebagai argumen command line agar optimizer tidak melakukan constant folding pada seluruh perhitungan
• impl.c dikompilasi terpisah untuk menghindari inlining

clang -O3 impl.c -c -o impl.o
clang -O3 harness.c impl.o -o benchmark
time ./benchmark 0 1000000000
time ./benchmark 1 1000000000

• Hasilnya adalah 12,3 detik untuk penerusan struct dan 5,3 detik untuk penerusan field secara terpisah

Perbedaan yang Terlihat di Assembly

• Versi penerusan struct menggunakan banyak instruksi untuk shuffle stack
• Versi field diuntungkan karena parameter sudah berada di register SSE saat masuk ke fungsi
• Versi penerusan struct harus memuat nilai dari stack setiap kali
• SystemV ABI bertujuan meneruskan nilai lewat register sebanyak mungkin, tetapi dalam kasus ini keuntungan tersebut hilang karena struct lebih besar dari 16 byte
• Dengan mempertimbangkan jumlah register yang tersedia di AMD64, penerusan nilai untuk tipe yang lebih besar dari 16 byte pun tampaknya akan berguna

Situasi yang Menjadi Mirip cdecl

• Cara menulis field ke stack lalu meneruskan pointer pada akhirnya menjadi mirip dengan ABI x86 lama cdecl, yang meneruskan semuanya lewat stack
• cdecl dikenal lambat, dan berbagai calling convention dibuat untuk membuatnya lebih cepat
• Masalahnya adalah AMD64 System V ABI, karena ukuran struct, dalam kasus ini berperilaku seperti cara penerusan lewat stack lama tersebut

Pengecualian Inlining dan LTO

• Dalam kode nyata, semua fungsi seperti ini bisa saja di-inline
• Jika LTO diaktifkan di gcc, perbedaan performa antara kedua versi hilang
• Di clang, hasil yang sama tidak muncul
• Tidak semua fungsi bisa atau harus di-inline

Saran untuk Implementor Bahasa dan Optimisasi API

• Saat memanggil C API, harus mengikuti C ABI
• Namun tipe tingkat tinggi di dalam bahasa non-C tidak harus direpresentasikan sebagai satu struct, meskipun bagi backend terlihat seperti struct
• Implementor bahasa dapat menentukan sendiri cara meneruskan array, tuple, sumtype, dan sebagainya
• Di Neat, tipe-tipe seperti ini yang lebih besar dari 16 byte dipilih untuk diteruskan sebagai field terpisah, dan benchmark menunjukkan manfaatnya
• Jika mengimplementasikan bahasa di AMD64 atau melakukan micro-optimization API, perlu mem-benchmark apakah membagi struct yang lebih besar dari 16 byte secara manual dapat membantu
• Khususnya dalam inner loop, perbedaan performanya bisa lebih besar dari perkiraan

Tambahan: Struct double dan SSE

• Pertanyaannya adalah mengapa struct tidak diteruskan lewat register SSE, padahal double menurut spesifikasi termasuk kelas SSE
• Jawabannya adalah tidak diketahui alasannya, tetapi dalam praktiknya memang tidak diteruskan seperti itu

[GN⁺]

Komentar Hacker News

• Masalahnya di sini adalah SysV amd64 ABI. ABI internal bahasa tidak harus memakai SysV. Kalau tidak diekspos ke pemanggil C SysV, boleh saja memakai konvensi pemanggilan apa pun yang diinginkan
  https://llvm.org/docs/LangRef.html#calling-conventions
  Untuk yang penasaran, perubahan terkait di neatlang ada di sini: https://github.com/Neat-Lang/neat/commit/f4ba38cefc1e26631a5...
  Kelihatannya jauh lebih rumit daripada sekadar mengubah output konvensi pemanggilan LLVM. Mungkin penulis ingin mengekspos tipe-tipe ini ke program C dengan konvensi pemanggilan yang deterministik

  • Sebenarnya bisa dibilang seluruh ABI memang seperti itu. Kalau Anda programmer assembly, Anda tahu ini salah satu buah yang tergantung rendah yang mudah mengalahkan compiler
    Jangan mengikuti kebiasaan secara membabi buta; pilih saja cara yang paling masuk akal untuk situasi tertentu
  • Pertanyaan pertama yang muncul di benak saya ternyata sudah terjawab. Menarik bahwa banyak hal mengikuti sesuatu seperti ABI yang dibuat sejak lama
    Khususnya ABI sering condong ke kompatibilitas dengan CPU yang lebih tua, sementara CPU yang lebih baru mungkin punya ruang perbaikan dengan memakai fitur seperti register ekstensi tanpa perlu mengurangi ukuran struct. Software yang disesuaikan untuk hardware atau generasi tertentu jadi tidak bisa dipakai di sebagian mesin, jadi mungkin tidak terlalu menarik, tetapi akan keren kalau ada compiler yang bisa menghasilkan output seperti itu saat kita ingin mengoptimalkan kode secara ekstrem sesuai kemampuan hardware sistem sendiri

• Biaya penerusan argumen sering kurang dipahami, jadi tulisan seperti ini menyenangkan. Bahkan di tempat seperti Google, objek 24 byte sering diteruskan by value, dan biayanya tersebar luas di semua fungsi sehingga sulit tampak di profiler

  • Penerusan by value dan by reference pada dasarnya memengaruhi ABI/API, jadi menjadi beban kognitif yang cukup besar. Zig berusaha tidak memaksakan ini, sehingga meski “diteruskan by value”, compiler bisa memutuskan untuk sebenarnya meneruskannya by reference
    Namun hambatan seperti ini juga terekspos: https://github.com/ziglang/zig/issues/5973#issuecomment-1330...
  • “Tempat seperti Google” maksudnya pengalaman langsung? Sebagai mantan Googler, saya bisa memastikan ada guideline untuk meneruskan apa pun yang bukan tipe primitif lewat pointer atau reference
    Satu-satunya pengecualian yang terpikir adalah string_view
  • Bagus bahwa ini menyoroti bahwa overhead yang tersebar luas seperti yang tertanam dalam konvensi pemanggilan hampir tidak bisa ditemukan lewat profiling
  • Jika objek 24 byte diteruskan sebagai pointer, trade-off-nya adalah saat objek itu benar-benar perlu dipakai, pointer tersebut harus di-dereference. Namun tidak ada jaminan objek itu berada dekat
    Kalau kurang beruntung, bisa terjadi cache miss dan harus menunggu sekitar 100 nanodetik untuk mengambil objek 24 byte dari memori utama. Kalau objek yang sama diteruskan langsung, ia berada di stack sehingga lebih mungkin ada di cache
  • Saya penasaran apakah C++ ABI juga menumpahkan objek 24 byte ke stack pada setiap pemanggilan. Saya tidak berharap parameter std::string atau std::function akan cepat, tetapi tetap saja mengejutkan

• Saat pertama beralih ke x64, saya sangat mengkhawatirkan objek vec3 di grafis (3 float) yang ukurannya membesar dari sizeof()=12 menjadi 16 byte, jadi saya melakukan banyak benchmark pada engine grafis
  Tidak mengherankan, berkat alignment pembacaan 8 byte, 16 byte lebih cepat daripada 12 byte. Itu berlaku baik secara internal maupun di GPU. Jadi vec3 diam-diam menjadi vec4, dan vec4 terpisah tetap ada. Seperti biasa, yang perlu dilakukan adalah benchmark dari sudut pandang keseluruhan, bukan benchmark lokal

  • Ada efek samping yang sangat bagus karena cocok dengan ukuran SSE. Jadi _mm_load_ps bisa dipakai langsung, kodenya jadi lebih bersih, dan vektorisasi juga jauh lebih mudah
  • Mungkin tidak jauh lebih cepat. Dan terlepas dari apa yang dilakukan terhadap data ini, saya rasa ini juga sangat bergantung pada CPU
    Untuk 16 byte, saya paham banyak akses bisa menjadi 2x8 byte yang aligned atau 1x16 byte, bukan 3x4 byte. Namun pada akses lain mungkin tidak begitu, dan ada juga masalah peningkatan tekanan cache
  • x64 ABI juga jauh lebih baik daripada x86 ABI

• Secara akal sehat, nilai yang diteruskan lewat register bisa dimuat lebih awal berkat speculative execution sehingga lebih cepat daripada penulisan ke stack, dan manipulasi stack lebih cepat daripada alokasi heap
  Karena itu kode spaghetti kotor dengan banyak variabel global bisa sangat cepat, sementara fungsi rekursif yang elegan atau argumen tuple/struct/list bisa luar biasa lambat. Yang pertama jauh lebih mudah dioptimalkan menjadi loop assembly yang rapat

  • Tentu perlu asumsi bahwa kode spaghetti itu mengimplementasikan algoritma yang sama dengan kode elegan
    Kalau kode elegan O(n) dan kode spaghetti O(n^2), perbedaannya bisa terasa. Maintainability juga perlu dipertimbangkan. Dalam satu arti, compiler ada untuk mengubah solusi elegan kita menjadi kode spaghetti
  • “Lewatkan parameter via register, bukan stack” cukup mirip akal sehat, tetapi “parameter yang lebih besar dari 16 byte selalu diteruskan lewat stack” tidak sejelas itu
  • Sebagian CPU modern bisa melakukan memory renaming, sehingga biaya menumpahkan ke stack bisa menjadi lebih murah
    Objek global juga menghambat optimisasi compiler

• Sebagai catatan, di MSVC, ukuran cutoff-nya 8 byte sebelum struct diteruskan lewat stack. Ini detail ABI, jadi jangan bergantung padanya dalam kode portabel
  Namun kalau fungsinya tidak sering dipanggil, tidak perlu terlalu stres. Kalau fungsinya kecil dan sering dipanggil seperti contoh, buat compiler bisa melakukan inline pada kode, misalnya dengan LTO. Dengan begitu, optimisasi yang terbuka jauh lebih berguna daripada meneruskan argumen lewat register

• Tulisan seperti ini saya golongkan sebagai “pengetahuan yang pas untuk jadi sumber masalah”. Walau mengikuti instruksinya dan mengompilasi secara terpisah untuk memaksa compiler membuat fungsi yang bisa dipanggil lewat ABI, LTO bisa membalikkan kesalahan ini.
  Jika program ini dibangun dengan LTO, pada kedua mode ia menjadi jauh lebih cepat daripada mode mana pun pada program tanpa LTO. Kalau programnya sensitif terhadap performa, lakukan profiling, optimalkan bottleneck sampai batasnya, baru setelah itu commit hal seperti membongkar struct menjadi argumen-argumen

  • Saran yang bagus, tetapi saya belum pernah melihat compiler yang membuat hal semacam ini terlihat. Pertama, ini tersebar di seluruh codebase, dan kecuali beruntung menjadi hotspot, saya juga belum melihat profiler yang menunjukkan dampaknya.
    Ini berlaku untuk hampir semua kode yang dihasilkan compiler. Valgrind mungkin bisa mengukurnya, tetapi profiler berbasis sampling mungkin tidak, dan tidak ada alat yang menyoroti masalah code generation yang tersebar
  • Selain itu, sambil berbicara tentang betapa mutlak pentingnya performa, mereka memakai reference counting

• Dalam cdecl calling convention bawaan Windows, struct yang lebih besar dari 8 byte tidak diteruskan lewat register [1]
  [1]: https://learn.microsoft.com/en-us/cpp/build/x64-calling-conv...

• Di amd64, sekalipun memakai SysV amd64 ABI, meneruskan dan mengembalikan struct yang lebih besar dari 16 byte by value sepenuhnya mungkin. Hanya saja lambat.
  Meski begitu, sering kali pass-by-value layak dilakukan demi membuat kode lebih jelas. Tentu bukan dalam kasus ini, tetapi seperti yang ditunjukkan loeg, di dalam bahasa sendiri bisa memakai ABI kustom seperti compiler C++, Go, OCaml, dan SBCL

• Pada contoh yang diberikan, ini bisa diperbaiki tanpa memengaruhi pemanggil dengan mengubah tipe parameter dari “struct Vector” menjadi “const struct Vector &” dan melakukan pass-by-reference.
  Saya sering melihat banyak kode C++ yang punya bug pointer memakai pointer tanpa perlu, padahal pass-by-reference sudah cukup serta lebih mudah dan aman dipakai

  • Tidak. Sebenarnya itulah inti masalah di sini. Berkat ABI, compiler pada dasarnya melakukan persis hal itu.
    Karena ABI mengatakan nilai harus diteruskan sebagai pointer, nilainya harus disimpan di suatu tempat untuk mendapatkan pointer, dan hal yang sama terjadi seperti ketika menuliskan const-ref secara eksplisit. Jika nilai struct diubah menjadi argumen terpisah, argumen bisa diteruskan lewat register
  • Saat menemukan masalah ini, kodenya punya dua puluh atau tiga puluh alloca untuk meneruskan pointer ke byval. Setiap fungsi dimulai dengan alloca terpisah untuk tiap parameter yang diteruskan ke pemanggilan.
    Saya selalu agak berasumsi LLVM akan membersihkan hal seperti ini dengan baik, tetapi ternyata tidak
  • Namun, untuk meneruskan pointer struct ke callee, compiler tetap harus menserialkan tiga register ke stack.
    Manfaat yang dijelaskan adalah sepenuhnya menghindari serialisasi dari register ke stack, dan tampaknya itu tidak bisa dihindari dengan pass-by-reference
  • Ini bukan contoh C++, melainkan contoh C99. Di banyak lingkungan, alat tidak bisa diganti sesuka hati karena inersia minimal sekalipun.
    Jika C++ diperbolehkan, ada lebih banyak opsi seperti argumen move untuk mengurangi penyalinan

• Rule of thumb yang selalu saya dengar di C++ adalah: apa pun yang bukan tipe primitif sebaiknya diteruskan by reference kecuali ada alasan bagus untuk meneruskannya by value, dan jika benar-benar perlu barulah diteruskan sebagai pointer.
  Ini karena ABI dan juga untuk menghindari copy constructor atau move constructor. Detail level rendah yang membosankan, tetapi kalau menginginkan performa tertinggi di C++, ini bagian yang harus diperhatikan. Jelasnya, ini hanya optimasi performa; kode yang meneruskan struct tetap berjalan benar, hanya saja kurang cepat