Algoritme SIMD yang Dirancang dari Awal

 (mcyoung.xyz)
2 poin oleh GN⁺ 2023-11-29 | 1 komentar | Bagikan ke WhatsApp
  • Codec base64 vb64 yang dibuat dengan std::simd di Rust menjadi kode SIMD yang cepat dan portabel bukan dengan sekadar memvektorisasi loop prosedural apa adanya, melainkan dengan merancang ulang tata letak data dan alur operasi seperti sebuah rangkaian
  • Optimisasi intinya adalah mengurangi stall akibat percabangan dan akses memori, dengan membuat struktur branchless yang menjalankan operasi yang sama terlepas dari input melalui compare, mask, select, dan shuffle
  • Dalam decoding base64, untuk mengubah karakter ASCII menjadi sextet, dibuat perfect hash menggunakan byte >> 4 dan koreksi /, lalu offset dicari dengan lookup table di dalam vektor SIMD dan shuffle
  • Saat mengemas empat sextet 6-bit menjadi tiga byte, lane diperbesar menjadi u16 lalu di-shift, kemudian byte low/high dipisahkan dan potongan byte dari lane yang bersebelahan digabungkan dengan rotate_lanes_left dan OR
  • Dalam benchmark, setelah kombinasi -Zbuild-std, -Ctarget-cpu=native, N = 32 serta optimisasi pemuatan remainder, performanya menunjukkan sekitar 2 kali lebih cepat di hampir seluruh rentang dibanding implementasi base64 baseline di crates.io

Latar belakang fisik mengapa SIMD diperlukan

  • Peningkatan performa komputer tidak hanya terkait CS teoretis, tetapi juga langsung terhubung dengan batasan fisik
  • Moore’s law tampaknya masih bertahan per 2023, tetapi selama 15 tahun terakhir efek Dennard scaling runtuh, sehingga transistor yang lebih padat berujung pada peningkatan kepadatan konsumsi daya
  • Setelah frekuensi clock semakin sulit terus dinaikkan, sejak awal 2000-an arah utama peningkatan performa bergeser ke penggunaan lebih banyak core
  • Multithreading memerlukan kerja sama antarkore sehingga menimbulkan biaya sinkronisasi, dan alur kontrol seperti jump, pemanggilan virtual, serta sinkronisasi menyebabkan stall
  • Penyebab utama stall ada dua
    • Percabangan: alur kontrol seperti if, loop, pemanggilan fungsi, return fungsi, dan switch di C
    • Operasi memori: load/store, terutama akses yang tidak ramah cache

Kode prosedural dan paralelisme tingkat instruksi

  • Core CPU modern tidak mengeksekusi kode baris demi baris, melainkan menerbitkan operasi yang tidak saling bergantung secara bersamaan
  • Operasi yang tidak saling bergantung seperti a = x + y dan b = x ^ y dapat menggunakan rangkaian add dan xor secara bersamaan
  • Cara ini disebut paralelisme tingkat instruksi, dan dependensi yang menghambatnya disebut data hazard
  • Semakin baik CPU memenuhi functional unit, semakin banyak operasi yang dapat diproses per satuan waktu
  • Percabangan harus menunggu perhitungan kondisi sebelum mengambil instruksi berikutnya, sedangkan operasi memori harus menunggu data secara fisik tiba di CPU, sehingga terjadi stall
  • GPU menangani gambar sebagai piksel berbentuk vektor dan banyak menjalankan operasi dengan lokalitas tinggi, sehingga mendekati mesin SIMD yang dirancang untuk operasi batch dan alur kontrol terbatas
  • SIMD adalah single instruction, multiple data, yaitu cara satu instruksi menjalankan operasi paralel pada beberapa lane data

Cara berpikir berbasis lane

  • SIMD dan vector sering digunakan dengan arti yang sama, dan satuan dasar instruksi SIMD adalah vector, yaitu array angka berukuran tetap
  • Setiap komponen dalam vector disebut lane
  • Karena vektor SIMD harus masuk ke register, ukurannya umumnya kecil
    • Lebar vektor maksimum pada lingkungan contoh adalah 256 bit
    • Ini setara dengan 32 byte pada u8x32 atau 4 double pada f64x8
  • Meski vektornya kecil, jika dapat mengurangi beban pemenuhan pipeline hingga 4 kali, hal itu dapat berujung pada perbaikan latency sebesar itu pula

