Mensimulasikan 20 Juta Partikel dengan JavaScript

 (dgerrells.com)
4 poin oleh GN⁺ 2024-07-09 | 1 komentar | Bagikan ke WhatsApp
  • Berawal dari simulasi partikel JavaScript yang hanya memakai CPU, proyek ini mencapai target 1 juta partikel 60fps di ponsel dan contoh akhirnya diperluas hingga 20 juta partikel
  • Kunci performanya adalah menghindari array objek dan menempatkan data partikel di memori berurutan dengan TypedArray dan SharedArrayBuffer, lalu membagi pekerjaan per core CPU lewat Web Worker
  • Bottleneck sebenarnya lebih banyak muncul pada penggambaran layar dan akses memori dibanding perhitungan posisi partikel, dan penulisan acak ke buffer piksel memicu cache miss CPU
  • Bottleneck dikurangi bertahap melalui buffer piksel per Worker, sinkronisasi postMessage, double buffering, grid jumlah partikel per piksel, dan rendering tekstur GPU
  • Struktur akhirnya: CPU menjalankan simulasi dan GPU merender tekstur grid berukuran resolusi layar; di M1 Mac, 20 juta partikel diproses sekitar 20fps

Target dan Pendekatan Dasar

  • Tantangannya adalah mensimulasikan 1 juta partikel di ponsel pada 60fps hanya dengan JavaScript murni dan CPU, tanpa WebAssembly
  • Array objek JavaScript sederhana dianggap punya keterbatasan dari sisi performa single-core mobile dan tata letak memori, sehingga dipilih pendekatan yang memperlakukan data sebagai array berurutan
  • Dalam komputasi skala besar, array memori berurutan yang rapat penting agar sebanyak mungkin data bisa masuk ke cache CPU
  • Array dan objek biasa di JavaScript sulit dijamin tersusun rapat seperti array atau struct pada bahasa level rendah
  • TypedArray dapat membuat array byte berukuran tetap dan berurutan, sehingga memungkinkan manajemen memori yang relatif level rendah di JavaScript

Implementasi Pertama: SharedArrayBuffer dan Web Worker

  • Data partikel disimpan dengan melapisi Float32Array view di atas SharedArrayBuffer
    • Satu partikel direpresentasikan oleh empat nilai floating-point 32-bit: x, y, dx, dy
    • Buffer datar diindeks dengan stride = 4, byte_stride = stride * 4
  • Simulasi dimulai dari pembaruan posisi sederhana yang melakukan x += dx, y += dy pada setiap frame
  • Multithreading disusun dengan Web Worker dan SharedArrayBuffer
    • Thread utama membagi chunk partikel untuk tiap Worker
    • Worker hanya membaca dan menulis chunk yang dialokasikan untuknya, sehingga menghindari situasi beberapa thread menulis ke lokasi memori yang sama
  • Untuk memakai SharedArrayBuffer di browser, header berikut diperlukan
    • Cross-Origin-Embedder-Policy: require-corp
    • Cross-Origin-Opener-Policy: same-origin
  • Sinkronisasi awal memakai SharedArrayBuffer khusus sinyal terpisah
    • Thread utama menulis sinyal eksekusi untuk Worker
    • Worker memeriksa sinyal dengan setInterval(..., 1), lalu mencatat status siap saat pekerjaan selesai
  • Rendering diproses seperti rasterizer berbasis CPU menggunakan ImageData
    • Satu partikel digambar sebagai satu piksel di layar
    • Partikel di luar layar dilewati untuk menghindari akses di luar rentang array
    • Hasil digambar ke Canvas dengan putImageData
  • Pada profiling awal, pekerjaan Worker hanya beberapa ms, sementara sebagian besar waktu dipakai untuk rendering di thread utama
  • Memori dialokasikan sekali saat awal dan tidak membuat objek baru di loop simulasi, sehingga hampir tidak menghasilkan garbage

