Spice: Teknik paralelisme granular di Zig dengan overhead sub-nanodetik

• Spice adalah proyek riset yang berupaya menjaga overhead di bawah 1 ns meski menambahkan kemungkinan eksekusi paralel ke fungsi di Zig menggunakan heartbeat scheduling
• Desain intinya adalah struktur fallback: fork menandai pekerjaan yang dapat dikerjakan thread lain, tetapi jika tidak ada thread yang mengambilnya, thread saat ini mengeksekusinya sendiri di join
• Dalam benchmark penjumlahan pohon biner 100 juta node, Rayon memiliki overhead 1 thread sekitar 15 ns dan pada 16 thread sekitar 4,5× dibanding baseline, sedangkan Spice pada 16 thread memperoleh peningkatan kecepatan sekitar 11× hampir persis dibanding baseline
• Untuk pekerjaan dengan waktu eksekusi sangat singkat seperti 1.000 node, ada kasus Rayon menjadi total 60× lebih lambat pada 32 thread, sementara Spice tidak memulai multithreading dan menidurkan thread tambahan jika menilai paralelisme tidak diperlukan
• Implementasi saat ini masih kurang pengujian, dokumentasi, dukungan array/slice, dan benchmark tambahan, banyak menggunakan @panic, dan penulis menyatakan bahwa banyak batasan perlu dipahami sebelum dipakai di produksi

---

Masalah yang ingin diselesaikan Spice

• Spice adalah proyek untuk mengimplementasikan paralelisme sangat granular di Zig dengan overhead rendah
• Tujuannya adalah agar pengguna tidak perlu terus khawatir apakah program akan melambat saat paralelisasi ditambahkan
• Untuk memaksimalkan performa, benchmark yang cermat tetap diperlukan, tetapi secara umum Spice dirancang agar penambahan paralelisme hampir tidak menimbulkan overhead nyata
• Proyek ini terutama merupakan proyek riset, dan jika mempertimbangkan penggunaan produksi, batasannya perlu diperiksa terlebih dahulu
• Dalam pembaruan September 2024, diperkenalkan Chili, port Rust dari ide ini

Cara penggunaan dan API inti

• Fungsi paralel Spice menerima *spice.Task sebagai parameter untuk mengoordinasikan pekerjaan
• Pemanggilan rekursif atau pemanggilan fungsi yang dapat diparalelkan harus dilakukan melalui t.call, bukan dipanggil langsung
• fork menyiapkan pekerjaan yang dapat dieksekusi thread lain
• Setelah fork, fungsi juga harus melakukan pekerjaan bermakna secara langsung
• join menunggu apakah thread lain telah menyelesaikan pekerjaan, tetapi dapat mengembalikan null
  • null adalah sinyal bahwa thread lain tidak mengambil pekerjaan tersebut
  • Dalam kasus ini, thread saat ini harus mengeksekusi pekerjaan itu sendiri

Desain “tidak semua pekerjaan berasal dari antrean”

• Ide inti Spice adalah bahwa tidak semua pekerjaan dimulai dari antrean
• fork memberi tahu bahwa ada pekerjaan yang dapat dieksekusi thread lain, tetapi jika thread lain sibuk, thread saat ini menanganinya seperti eksekusi sekuensial semula
• Ketika tidak ada peluang eksekusi paralel, yang dilakukan Spice di hot path hanyalah sekitar push/pop ke antrean, tanpa benar-benar memeriksa isi item antrean
• Koordinasi nyata dengan thread lain terjadi pada heartbeat tetap
  • Kira-kira setiap 100 mikrodetik, thread memeriksa antrean pekerjaannya saat ini
  • Pekerjaan paling atas di antrean diberikan ke thread lain yang sedang menunggu
  • Karena frekuensi heartbeat rendah, meski memakai ratusan ns, overhead total tetap kecil

Perbandingan dengan benchmark Rayon