Divide and conquer dilihat dari popcnt

  • Operasi vektor yang paling sederhana adalah bitwise and/or/xor
  • Integer biasa pun dari sudut pandang operasi bitwise dapat dilihat sebagai vektor dengan lane 1 bit
    • Dari sudut pandang ini, i32 sama dengan i1x32
  • popcnt adalah operasi menghitung jumlah bit 1 di dalam integer, dan jika i32 dilihat sebagai i1x32, ini adalah operasi reduce
  • Implementasi sederhana yang mengeluarkan 32 bit ke array lalu menjumlahkannya dapat menghasilkan kode yang buruk
  • Cara yang lebih baik adalah menjumlahkan pasangan bit yang bersebelahan, lalu menjumlahkan pasangan dari pasangan itu, dan seterusnya sambil memperbesar lebar lane
    • Memisahkan bit genap/ganjil dengan mask 0x55555555, 0xaaaaaaaa
    • Menyelaraskan lane dengan shift, lalu menjumlahkannya
    • Setelah itu mengulanginya dalam satuan 2 bit, 4 bit, 8 bit, dan 16 bit
  • Implementasi ini tidak dioptimalkan menjadi instruksi popcnt, tetapi menjadi kode kecil dan cepat pada sistem yang tidak memiliki instruksi tersebut
  • Ini juga dapat diterapkan pada u64 cukup dengan menambahkan satu tahap reduction lagi, dan tidak memerlukan penjumlahan seluruh u64
  • Pendekatan divide and conquer seperti ini adalah pola inti dalam pemrograman SIMD

Alat utama dalam instruction set SIMD

  • Vektor SIMD sebenarnya menyediakan makna yang lebih kompleks dibanding skalar, dan fitur untuk menggantikan alur kontrol yang lambat sangat penting
  • Instruksi yang tersedia sangat bergantung pada arsitektur
    • Banyak core berperforma tinggi di x86 mengimplementasikan AVX2
    • AVX2 menyediakan vektor ymm 256 bit
    • Register itu sendiri tidak memiliki jumlah lane; instruksilah yang menentukan cara interpretasi lane
    • Misalnya, vpaddb menafsirkan ymm sebagai i8x32
  • Operasi yang umumnya dapat digunakan adalah sebagai berikut
    • Operasi bitwise: lebar lane selalu implisit 1 bit
    • Aritmetika lane-wise: penjumlahan, pengurangan, perkalian, pembagian, shift integer, min/max, dan sebagainya
    • Perbandingan lane-wise: membuat mask vector seperti m[i] = a[i] < b[i]
    • select: memilih nilai per lane dari dua vektor dengan menggunakan mask
    • shuffle/swizzle: melihat satu vektor seperti lookup table dan menyusun ulang lane dengan vektor indeks
  • true/false pada mask vector biasanya menggunakan pola bit all-ones atau all-zeros
  • Compare dan select adalah alat inti yang membantu kode SIMD tetap branchless
  • Kode branchless menjalankan operasi yang sama terlepas dari input, dan membuang hasil yang tidak diperlukan dengan sifat seperti x * 0 = 0, a ^ b ^ a = b

Menyesuaikan posisi data dengan shuffle

  • Shuffle adalah alat inti dalam SIMD untuk membuat data berada di “posisi yang tepat”
  • Broadcast atau splat membuat vektor yang semua lane-nya memiliki scalar yang sama, dan dapat dinyatakan sebagai shuffle indeks [0, 0, ...]
  • Interleave atau zip/pack menempatkan lane dari dua vektor a, b secara bergantian
    • c = [a[0], b[0], a[1], b[1], ...]
    • Dapat diimplementasikan dengan shuffle2
  • Deinterleave atau unzip/unpack adalah kebalikan dari interleave
  • Rotate memutar lane dalam bentuk b[i] = a[(i + j) % n], dan ini juga merupakan shuffle
  • Dalam pemrograman SIMD, sering kali blok data yang lebih besar dari integer ditafsirkan ulang dan disusun ulang menjadi blok-blok kecil dengan berbagai ukuran