Implementasi Kedua: Input dan Interaksi Mirip Gravitasi

  • Data input ditambahkan ke SharedArrayBuffer yang sudah digunakan untuk status simulasi
    • Menyimpan delta time, mouse x/y, status sentuh, serta lebar/tinggi layar
    • Status sentuh adalah nilai yang mirip boolean, tetapi memakai 4 byte
  • Saat layar ditekan, ditambahkan efek partikel tertarik ke titik sentuh
    • Mengacu pada bentuk 1 / r² dari rumus gravitasi nyata, tetapi dimodifikasi untuk interaksi yang menyenangkan, bukan simulasi fisika yang akurat
    • Redaman setara gesekan ditambahkan agar partikel tidak terus berakselerasi tanpa batas dan terlempar keluar layar
  • Warna rendering diubah agar bergantung pada posisi partikel
    • Nilai x / width, y / height digunakan untuk menyesuaikan nilai kanal RGB
    • Jika warna tiap partikel disimpan terpisah, ukuran partikel membesar; karena itu dipakai warna berbasis posisi untuk mengurangi ukuran data
  • Eksperimen dapat dilakukan hingga 2 juta partikel, dan jumlah partikel bisa diubah lewat parameter query count pada URL
  • Pada 10 juta partikel, frame rate turun, dan hasil profiling menunjukkan penulisan piksel ImageData sebagai bagian yang lebih lambat daripada Worker
  • Ketika diubah agar hanya menulis kanal biru dan alpha, bukan seluruh RGB, waktu render di sebagian lingkungan turun dari sekitar 80–90ms menjadi 16–18ms
    • Perbedaan ini bergantung pada CPU, dan tampak lebih besar di desktop Ryzen dibanding M1 MacBook Air

Implementasi Ketiga: Menulis Buffer Piksel di Worker

  • Untuk memanfaatkan lebih banyak core CPU, Worker diubah agar menangani penggambaran piksel selain simulasi
  • Agar beberapa Worker tidak menulis buffer piksel yang sama secara bersamaan, dibuat buffer piksel per Worker
    • Menggunakan SharedArrayBuffer berukuran CPU_CORES * window.innerWidth * window.innerHeight * 3
    • Setiap Worker memiliki satu buffer RGB layar penuh
  • Thread utama menjumlahkan semua buffer piksel per Worker lalu menuliskannya ke ImageData
  • Pada versi ini muncul kedipan layar
    • Thread utama sedang membaca buffer yang sama saat Worker membersihkan buffer pikselnya sendiri dengan fill(0)
    • Rendering sebelumnya juga bisa membaca data lama, tetapi perbedaan antar-frame tidak terlihat; kali ini operasi pembersihan Worker muncul sebagai kedipan di sebagian layar
  • Kandidat solusinya adalah sinkronisasi berbasis Atomics, menunggu Worker selesai lewat postMessage, dan double buffering

Implementasi Keempat: Sinkronisasi Berbasis postMessage

  • Untuk menghilangkan kedipan, array sinyal dibuang dan Worker diubah agar memberi tahu penyelesaian lewat postMessage
  • Thread utama mengelola nilai activeWorkers
    • Setiap kali Worker selesai, ia mengirim pesan dan activeWorkers dikurangi
    • Setelah semua Worker selesai, rendering dilakukan dan requestAnimationFrame berikutnya diminta
  • Dengan cara ini, kedipan teratasi
  • Waktu frame tidak membaik secara signifikan dan bahkan bisa memburuk
    • Karena thread utama tidak melakukan apa pun saat menunggu Worker selesai
    • Untuk 2 juta partikel, ada situasi ketika sekitar 7ms bisa dihemat jika Worker tidak menunggu rendering thread utama
  • Untuk mengurangi bottleneck ini, diterapkan double buffering yang umum di driver grafis

Implementasi Kelima: Double Buffering dan Bottleneck Cache

  • Double buffering adalah cara membuat dua buffer piksel dan mengganti buffer aktif di setiap frame
    • Saat thread utama menggambar satu buffer, Worker menyiapkan frame berikutnya di buffer lain
  • Setelah diterapkan, Worker tidak lagi menunggu rendering thread utama, dan sebagian frame yang sebelumnya melewati 50ms menjadi lebih dekat ke 16ms
  • Kode yang tetap lambat adalah tiga baris yang menambahkan nilai ke kanal RGB buffer piksel
  • Penyebabnya: meskipun data disimpan berurutan, urutan aksesnya tidak berurutan
    • pixelIndex yang dihitung dari x, y partikel tidak selaras dengan urutan array partikel
    • Setiap loop melompat ke lokasi acak di buffer piksel, menghasilkan pola yang mendekati akses acak
  • Pola akses ini menimbulkan cache miss ketika data partikel dan data piksel tidak semuanya muat di cache
  • Contoh perhitungan untuk iPhone adalah sebagai berikut
    • Rumus: screen width * screen height * bytes per pixel + bytes per particle * total particles / number of workers
    • 2532 * 1170 * 3 + 16 * 2,000,000 / 5
    • Hasilnya melebihi 15MB, terlalu besar untuk dimasukkan ke L1 cache
  • Pada versi ini, di chip M1, simulasi 2 juta partikel memakan sekitar 4ms, akses data piksel sekitar 3,5ms, dan penulisan buffer piksel sekitar 7ms
  • Di ponsel, 1 juta partikel bisa dipertahankan pada 60fps, tetapi di desktop dengan lebih dari 20 thread, thread utama menghabiskan 30ms untuk menjumlahkan lebih dari 20 buffer piksel setiap frame