• Penjumlahan pohon biner 100 juta node adalah kasus di mana operasi aktual sangat cepat sehingga overhead framework paralel tampak besar
• Rayon di Rust dan Spice sama-sama dibandingkan dalam bentuk API fork/join yang mudah dibaca dan dipahami
• Pada benchmark Rayon, overhead diukur sekitar 15 ns
  • Naik dari 7,48 ns menjadi 22,99 ns
  • Pada 4 thread, performanya kembali ke tingkat sekuensial, tetapi memakai CPU 4× lebih banyak
  • Pada 16 thread, peningkatan kecepatan sekitar 14× menurut basis Rayon sendiri, dan sekitar 4,5× dibanding baseline
• Spice menunjukkan peningkatan kecepatan sekitar 11× saat berpindah dari 1 thread ke 16 thread
  • Skalanya sedikit lebih buruk daripada Rayon, tetapi karena overhead rendah, peningkatan kecepatan dibanding baseline juga hampir tetap utuh
• Benchmark dijalankan pada instance c4-standard-16 Google Cloud, di lingkungan 16 core
• Alasan baseline Zig sekitar 2× lebih cepat daripada baseline Rust tidak jelas
  • Menurut compiled assembly, Rust menyimpan 5 register ke stack, sedangkan Zig menyimpan 3 register

Perilaku pada pekerjaan kecil

• Penjumlahan pohon biner 1.000 node adalah pekerjaan sangat singkat dengan total waktu eksekusi di tingkat beberapa mikrodetik
• Dalam kasus ini, Rayon menunjukkan overhead lebih tinggi, sekitar 19 ns, dan performanya memburuk saat thread ditambahkan lebih banyak
• Saat memakai 32 thread pada mesin 16 core, total waktu eksekusi menjadi 60× lebih lambat
  • Tidak bisa disimpulkan bahwa pelambatan yang sama juga terjadi pada mesin 32 core
  • Namun perilaku scaling seperti ini tetap dinilai mengkhawatirkan
• Penilaian paralelisme tradisional menjadi “hanya bernilai jika ada cukup pekerjaan”
  • Kriteria “cukup pekerjaan” mungkin perlu diketahui lewat benchmark per input
  • Pada input seperti pohon biner, yang ukuran totalnya tidak dapat diketahui hanya dari root, sulit menentukan apakah pekerjaannya kecil
  • Jika 90% beban kerja berupa input kecil, pelambatan ekstrem bisa menjadi masalah
  • Saat program berevolusi, kriteria cukup pekerjaan juga berubah
• Pada kasus 1.000 node yang sama, Spice menilai waktu eksekusi terlalu singkat sehingga tidak memulai multithreading
  • Thread tambahan tetap dalam keadaan tidur
  • Core dapat digunakan untuk menjalankan program lain

Perbedaan work-stealing dan Spice

• Spice menyediakan model fork/join, dan model ini biasanya diimplementasikan dengan work-stealing
• Dalam work-stealing umum, setiap thread memiliki antrean pekerjaan lokal; ketika antreannya kosong, ia mencuri pekerjaan dari ujung antrean thread lain
• Inefisiensi work-stealing dapat diringkas menjadi tiga hal
  • Semua pekerjaan menjadi bentuk “pemanggilan fungsi dinamis” generik, sehingga muncul biaya dynamic dispatch
  • Antrean lokal sebenarnya adalah antrean yang bisa dicuri semua thread, sehingga membutuhkan operasi atomik
  • Saat terjadi kontensi antrean, muncul spinning, dan pada kondisi tertentu bisa 10–100× lebih lambat
• Spice mengurangi langsung inefisiensi ini
  • Dynamic dispatch pada antrean pekerjaan hanya digunakan ketika mengirim pekerjaan ke thread lain
  • Pekerjaan yang dilakukan di dalam satu thread menggunakan pemanggilan fungsi biasa
  • Push ke antrean pekerjaan ditangani dengan stack pointer, stack frame saat ini, dan penyimpanan register, tanpa sinkronisasi dengan thread lain
  • Tidak ada spinning karena tidak ada loop while yang berjalan tanpa memanggil wait()

Detail implementasi