intrinsics, target feature, portable SIMD

  • Operasi yang dapat digunakan di SIMD berbeda-beda tergantung arsitektur dan instruction set extension
  • x86 bisa memiliki operasi yang tidak ada di ARM, dan bahkan dalam vendor yang sama ada ekstensi seperti Intel AVX-512 yang hanya tersedia pada chip server kelas atas
  • Toolchain menggeneralisasi ekstensi semacam ini sebagai target feature
    • lscpu di Linux menampilkan feature yang dikenali CPU
    • LLVM memilih instruksi secara berbeda sesuai pengaturan feature
    • LLVM hanya dapat menghasilkan kode yang menggunakan ymm jika ada +avx2
  • -march=native atau -Ctarget-cpu=native dapat menghasilkan kode yang bagus untuk mesin tempat build dilakukan, tetapi portabilitas ke prosesor lain bisa menurun
  • Runtime feature detection adalah cara memeriksa kemampuan yang didukung CPU lalu menentukan versi fungsi mana yang akan dipanggil, dan digunakan pada kode yang didistribusikan ke beragam perangkat seperti library kriptografi
  • Kode SIMD di C++ biasanya menggunakan intrinsics seperti _mm256_cvtps_epu32
    • Merepresentasikan operasi level rendah dari instruction set tertentu
    • Tidak selalu dipetakan menjadi satu instruksi tunggal
    • Compiler dapat melakukan optimisasi penggabungan, penghapusan duplikasi, dan pemilihan instruksi
  • Jika harus menulis kode serupa berulang kali untuk berbagai instruction set, keunggulan pemeliharaan dibanding assembly bisa tidak terlalu besar
  • Library portable SIMD adalah pendekatan yang menangani sebagian pemilihan instruksi di level library dan menyerahkan sisanya kepada compiler
  • Implementasi vb64 adalah eksperimen untuk memastikan apakah portable SIMD Rust dapat menghasilkan kode yang kompetitif

Mengubah decoding base64 menjadi SIMD

  • base64 adalah cara mengenkode data biner arbitrer menjadi ASCII
  • Deretan byte input dipandang sebagai vektor bit lalu dibagi menjadi chunk 6-bit yang disebut sextet
  • Nilai sextet dipetakan ke karakter berikut
    • 0..25 → 'A'..'Z'
    • 26..51 → 'a'..'z'
    • 52..61 → '0'..'9'
    • 62 → +
    • 63 → /
  • base64 memiliki banyak varian, tetapi sebagian besar kompleksitasnya sama
  • Ada dua hal yang perlu diperhatikan
    • base64 adalah format yang bit di dalam byte-nya bersifat big endian
    • Panjang input bisa saja tidak habis dibagi 4; secara prinsip disesuaikan ke kelipatan 4 dengan padding =, tetapi pesan dengan padding yang tidak benar pun dapat ditangani
  • decoded length dihitung dengan input / 4 * 3 ditambah panjang sisa sesuai input % 4

Refactoring dasar menuju branchless

  • Decoder base64 sederhana memiliki banyak percabangan
    • Loop yang menelusuri input sebagai chunk
    • Loop byte di dalam chunk
    • match per karakter ASCII
    • return Err saat terjadi error
    • match di dalam decoded_len
    • Kemungkinan pemanggilan Vec::extend_from_slice dan allocator
  • Panduan optimisasinya adalah menghapus semua percabangan
  • match pada decoded_len memetakan nilai input % 4 yaitu 0, 1, 2, 3 menjadi 0, 1, 1, 2
  • Jika ini diubah menjadi mod4 - mod4 / 2, hasilnya menjadi versi branchless
  • LLVM pada dasarnya dapat melipat match menjadi switch table, tetapi di area ini akses memori yang tidak perlu menurunkan performa