Implementasi Keenam: Gaya yang Mengembalikan ke Posisi Awal

  • Efek baru membuat partikel ditarik kembali semakin kuat saat semakin jauh dari posisi awalnya
  • Untuk itu, dua nilai posisi awal sx, sy ditambahkan ke partikel
    • Satu partikel memiliki enam float: x, y, dx, dy, sx, sy
    • particleStride = 6, meningkat dari sebelumnya
  • Fungsi perhitungan gaya ditambahkan ke kode Worker, dan objek cache digunakan untuk menghindari pembuatan garbage
  • Hasilnya menciptakan efek visual seperti jeli atau fluida, dengan partikel tampak berpusar seperti kertas atau kain yang diremas
  • Dalam proses ini muncul ide untuk tidak menyimpan buffer piksel per Worker, melainkan menggantinya dengan grid yang hanya menghitung jumlah partikel per piksel

Implementasi Ketujuh: Grid Jumlah Partikel per Piksel

  • Jika hanya menyimpan jumlah partikel pada tiap posisi piksel alih-alih nilai RGB, memori bisa dikurangi menjadi 1/3
  • Karena warna dihitung dari posisi x, y, bukan dari data per partikel, rendering dapat dilakukan hanya dengan hitungan per piksel
  • Diubah agar semua Worker berbagi satu grid jumlah partikel
    • Pekerjaan thread utama untuk menjumlahkan buffer per Worker hilang
    • Masalah biaya penjumlahan render yang membesar saat jumlah Worker bertambah ikut terselesaikan
  • Rumus perhitungan cache baru adalah sebagai berikut
    • screen width * screen height + bytes per particle * total particles / number of workers
    • Untuk iPhone: 2532 * 1170 + 16 * 2,000,000 / 5
    • Sekitar 9,3MB, kira-kira 30% lebih kecil dari sebelumnya, tetapi masih besar untuk L1 cache
  • Rendering menelusuri seluruh piksel, membaca jumlah partikel pada piksel tersebut, menghitung nilai RGB, lalu menginisialisasi ulang grid dengan fill(0)
  • Setelah simulasi, Worker menghitung pCountIndex untuk partikel yang berada di dalam layar dan melakukan activeGrid[pCountIndex]++
  • Perubahan ini sangat membantu saat jumlah Worker banyak, dan semua 24 thread di desktop dapat digunakan
  • Meski begitu, M1 MacBook Air kadang lebih cepat daripada desktop Ryzen 9 3900X
    • Ryzen 9 3900X memiliki L3 cache 64MB, tetapi L1 hanya 64KB
    • M1 generasi pertama memiliki L1 cache 320KB, dengan 128KB untuk data dan 192KB untuk instruksi
    • L1 data cache yang lebih besar tampaknya menguntungkan dalam mengurangi waktu tunggu memori

Batas Optimasi Khusus CPU

  • Setelah berbagai optimasi, diperoleh peningkatan kecepatan sekitar 2 kali dibanding versi multithread pertama
  • Target memproses 1 juta partikel berbasis CPU di ponsel pada 60fps hanya dengan JavaScript tercapai
  • Hasil keseluruhannya tidak tergolong sangat mengesankan, dan dengan bahasa terkompilasi diperkirakan bisa 10 kali lebih cepat
  • Jika instruksi SIMD bisa digunakan dalam tight loop, masih ada peluang menjadi lebih cepat
  • Pada langkah berikutnya, simulasi tetap di CPU sementara hanya rendering dipindahkan ke pipeline GPU tradisional untuk dibandingkan