• Optimisasi static dispatch

  • Spice menganggap pekerjaan yang di-fork sebagian besar tidak diambil oleh thread lain, lalu menduplikasi jalur eksekusi kode tersebut di dalam fungsi
  • Jika pekerjaan tidak dieksekusi oleh thread lain, program berperilaku seperti versi sekuensial yang hanya menambahkan beberapa branch yang dapat diprediksi
  • Struktur ini menguntungkan optimisasi kode seperti inlining dan eksekusi CPU

• Sinyal heartbeat ber-overhead rendah

  • Heartbeat scheduling melakukan scheduling secara lokal dengan frekuensi rendah
  • Kira-kira setiap 100 mikrodetik, thread melihat antrean pekerjaan lokal dan mengirim pekerjaan ke thread lain
  • Jika memakai 100 ns setiap 100 mikrodetik, overhead totalnya sekitar 0,1%
  • Alih-alih sinyal sistem operasi, ia memanggil tick() secara kooperatif
    • Saat menggunakan helper t.call, tick() dipanggil otomatis
    • Thread heartbeat terpisah secara berkala mengubah nilai atomic heartbeat tiap thread dari false menjadi true
    • tick() membaca nilai ini dan menjalankan kode heartbeat saat bernilai true
  • Fungsi heartbeat harus ditandai cold; jika tidak, overhead menjadi jauh lebih besar

• Mutex global tanpa kontensi

  • Thread pool Spice memiliki satu mutex yang dikunci di beberapa tempat
  • Mutex global menjadi masalah saat thread benar-benar diblokir
  • Di Spice, karena heartbeat, biasanya hanya satu thread yang menjalankan heartbeat
  • Kode pengguna tidak dijalankan saat lock dipegang; lock hanya melindungi baca/tulis memori sederhana yang selesai dalam waktu konstan

• Doubly linked list tanpa branch

  • Spice menggunakan doubly linked list untuk melacak antrean pekerjaan
  • fork() melakukan append di akhir, join() melakukan pop dari akhir jika masih tersisa, dan saat mengirim ke worker latar belakang, pop dilakukan dari depan
  • Append umum membutuhkan kondisi untuk memeriksa apakah list kosong
  • Spice menempatkan node head sentinel yang selalu ada agar list tidak pernah kosong, lalu menjalankan push/pop tanpa branch

• Meminimalkan penggunaan stack

  • Future memiliki status queued atau executing
  • Heartbeat mengubah queued future menjadi executing
  • State tambahan yang diperlukan untuk status executing ditempatkan di struct terpisah yang dialokasikan dari pool untuk mengurangi penggunaan stack pada queued future
  • Ia menggunakan bentuk tagged union manual yang membedakan status queued/executing berdasarkan apakah field pertama prev_or_null bernilai null

• Mengirim nilai melalui register

  • Task memiliki pointer owning worker dan pointer tail antrean pekerjaan
  • LLVM sering menangani penerusan struct melalui stack, sehingga Spice mendefinisikan callWithContext yang menerima worker dan job_tail sebagai parameter fungsi terpisah
  • Fungsi ini selalu dipanggil dengan inline agar parameter pointer dikirim melalui register

Dasar riset dan pekerjaan terkait

• Spice dibuat berdasarkan riset heartbeat scheduling
• “The best multicore-parallelization refactoring you've never heard of” adalah makalah yang memperkenalkan konsep heartbeat scheduling secara singkat; meski berfokus pada satu use case, makalah ini menjelaskannya dengan cara yang dapat digeneralisasi
  • Solusi di makalah ini mengubah kode ke continuation-passing style untuk beralih antara eksekusi sekuensial dan paralel
  • Spice berawal dari eksperimen pendekatan ini, tetapi overhead-nya ternyata melebihi 10 ns
• “Heartbeat scheduling: provable efficiency for nested parallelism” adalah makalah pertama yang memperkenalkan heartbeat scheduling
  • Makalah ini kaya informasi konsep, tetapi implementasinya berbasis integrasi interpreter dan lebih berfokus pada jaminan teoretis