Memisahkan loop terpanas

  • Kekuatan SIMD terletak pada pemrosesan banyak data sekaligus sehingga loop dapat di-unroll secara agresif dan dibuat mendekati branchless
  • Tujuan hot loop adalah membaca hingga 4 byte, membuat hingga 3 byte hasil decoding, dan juga memberi tahu apakah ada kesalahan sintaks
  • Ada tiga fakta yang bisa dimanfaatkan
    • Panjang output dapat dihitung dengan decoded_len() yang branchless
    • base64 yang salah dianggap sebagai jalur yang sangat jarang, dan jika posisi error diperlukan, input dapat dipindai ulang setelahnya
    • Karena A pada base64 bernilai 0, padding chunk terpotong dengan A tidak mengubah nilainya
  • decode_hot() dipisahkan dalam bentuk yang memproses empat byte input lalu mengembalikan hasil decoding dan bool keberhasilan
  • Jika bool dikembalikan terpisah alih-alih Option<[u8; 3]>, percabangan if !ok lebih mudah dihapus kemudian
  • Pada versi SIMD, input diterima sebagai Simd<u8, 4>, dan output juga dibuat sebagai Simd<u8, 4> agar sesuai dengan jumlah lane power-of-two
    • Output yang sebenarnya dibutuhkan adalah 3 byte
    • Lane terakhir tidak digunakan

Cara mengubah ASCII menjadi sextet

  • Sebagian besar match yang mengubah karakter ASCII menjadi sextet dapat diekspresikan dalam bentuk byte - C
    • 'A'..'Z' → byte - 'A'
    • 'a'..'z' → byte - 'a' + 26
    • '0'..'9' → byte - '0' + 52
    • '+' → byte - '+' + 62
    • '/' → byte - '/' + 63
  • Caranya adalah membuat vektor offset per lane lalu melakukan ascii - offsets
  • Pendekatan pertama adalah compare-and-select
    • Membuat mask untuk A-Z, a-z, 0-9, +, /
    • Lane yang tidak dipilih oleh mask mana pun dianggap invalid
    • Offset yang sesuai dengan tiap mask di-splat lalu digabung dengan OR
  • Cara ini elegan dan dapat menghasilkan kode yang kompetitif, tetapi membutuhkan total 8 perbandingan dan banyak nilai hidup sehingga dapat menimbulkan register pressure

SIMD hash table dan perfect hash

  • Rentang byte A-Z, a-z, 0-9 masing-masing adalah 0x41..0x5b, 0x61..0x7b, 0x30..0x3a, dan high nibble-nya berbeda
  • + dan / adalah 0x2b, 0x2f, sehingga sebagian besar dapat dibedakan hanya dengan byte >> 4
  • Untuk kasus /, jika dikurangi satu, hasilnya menjadi perfect hash untuk rentang tersebut
  • Pemetaan (byte >> 4) - (byte == '/') adalah sebagai berikut
    • A-Z → 4 atau 5
    • a-z → 6 atau 7
    • 0-9 → 3
    • + → 2
    • / → 1
  • Nilai ini kecil, sehingga offset lookup table dapat dimasukkan ke dalam vektor SIMD dan lookup dapat dilakukan dengan shuffle
  • Ide perfect hash ini diajukan oleh pengguna anonim di GitHub issue
  • Simd::swizzle_dyn() memiliki batasan bahwa array index dan panjang lookup table harus sama
  • Pada metode perfect hash, validation tidak didapat sebagai efek samping dalam proses perhitungan sextet, sehingga validitas byte diperiksa menggunakan exact bloom filter dari GitHub issue yang sama
  • Contoh implementasinya ada di simd.rs milik vb64

Mem-packing empat sextet menjadi tiga byte

  • Tahap menggabungkan empat sextet 6-bit menjadi tiga byte lebih rumit
  • Dengan menjadikan satu sextet input tertentu sebagai all-ones lalu melihat ke mana bit berpindah di output, hubungan penempatannya dapat dilacak
  • Shuffle per byte saja tidak cukup
    • Target yang harus dipindahkan adalah potongan byte
    • Shift saja juga tidak cukup
    • Bit yang overshift harus berpindah ke lane yang bersebelahan
  • Solusinya adalah membuat lane lebih besar
  • Setelah sextets di-cast menjadi vektor u16, lakukan shift per lane
    • input[0] di-shift 2 bit
    • input[1] di-shift 4 bit
    • input[2] di-shift 6 bit
    • input[3] disesuaikan dengan shift 8 bit
  • Pisahkan vektor low byte dan high byte dari hasil shift
  • Dengan hi.rotate_lanes_left::<1>(), sejajarkan potongan di sisi high byte ke lane bersebelahan, lalu gabungkan dengan lo | hi_rotated
  • Cara ini secara aktif memanfaatkan hardware primitive sehingga kodenya kecil dan efisien