20 Juta Partikel dan Rendering GPU

  • Perbandingan rendering GPU pertama memakai GPU instancing di threejs untuk menggambar plane/quad bagi tiap partikel
  • Performa cara ini lebih rendah dari perkiraan
    • Instancing threejs harus memperbarui matriks untuk setiap posisi partikel, dan pekerjaan ini dilakukan di single thread CPU
    • Data transformasi partikel harus diunggah ke GPU setiap frame, dan transfer ini lambat
  • Saat mensimulasikan 4 juta partikel di chip M1, 80% waktu frame dipakai untuk mengirim data ke GPU
  • Di desktop, porsi transfer data adalah 30%, tetapi tetap menjadi bottleneck terbesar
  • Alternatifnya adalah memakai grid jumlah partikel yang dibuat sebelumnya sebagai tekstur dan merender quad layar penuh
    • Jumlah data yang dikirim ke GPU dibuat tetap sebesar resolusi layar, bukan jumlah partikel
    • Pada simulasi besar, volume transfer berkurang; pada simulasi kecil, ini menjadi trade-off karena dapat mengirim data lebih banyak
  • Setelah implementasi cepat dengan threejs dan pixel shader kustom, rendering thread utama menjadi hanya beberapa ms terlepas dari ukuran simulasi
  • Dalam struktur ini, Worker berjalan secepat mungkin, dan simulasi terikat langsung pada jumlah core CPU baik untuk skala besar maupun kecil
  • Setiap Worker memakai sekitar 50% waktunya untuk perhitungan angka dan sekitar 50% untuk memperbarui hitungan grid partikel
  • Performa versi akhir adalah sebagai berikut
    • Di M1 Mac saat memakai baterai, 20 juta partikel berjalan sekitar 20fps
    • Desktop memproses sekitar 30 juta partikel pada fps yang mirip
    • Dalam pengujian seorang teman dengan CPU 32-core, jumlahnya mencapai sekitar 40 juta partikel
  • Demo terkait:

Ringkasan

  • CPU dan GPU dapat memproses perhitungan angka dengan sangat cepat
  • Bagian yang lambat adalah memindahkan data, terutama akses memori acak
  • Untuk membuat kode cepat, perlu memahami bagaimana hardware melakukan cache dan memindahkan data
  • SharedArrayBuffer dan Web Worker berguna untuk eksperimen memanfaatkan banyak core di JavaScript
  • Jika WebGPU diadopsi lebih luas, rencananya akan mencoba compute shader

Bacaan terkait