• “Task parallel assembly language for uncompromising parallelism” adalah riset lanjutan yang meningkatkan performa heartbeat dengan bahasa assembly kustom dan OS signaling
  • Dinilai sulit diintegrasikan ke bahasa yang sudah ada

Batasan saat ini

• Spice bisa memiliki perilaku kasar ketika digunakan secara salah
  • Terutama sensitif terhadap cara penggunaan fork dan join
  • Perlu diperbaiki dengan pemeriksaan compile-time, assertion debug-mode, dan perubahan API
• Ada banyak kode concurrency, tetapi cakupan pengujiannya 0
• Belum ada dukungan native untuk memproses tiap elemen array/slice, yang merupakan use case umum paralelisme granular
• Dokumentasi yang baik untuk menjelaskan cara penggunaan masih kurang
• Saat ini pengujian hanya berpusat pada satu benchmark kecil
  • Benchmark tersebut dianggap semestinya representatif, tetapi benchmark tambahan diperlukan untuk memvalidasi hasil
• Banyak menggunakan @panic dalam penanganan error
  • Agar dianggap sebagai library Zig yang layak, penanganan kasus error perlu lebih banyak dipertimbangkan
• Diperlukan benchmark dan pengujian tambahan untuk mengetahui seberapa baik ia bekerja pada ReleaseSafe Zig
• Seluruh codebase sekitar 500 baris, dan saat ini penulis tidak memiliki rencana pengembangan aktif untuk meningkatkan Spice karena keterbatasan waktu
• Perbaikan melalui fork atau implementasi ulang di bahasa lain disarankan

[GN⁺]

Opini Hacker News