Memperluas jumlah lane dan menghapus garbage lane

  • Simd<u8, 4> lebih kecil daripada register vektor minimum 128-bit di x86, sehingga decode_hot() dibuat generic terhadap jumlah lane N
  • Constraint LaneCount<N>: SupportedLaneCount menjamin jumlah lane power-of-two yang kecil
  • Lookup table dan shift table membuat vektor pola berulang dengan helper tiled()
  • Pada N = 4, cukup mengabaikan nilai garbage di lane terakhir, tetapi ketika N membesar, garbage tercampur di every fourth lane
  • Untuk menghapusnya, digunakan shuffle
    • Relasi yang diinginkan adalah shuffled[i] = output[i + i / 3]
    • Menghapus garbage lane dengan melewati setiap indeks keempat
    • Bagian yang overflow adalah 1/4 atas dari vektor output akhir, sehingga diabaikan
  • Dengan cara ini, decode_hot::<32>() dapat mendekode 32 byte base64 secara paralel

Optimasi outer loop

  • decode() juga diubah agar generic terhadap jumlah lane internal N
  • Biaya yang tersisa adalah sebagai berikut
    • Branch perbandingan panjang pada for chunks in ...
    • memcpy variable-length dari [T]::copy_from_slice
    • Branch ok pada setiap loop iteration
    • Kemungkinan pemanggilan allocator dari Vec::extend_from_slice dan memcpy lainnya
  • Karena panjang output sudah diketahui, ruang dialokasikan lebih dulu dengan out.reserve(final_len + N / 4)
  • Selain itu, disediakan ruang slop agar bisa melakukan full SIMD store alih-alih variable-length memcpy
  • Setiap iteration menulis seluruh vektor SIMD, dan write berikutnya bergeser sebesar 3/4 * N sehingga menimpa byte garbage sebelumnya
  • Byte garbage terakhir tidak disertakan dalam Vec::set_len() akhir, sehingga diperlakukan seolah-olah terhapus
  • Walaupun terjadi early return karena if !ok, karena belum di-commit dengan set_len(), out tetap dalam keadaan tidak berubah

Menunda penanganan error ke luar hot loop

  • Tidak return dengan if !ok pada setiap iteration, melainkan mengakumulasikan dengan error |= !ok
  • Tepat sebelum set_len() akhir, status error hanya diperiksa sekali
  • Dengan asumsi sebagian besar blob base64 valid, jalur error didorong keluar dari hot loop
  • Meskipun ada error sintaks, operasi SIMD berikutnya tidak akan misbehave secara arbitrer, sehingga garbage write tidak di-commit dan menghilang
  • Setelah itu, pemanggilan seperti Vec::push() dapat menimpa area buffer yang sama

Unroll and jam dan penanganan remainder

  • Untuk mengurangi variable-length memcpy dari copy_from_slice, diterapkan unroll and jam
  • Loop dibagi menjadi dua bagian
    • Hot vectorized loop: selalu memproses input sepanjang N
    • Cold remainder part: memproses input i < N paling banyak sekali
  • Mengimplementasikan hand-rolled unroll-and-jam dengan Iterator::chunks_exact() milik Rust
  • Di hot loop, Simd::from_slice() dipanggil untuk melakukan satu load berukuran vektor
  • Bentuknya membuat bounds check mudah dihapus oleh compiler