1 komentar

 
GN⁺ 2024-07-09
Komentar Hacker News

  • Akan bagus kalau simulasinya di-embed langsung di dalam blog
    Saya harus scroll cukup lama naik-turun sampai menemukan tautan ke simulasi aslinya
    Bisa saja memilih nilai yang tetap berjalan cukup baik bahkan di ponsel lama, atau dibuat menyesuaikan dengan frame rate, atau cukup menaruh beberapa tautan di bagian atas artikel
    https://ciechanow.ski/ adalah contoh kelas dunia yang menunjukkan betapa kerennya jika simulasi dimasukkan ke dalam artikel
    Dulu semua situs web sering meng-embed elemen interaktif keren seperti ini
    Dan menurut saya simulasi partikel di GPU bisa dijalankan tanpa WebGPU
    Contoh: https://news.ycombinator.com/item?id=19963640

    • Ini salah satu contoh terbaik blog penjelasan yang pernah saya lihat
      Semoga ini menjadi standar berbagi informasi. Kalau sesuatu layak dibagikan, berarti layak juga dibuat mudah dipahami
    • Simulasi fluida itu benar-benar menakjubkan
    • Saya setuju embed itu bagus
      Saya sempat mempertimbangkan untuk meng-embed tiap versi, tetapi khawatir terlalu banyak worker berjalan sekaligus
      Saya berencana memperbarui artikel agar versi final di-embed di bagian akhir
      Blog itu benar-benar bagus; setiap contohnya sangat matang
      Edit: Saya mencoba menambahkan versi embed, tetapi header yang dibutuhkan tidak cocok dengan embed lain, dan versi-versi lama masih terikat ke codesandbox
    • Cukup beri petunjuk, “Kalau ingin mencoba aplikasi finalnya, lompat ke bagian akhir”

  • Saya mencobanya langsung di demo mobile [0], dan cukup mengagumkan
    [0] https://dgerrells.com/sabby

    • Ini juga bekerja dengan beberapa jari
      Luar biasa bisa sejauh ini dengan JavaScript murni, dan karena latensinya makin besar saat jumlah jari bertambah, sepertinya data yang bolak-balik antar-thread juga makin banyak
    • Anehnya terlihat organik, seperti struktur lipid di dalam sup purba
    • Di ponsel saya, Firefox berjalan lebih baik daripada Chrome, jadi cukup memuaskan

  • Murni karena penasaran, saya bertanya-tanya apakah data ini bisa dienkode ke dalam satu angka JS, alih-alih merepresentasikan tiap partikel sebagai empat bilangan floating-point 32-bit: x, y, dx, dy
    Rentang integer aman JS adalah 2^53 - 1 = 9,007,199,254,740,991, sementara rentang Float32Array yang dipakai di artikel adalah dari -3.4e38 sampai 3.4e38
    Misalnya jika posisi layar berupa kanvas 1000x1000, itu bisa direpresentasikan dengan angka 0 sampai 1.000.000, dan bahkan jika ditambah 10 tingkat subpiksel pun menjadi 100.000.000, masih sangat muat dalam rentang JS
    Kecepatan dx, dy juga dihitung sebagai pecahan acak antara -10 dan +10 dengan (Math.random()*2-1)*10, tetapi jika cukup dibatasi ke satu angka desimal, itu bisa diubah menjadi rentang integer -100 sampai +100, dan hanya perlu 10.000 nilai yang mungkin
    Jika keduanya digabung, 10,000 * 100,000,000 = 1,000,000,000,000, yaitu satu triliun angka, sudah cukup untuk merepresentasikan partikel dan masih berada dalam MAX_SAFE_INTEGER JS
    Jadi sepertinya data satu partikel bisa dimasukkan ke dalam satu MAX_SAFE_INTEGER atau satu elemen Float32Array; dengan begitu tidak perlu stride dan konsistensi data juga bisa lebih terjamin
    Namun biaya encoding/decoding mungkin lebih besar daripada penghematan memori, sehingga dari sisi performa bisa jadi sama sekali tidak bernilai

  • Benar-benar keren, tapi saya penasaran dengan bagian ini
    Javascript does support an Atomics API but it uses promises which are gross. Eww sick.
    Selain waitAsync[1], Atomics API tampaknya tidak memakai promise
    Saya pernah memakai Atomics sebelumnya, tetapi tidak perlu menangani kode async/promise
    Saya penasaran apakah secara internal ia memakai promise, atau ada bagian yang saya lewatkan
    [1] https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...

  • Ada juga simulasi yang menangani hampir 20 juta partikel
    Bisa dijalankan dan diprogram: https://tinlizzie.org/~ohshima/shadama2/
    https://tinlizzie.org/~ohshima/shadama2/live2017/
    https://www.youtube.com/watch?v=tqBO_5GMfWw

  • Videonya keren, tetapi tautan codesandbox di try it out here tidak berfungsi di desktop MacOS Chrome
    Muncul error CORS seperti Uncaught ReferenceError: SharedArrayBuffer is not defined dan ERR_BLOCKED_BY_RESPONSE.NotSameOriginAfterDefaultedToSameOriginByCoep

    • Karena editor inline codesandbox menghalangi pengaturan header, pratinjau harus dibuka di tab khusus
      Jika memakai browser yang berfokus pada privasi, bisa saja diblokir
      Ke depannya saya akan mencoba menyertakan contoh embed
      Versi final bisa dicoba di sini: https://dgerrells.com/sabby

  • Luar biasa
    Saya menghabiskan satu jam untuk memahami dan mengutak-atik kodenya, dan membuat implementasi real-time di sini: https://particules.kapochamo.com/index.html

    • Saya terkejut saat pertama kali membukanya
      Benar-benar indah, dan sulit dipercaya bisa menyimulasikan partikel sebanyak ini di JS
    • Keren
      Mengesankan bahwa Anda menggali kodenya sedalam itu

  • Patut dicek apakah chrome://tracing memberi lebih banyak insight
    Saya mengetahuinya dari sini: https://youtu.be/easvMCCBFkQ?t=114

  • Saya ingin segera mengirim ini ke tim UI yang membuat aplikasi React lambat
    JS benar-benar cepat, terutama jika ditulis dengan baik, bisa sangat cepat

    • Masalahnya, JS idiomatis dan JS yang cepat dalam praktiknya hampir bertolak belakang
      JS yang cepat tampak seperti dialek C yang buruk, dan kita tidak boleh melakukan alokasi objek yang dikelola garbage collection, tetapi bahasanya kekurangan alternatif bagus tanpa alokasi
      Dalam aplikasi JS yang kompleks, hampir tidak ada orang yang akan menangani semua alokasi memori sebagai pointer di dalam ArrayBuffer raksasa, dan kalau sudah begitu lebih mudah beralih ke WebAssembly
    • JavaScript mungkin adalah bahasa yang paling banyak menyerap jam kerja manusia untuk berbagai optimisasi engine
      Yang disayangkan adalah kita tidak bisa hanya mengandalkan JS dan harus banyak mencampurnya dengan manipulasi DOM, dan bagian yang biasanya lambat di UI yang kita buat adalah manipulasi DOM itu