• Implementasi ini didasarkan pada heartbeat scheduling, arus riset terbaru, dan mencapai semacam kontrol granularitas kerja otomatis yang dinamis dengan mengamortisasi biaya pembuatan paralelisme
  Makalah terkait:
  (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
  (2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
  (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
  (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf

  • Ini benar-benar menarik, dan saat menulis Spice saya hanya tahu dua makalah pertama
    Saya pasti akan melihat dua makalah terakhir juga

• Saya belum membaca kodenya secara detail, tetapi frasa overhead kurang dari 1 nanodetik terdengar seperti bahasa pemasaran yang menyesatkan
  Sekilas, ini terlihat seperti metrik “waktu per pekerjaan” yang rumit, dihitung dalam situasi ketika jumlah thread jauh lebih sedikit daripada jumlah “pekerjaan”

  • Saya penulisnya
    Saya tahu sebagian orang akan bereaksi negatif terhadap frasa itu, tetapi niatnya adalah membantu orang memahami dengan lebih baik kapan dan bagaimana tepatnya menggunakan Spice dan Rayon
    Saya sarankan membaca dokumen benchmark: https://github.com/judofyr/spice/blob/main/bench/README.md
    Biasanya saat membandingkan kode paralel, yang dibandingkan hanya implementasi sekuensial/acuan dan implementasi paralel yang memakai semua thread (16). Pada kasus 100M, angka Rayon adalah 7,48 ns untuk versi sekuensial dan 1,64 ns untuk Rayon, lalu mudah untuk berhenti dengan kesimpulan “Rayon 4,5 kali lebih cepat pada masalah ini, tetapi memakai 16 thread, jadi kurang cocok.” Itu memang benar, tetapi sulit untuk belajar bagaimana menerapkannya ke jenis masalah lain
    Jika benchmark yang sama dijalankan dengan jumlah thread yang beragam, terlihat hal yang lebih menarik. Scheduler Rayon cukup bagus dalam membagi pekerjaan ke thread terpisah, tetapi mekanisme eksekusi pekerjaan secara keseluruhan memiliki overhead sekitar 15 ns. Walaupun program ini adalah contoh yang sepenuhnya tidak berguna, ada fakta yang bisa dipelajari untuk diterapkan nanti: jika ingin memakai Rayon, kemungkinan unit kerja terkecil harus kira-kira lebih besar dari 7 ns. Kecuali jika mengurangi latensi total lebih penting meskipun harus mengorbankan throughput total
    Dokumentasi Rayon tidak memberikan angka dan hanya mengatakan “secara konseptual, pemanggilan join() mirip dengan membuat dua thread dan menjalankan satu closure pada masing-masing, tetapi implementasinya cukup berbeda dan memiliki overhead yang sangat rendah”: https://docs.rs/rayon/latest/rayon/fn.join.html
    Jika saya ingin menyesatkan, saya akan mengatakan “Spice memberi speedup 10 kali dan Rayon 4,5 kali, jadi Spice dua kali lebih cepat daripada Rayon”
  • Agar “overhead kurang dari 1 nanodetik” menjadi bahasa pemasaran yang menyesatkan, Spice 1 thread - implementasi acuan non-paralel harus lebih besar dari 1 ns
    Hasil pengujian mendukung klaim tersebut: https://github.com/judofyr/spice/tree/main/bench
  • Menurut saya ini juga sama seperti posisi ekologis Rayon yang dikutip
    Strukturnya adalah ketika harus memproses ribuan hingga jutaan pekerjaan, ingin memparalelkannya semaksimal mungkin dalam puluhan core, dan tidak ingin termakan overhead scheduling, maka overhead per pekerjaan menjadi hal yang dipertimbangkan
  • Kemarin saat ini muncul di Reddit, saya menyampaikan kekhawatiran soal benchmark-nya
    Benchmark tersebut mengklaim overhead 0,36 ns per panggilan, tetapi hanya menyertakan fungsi komputasi. Ada thread kedua yang melakukan scheduling, tetapi tidak masuk ke angka overhead. Tampaknya dijalankan pada mesin 8 core dengan hyperthreading, yaitu 16 thread, dan jika diasumsikan 3 GHz, secara harfiah itu overhead satu siklus
    Untuk setiap thread tambahan, overhead bertambah karena kontensi lock. Pada 16 thread, nilainya 3,6 ns, naik 10 kali lipat. Dugaan saya, jika begitu, overhead 0,36 ns berarti mencakup lock tanpa kontensi, tetapi itu mustahil. Ada hal-hal aneh lain juga di data benchmark. Entah saya tidak memahami apa yang sebenarnya diukur, atau mungkin ada bug di kode benchmark
    Jika semua nilainya dikalikan, sepertinya waktunya diukur dalam milidetik. Waktu eksekusi dihitung lalu dikonversi ke milidetik dan menjadi bilangan bulat. Bukankah benchmarker biasanya memakai presisi yang lebih baik dari ini? Mungkin datanya sangat berantakan karena hanya memakai time prog, atau metrik yang dipilih sama sekali tidak berguna untuk tujuan ini
  • Setelah membaca README, menurut saya klaim pada judul dijelaskan dengan sangat presisi tentang apa maksudnya
    Tidak ada judul yang sama sekali tanpa potensi salah paham, dan judul ini cukup baik. Yang saya tangkap adalah bahwa ini pustaka dengan latensi sangat rendah menurut suatu metrik, dan metrik itu bisa diperiksa di README. Cukup jelas

• Saya tidak terlalu akrab dengan bidang ini, tetapi saya suka model concurrency yang disajikan di sini
  README-nya juga ditulis sangat baik; hanya dengan membacanya, saya bisa mendapat gambaran apa yang terjadi. Namun ada beberapa bagian yang membuat saya agak bertanya-tanya. Untungnya kodenya cukup mudah dibaca

  • Saat dibangun dengan zig build dalam mode Debug, hasilnya Baseline,3.92809172, Spice 1 thread,19.1012624
    Saat dibangun dengan zig build --release=safe dalam mode ReleaseSafe, hasilnya Baseline,3.264224280000001, Spice 1 thread,3.78043278
    Jadi Spice mengalami penurunan performa yang cukup besar jika bukan build rilis. Implementasi pembanding tidak melambat sebesar itu dalam mode build Debug Zig
    Versi yang digunakan adalah zig 0.13.0

• Ini pekerjaan riset yang menarik; bukan hanya kodenya, dasar pengambilan keputusannya juga bagus, dan dokumentasinya ditulis dengan baik
  Makalah heartbeat scheduling tahun 2018 juga layak dibaca: https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf

• Daftar batasan proyek: https://github.com/judofyr/spice?tab=readme-ov-file#limitati...

  • Proyek ini bagus, dan penulisnya pantas mendapat banyak pujian karena telah meluangkan waktu untuk membuatnya berjalan dan membagikannya ke komunitas HN
    HN juga dikenal sebagai tempat yang umumnya bereaksi terlalu kritis atau pesimistis
    Saya juga suka bahwa penulis mengakui keterbatasan proyeknya sendiri, sehingga sebagian besar sinisme umum sudah diantisipasi
    Pada bagian “Kurangnya pengujian: Spice memiliki banyak kode concurrency yang rumit, tetapi cakupan pengujiannya 0. Ini harus diperbaiki agar Spice dapat digunakan secara bertanggung jawab untuk pekerjaan penting”, terlepas dari pengujian kebenaran eksekusi pekerjaan penting itu sendiri, menurut saya sebuah library yang mengimplementasikan kode concurrency yang rumit setidaknya harus memiliki regression test
    Dari sudut pandang pengguna akhir, saya bertanya-tanya apa jaminannya bahwa fitur yang berfungsi hari ini tidak akan rusak besok oleh regresi yang halus dan merugikan
    SQLite memiliki kode pengujian dan skrip pengujian 590 kali lebih banyak daripada kode sumber C murninya https://www.sqlite.org/testing.html. Selain stabilitas dan portabilitas, ini juga salah satu dari banyak alasan mengapa SQLite menjadi database tertanam standar de facto di seluruh dunia
    Ini memang contoh yang agak memaksakan perbandingan apel dan jeruk, tetapi poin umumnya tetap berlaku. Regression test melahirkan stabilitas dan kepercayaan pada proyek
    Di tempat saya bekerja, jika regression test dasar benar-benar harus ditunda, biasanya kami membuat tiket lanjutan dalam epic yang sama agar setidaknya ditulis sebelum fitur/epic dirilis

• Menurut penjelasannya, worker menggunakan busy waiting untuk mendapatkan latensi tingkat nanodetik
  Saya penasaran seberapa realistis busy waiting pada aplikasi besar dengan puluhan ribu pekerjaan. Jika pekerjaannya bukan berbasis thread melainkan async, mungkin masih memungkinkan karena hanya ada penunggu sebanyak ukuran N dari thread pool executor. Bagaimanapun, struktur seperti ini akan meningkatkan konsumsi energi
  Terkait hal itu, saya sudah lama bertanya-tanya apakah ada cara bagi produsen pekerjaan untuk membangunkan konsumen lebih cepat tanpa busy waiting. Misalnya, apakah mungkin menjalankan konsumen di dalam time slice milik produsen
  Masih terkait, saya juga bertanya-tanya apakah operasi FUTEX_WAKE di user space bisa memungkinkan biaya membangunkan konsumen dipangkas menjadi separuh dari biasanya, yaitu hanya biaya di sisi konsumen

• Ada juga tautan ke makalah-makalah yang rapi dan bagus
  Namun saya berharap pembandingnya adalah OpenMP tasks. Saya pernah mendengar reputasi bahwa Rayon agak lambat

• Cooperative scheduling adalah dasar dari banyak pola yang menghasilkan metrik bagus

  • Namun ini bukan cooperative scheduling dalam arti pekerjaan saling yield satu sama lain
    Ini terutama cara bekerja sama agar sebagian pekerjaan dapat diserahkan ke thread lain, dan itu pun tidak selalu terjadi, hanya sekali setiap heartbeat. Karena scheduling jarang terjadi, biaya teramortisasinya rendah

• README di bawah bench juga layak dilihat: https://github.com/judofyr/spice/blob/main/bench/README.md