Benchmark dan optimasi manual loading

  • Benchmark mendekode pesan dari panjang 0 hingga sekitar 200 atau 500 byte, dan membandingkannya dengan implementasi base64 baseline dari crates.io
  • Opsi kompilasi yang digunakan adalah -Zbuild-std dan -Ctarget-cpu=native
  • Hasil tuning menunjukkan N = 32 paling baik, menggunakan satu register YMM pada setiap hot loop iteration
  • Awalnya baseline berhasil dikalahkan, tetapi muncul fluktuasi performa berbentuk heartbeat yang berkorelasi kuat dengan data.len() % 32
  • Setelah memeriksa assembly, disimpulkan bahwa copy_from_slice tampaknya di-inline/di-unroll menjadi byte-wise load loop
  • Simd::gather_or() juga dicoba, tetapi menghasilkan assembly yang lebih buruk sehingga tidak digunakan
  • Sebagai gantinya, ditulis fungsi loading manual untuk data variable-length
    • Hot part melakukan load skalar terbesar yang memungkinkan, yaitu load u128, di dalam loop
    • LLVM menurunkan chunk 16 byte menjadi XMM load
    • Remainder menggunakan load u64, u32, u8 yang saling overlap
  • Saat membaca 15 byte, dilakukan read u64 dari p dan u64 dari p + 7, sehingga 1 byte overlap, lalu keduanya digabung dengan OR
  • Untuk 4–7 byte digunakan load u32 yang overlap
  • Untuk 1–3 byte, pembacaan dilakukan dari p, p + len/2, dan p + len - 1, sehingga sebagian byte bisa di-load berulang, tetapi jumlah branch berkurang
  • Setelah kode loading baru diterapkan, variance menjadi sangat kecil, dan hampir di seluruh rentang menunjukkan performa 2× dibanding baseline

Encoding dan web-safe base64

  • Fungsi encoding cukup mengimplementasikan encode_hot() yang menjalankan operasi decode_hot() secara terbalik
  • Perfect hash yang digunakan saat decoding tidak cocok untuk encoding, sehingga diperlukan hash baru
  • Kode loading/storing di sekitar encoder juga sedikit berbeda dari decoder
  • vb64 juga mengimplementasikan encoding routine yang efisien
  • Web-safe base64 adalah varian yang mengganti + dan / dengan - dan _
  • Penyusunan perfect hash untuk web-safe base64 lebih rumit; sebagai contoh, mungkin diperlukan cara seperti (byte >> 4) - (byte == '_' ? '_' : 0)
  • vb64 belum mendukung web-safe base64

Kesimpulan

  • vb64 menyatakan bahwa ini bukan library yang dimaksudkan untuk menyelesaikan bottleneck penting, dan tidak mengetahui tempat nyata di mana base64 decoding benar-benar menjadi bottleneck
  • Kode branchless sering kali berlebihan, tetapi membantu memahami apa yang bisa dan tidak bisa dilakukan compiler
  • std::simd di Rust secara umum bagus dan menghasilkan kode yang sangat baik
  • Ada beberapa rough edge yang diharapkan bisa diperbaiki agar kode SIMD menjadi lebih sederhana, tetapi hasil kerja saat ini dinilai memuaskan
  • SIMD dan optimasi performa adalah topik kompleks yang membutuhkan banyak trik dan pengetahuan hardware, dan banyak di antaranya tidak terdokumentasi

Bacaan terkait

1 komentar

 
GN⁺ 2023-11-29
Komentar Hacker News

  • Menarik melihat portable SIMD benar-benar digunakan, dan ketika benchmark direproduksi di sistem Zen 3, peningkatan kecepatannya ternyata sama
    Di M1 MacBook Pro, pada panjang input 110 byte peningkatan performa mulai dari 1,4x lalu naik bertahap hingga 2x; memang lebih rendah daripada x86_64, tetapi tampaknya targetnya tetap tercapai
    Namun, melihat kodenya mengonfirmasi pengalamanku bahwa Rust punya ergonomi yang cukup buruk untuk pekerjaan terkait SIMD dan pointer, dan lebih luas lagi untuk performance engineering

    • Dari sudut pandang engineer Rust, aku cukup setuju, tetapi pekerjaan dengan pointer dan memori mentah memang sengaja diberi banyak batasan demi keamanan, dan ada sisi bahwa bahasa ini ingin memaksa kita benar-benar memikirkan apa yang sedang dilakukan
      Meski begitu, portable SIMD di Rust masih belum bisa dibilang bagus dibandingkan C++, dan kalau ingin turun ke manipulasi area byte mentah, pointer, dan buffer, kita harus terbiasa dengan Pin, MaybeUninit, dan sebagainya
      portable_simd dan allocator_api sudah bertahun-tahun tetap tidak stabil, hambatan masuknya tinggi, dan terasa lebih canggung; sebagian besar memang by design
      Namun, tidak ada yang mencegah kita membuat abstraksi sendiri agar lebih nyaman dipakai di program kita, atau memakai crate pihak ketiga
    • Aku tidak setuju bahwa ergonominya buruk
      Intrinsic SSE di C++ jauh lebih buruk karena penuh underscore yang jelek dilihat dan namanya juga sulit dihafal

  • Kadang benar-benar mengejutkan ketika kita sudah mengimplementasikan sesuatu sebaik mungkin dengan C++ klasik, lalu seseorang datang dengan versi SIMD yang lebih dari 10x lebih cepat
    Sebagai gantinya, kode seperti ini kurang portabel
    Aku berharap autovectorization dari compiler menjadi lebih baik, dan juga ada dukungan semacam anotasi di level bahasa yang secara lokal mengizinkan penataan ulang sebagian operasi

    • Kode SIMD yang bagus perlu mempertimbangkan dengan saksama bagaimana data ditata di memori
      Compiler tidak bisa membenahi data itu untuk kita di luar konteks yang sangat lokal, jadi autovectorization benar-benar sulit
    • Bahkan jika compiler bisa mengoptimalkan secara sempurna, tetap ada banyak jaminan serial yang tak bisa dihindari
      Misalnya pada for(double v: vec) sum+=v, penjumlahan floating point tidak memenuhi sifat asosiatif, jadi menambahkan nilai secara berurutan tidak sama dengan pendekatan SIMD yang menjumlahkan tiap 8 elemen lalu menggabungkan sisanya
      Dari sudut pandang compiler itu mungkin tampak seperti optimisasi yang jelas, tetapi kecuali kita memberi tahu agar jaminan tertentu dilonggarkan, compiler akan memprioritaskan jaminan semantik serial daripada optimisasi
      Karena itu semuanya jadi berantakan, dan seperti kata janwas, untuk hot path lebih baik memakai library, terutama Google Highway atau Intel ISPC
    • Itu memang salah satu poin dari bahasa pemrograman sistem seperti C++
      Ia berusaha seefisien mungkin dengan portabilitas setinggi mungkin, sambil tetap memudahkan pemrograman yang spesifik ke target saat diperlukan
      Autovectorization memang jauh lebih baik di compiler FORTRAN, karena aliasing tidak diizinkan
      C++ terhambat karena harus mengikuti model memori C
    • Bisa juga langsung pakai CUDA
      CUDA adalah C++ yang dirancang untuk GPU, mesin SIMD pamungkas masa kini, dan ROCm pada dasarnya sangat mirip CUDA untuk AMD
      Secara pribadi aku suka C++AMP dari Microsoft, menurutku itu yang paling mudah untuk mulai dipelajari
      Sayangnya pada akhirnya tidak berhasil mendapat tempat
    • Dalam pengalamanku, hal seperti ini memang sering terjadi
      Selain itu, kalau memakai library pembungkus SIMD, hasilnya sebenarnya bisa dibuat cukup portabel

  • Sebagai catatan kecil, compiler tidak berhasil mengoptimalkan implementasi popcount tersebut menjadi instruksi tunggal, tetapi itu bisa dilakukan pada implementasi lain
    Tentu saja cukup rumit: https://godbolt.org/z/T69KxWWW8

  • Disebutkan bahwa _mm256_cvtps_epu32 merepresentasikan operasi level rendah dari set instruksi tertentu dan dijelaskan sebagai cast float-ke-int milik AVX2, tetapi instruksi itu sebenarnya bagian dari AVX-512
    AVX2 tidak punya cast float-ke-int semacam itu, dan di AVX1 hasil integer-nya signed dengan instruksi _mm256_cvtps_epi32

  • Penasaran bagaimana perbandingannya dengan fastbase64[0]
    Tulisannya sangat bagus dan menyenangkan bisa membaca hal seperti ini secara online, tetapi sulit bagiku untuk ikut berbagi optimisme penulis terhadap library portable SIMD
    [0]: https://github.com/lemire/fastbase64

  • Menurutku ISPC memang lebih baik daripada menambahkan SIMD ke C++ atau Rust
    Ia juga mendukung dynamic dispatch, fitur yang menyakitkan kalau harus diimplementasikan sendiri

    • Kalau itu alat yang membuat orang lebih sering memakai SIMD, pada umumnya itu hal yang baik, tetapi secara pribadi aku lebih suka SIMD terintegrasi dalam toolchain yang sama
      Dengan begitu kita bisa mengirim balik inline call ke C++, memakai template dan class di kode SIMD, dan juga melakukan inline ke beberapa area kode SIMD sekaligus
      Aku setuju bahwa implementasi dynamic dispatch itu sulit, tetapi Highway sudah menangani bagian itu
    • Aku penasaran apakah untuk subrutin kecil seperti di tulisan utama, C++ atau Rust mudah memanggil ISPC

  • Tulisan yang luar biasa, dan meninggalkan kesan kuat seperti, “aku tidak akan pernah bisa sepintar ini”

    • Itu hanya karena ini bukan bidang pekerjaanmu
      Sama seperti kebanyakan orang bukan software engineer atau fisikawan
      Kalau fokus belajar beberapa bulan, kamu mungkin bisa mencapai level yang mirip
    • Kalau ada kesempatan bertemu pemberi kerja atau proyek yang membutuhkan hal seperti ini, kamu mungkin akan bisa “menjadi sepintar ini”
      Pada akhirnya ini soal minat dan kebutuhan
      Aku juga kadang mengerjakan optimisasi performa atau engineering yang lebih dekat ke sistem dan bare metal dalam proyek pribadi, tetapi berharap itu lebih dibutuhkan di pekerjaan
      Hanya saja, sebagian besar pekerjaan di industri memang tidak menuntut itu
    • Coba AoC '23 dengan APL/j/k, BQN, Python/numpy, CUDA dan sebagainya
      Bukan Python idiomatis, melainkan menyelesaikan semuanya dengan numpy
      Seru, bisa mempelajari kecerdikan semacam ini, dan banyak bagian dari tulisan itu terasa sangat alami bila dilihat dari cara berpikir pemecahan masalah di bahasa-bahasa seperti itu
      Lama-kelamaan kamu mulai melihat masalah dalam bentuk seperti itu
    • https://fgiesen.wordpress.com/2016/02/05/smart/

  • Tulisan yang menarik
    Pada contoh pertama di awal, disebutkan bahwa implementasi popcnt yang tidak divektorkan menghasilkan “kode yang, terus terang, buruk sampai terasa konyol”, tetapi dalam mode release dengan target native CPU, fungsi itu tampaknya tervektorkan dengan cukup baik
    https://godbolt.org/z/WE1Eq65jY

    • Kode di bawah ini seharusnya menghasilkan output yang setara
      pub fn popcnt(mut x: u32) -> u32 { x.count_ones() }
      Ini dikompilasi menjadi popcnt eax, edi; ret
      Pada vektor bit besar, implementasi AVX2 bisa lebih cepat daripada POPCNT
      Lihat “Faster Population Counts Using AVX2 Instructions”: https://academic.oup.com/comjnl/article/61/1/111/3852071
      Untuk 32-bit, ukurannya tidak cukup besar, dan kode yang dihasilkan Rust memang benar-benar buruk sampai terasa konyol
    • Idealnya, ini tampaknya harus diturunkan menjadi instruksi popcnt
    • Otomatis vektorisasi kadang berhasil, kadang tidak
      Baru-baru ini saya menulis kode yang perlu menghitung jumlah bit pada mask hasil operasi vektor, dan ini berubah dengan baik menjadi popcnt
      https://godbolt.org/z/zT9Whcnco

  • Karena ada bagian seperti “ini terasa seperti pertanyaan jebakan… bukannya ini cuma add?”, biasanya saya ingin menargetkan representasi vektor menengah dan membiarkan compiler yang memutuskan detailnya
    Misalnya, chip Haswell memiliki beberapa unit eksekusi floating-point per core, dan CPU dapat menjalankan lebih dari satu operasi floating-point terpipeline secara bersamaan, tetapi di antaranya hanya satu instruksi add yang bisa dijalankan
    Jika ada banyak penjumlahan yang tidak bergantung pada hasil sebelumnya sehingga latensi bisa dihindari, instruksi fused multiply-add dengan faktor perkalian 1 juga bisa dikirim untuk menggandakan throughput penjumlahan
    Instruksi itu dapat dijalankan bersamaan dengan penjumlahan floating-point vektor biasa