Mesin Peredvizhnikov: Game engine lock-free yang ditulis dengan C++20

• Sebuah game engine lock-free sepenuhnya yang ditulis dengan C++20, mengimplementasikan model aktor untuk komputasi konkuren di atas primitif coroutine bahasa tersebut
• Dengan menggunakan abstraksi model aktor, pengembang dapat membangun logika paralel yang kompleks sambil tetap terisolasi dari detail sinkronisasi antar-thread
• Implementasi yang sepenuhnya lock-free memberikan jaminan progres bahkan dalam situasi penghentian thread secara arbitrer, mencegah deadlock, menyediakan latensi yang dapat diprediksi untuk respons terhadap event penting, serta toleransi terhadap kegagalan
• Memberikan jaminan bahwa engine tetap berjalan meskipun salah satu worker thread berhenti secara asinkron
• Implementasinya mencakup Software Transactional Memory, queue lock-free, primitif serialisasi lock-free, std::atomic_shared_ptr, scheduler lock-free, memory allocator lock-free, DAG compile-time, dan lainnya
• Algoritme lock-free, dasar desain, dan benchmark dibahas dalam dokumen Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler
• Untuk membantu desain berorientasi data, engine ini mengimplementasikan database in-memory yang dioptimalkan untuk akses per komponen dan mendukung set data berskala besar
• Database in-memory tersebut berbasis pada struktur data Flat Hash Map dan Bitwise Trie with Bitmap
• Platform yang saat ini didukung hanya Linux, dan build dari source membutuhkan Clang++ 16
• Source code tersedia di bawah lisensi GPLv3, dan izin untuk menggunakan sebagian atau seluruh kode di bawah lisensi lain dapat diberikan berdasarkan kasus per kasus

[GN⁺]

Komentar Hacker News

• Dalam framework Actor, digunakan std::deque biasa sebagai antrean pointer metode, dan saat memasukkan pesan ke antrean, penguncian dilakukan dengan cara Benaphore
  Pada dasarnya seperti Futex, menggabungkan operasi atomik dengan primitif penguncian, tetapi primitif penguncian saya bekerja sebagai kombinasi spinlock/mutex bergantung pada jumlah percobaan ulang. Dalam benchmark, fungsi push pesan sangat jarang terblokir, dan kemungkinan context switch oleh sistem operasi juga rendah, jadi meskipun sesekali thread yang terkunci di-swap out, itu tidak terjadi cukup sering untuk membenarkan biaya algoritma lock-free
  Singkatnya, antrean non-lock-free jauh lebih cepat daripada antrean lock-free, tetapi kita harus menerima adanya latensi panjang yang sangat jarang akibat context switch ketika tidak ada yang berhasil mendapatkan lock. Pada hardware modern, bisa memasukkan 10 juta pesan per detik per worker thread ke antrean

  • Anda mengatakan “pada dasarnya Futex”, tetapi Benaphore adalah ide yang cukup lama, dan Futex bukan sekadar “Benaphore ala Linux”
    Intinya adalah objek kernel, yaitu primitif penguncian terpisah, sebenarnya tidak diperlukan. Di titik inilah ide tersebut berubah dari “cara yang semua orang tahu” menjadi “fitur yang harus segera dimasukkan ke sistem operasi”
    Dalam desain Futex, alih-alih objek sinkronisasi sistem operasi untuk menangani tabrakan, sistem operasi memelihara daftar pemetaan alamat→thread. Jika thread T tidur pada futex di alamat X, daftar tersebut mencatat agar X menunjuk ke T, dan ketika ada permintaan untuk membangunkan futex X, sistem operasi menelusuri daftar itu dan membangunkan T
    Perbedaannya terlihat pada batasannya. Sesuatu seperti Benaphore adalah sumber daya seluruh sistem yang mahal, dan seingat saya BeOS hanya mengizinkan sekitar 65.536 per mesin. Namun Futex hanyalah memori, jadi tidak ada alasan untuk membatasinya
  • Untuk tulisan semenarik ini, seharusnya ada tautan kode. Klaimnya juga akan terbukti, dan orang seperti saya langsung ingin melihat implementasinya karena idenya menarik
  • Sangat bergantung pada detail situasinya. Jika kontensi tinggi, performa bisa turun drastis, dan bahkan instruksi atomik bisa menjadi bottleneck (https://stackoverflow.com/q/2538070)
    Saya pikir pengamatan bahwa dalam banyak kasus cukup memakai lock dan tidak perlu khawatir itu benar. Namun ada juga aplikasi atau situasi yang bisa melakukannya lebih baik. Jika consumer mengambil semua item dalam antrean dengan satu operasi lock, dan producer memberi sinyal kepada consumer, dengan hati-hati efisiensi antrean dan throughput bisa ditingkatkan. Misalnya, jangan mengirim sinyal setiap kali memasukkan item; kirim hanya ketika antrean berubah dari kosong menjadi tidak kosong
  • Bukankah struktur data lock-free lebih bermakna untuk mengurangi dampak kontensi, bukan untuk meningkatkan throughput saat kontensi rendah?
  • “Biaya yang dapat diterima” itu punya pengecualian bagi orang-orang yang memiliki persyaratan kuat bahwa latensi panjang yang tidak dapat diprediksi dan jarang terjadi seperti yang disebutkan tadi sama sekali tidak boleh terjadi

• Scheduler lock-free jelas terlihat menarik, terutama linearizability dari broadcast event yang mencolok. Namun dalam benchmark makalahnya, puncaknya adalah 43.500 pesan per detik untuk 12 pasang actor (dan 12 core?), dan grafik single-core juga sekitar 5.000 pesan per detik, jadi angkanya mengejutkan rendah untuk benchmark jenis ini
  Karena engine ini membutuhkan Linux dan, yang lebih penting, x86 (karena instruksi assembly), saya belum bisa mereproduksinya, tetapi saya mengharapkan setidaknya sekitar 1 juta request per detik per sepasang actor. Jika memikirkan kasus seperti Erlang, angka yang lebih rendah dari itu membuat overhead menjadi terlalu besar hingga sulit diterima
  Engine ini berfokus pada message passing, tetapi dari pengalaman, pendekatan ini sangat sulit ditangani. State machine itu sulit, dan menjadi lebih sulit ketika bekerja dengan beberapa actor turunan. Pada dasarnya, menurut saya actor lebih dekat ke mengisolasi state tanpa lock daripada sekadar message passing. Saya rasa Swift actors melakukannya dengan benar; menggunakan pemanggilan metode alih-alih pesan tidak hanya membuat penalaran lebih mudah, tetapi juga memberi tahu titik-titik tambahan di mana konteks bisa berubah saat runtime, dan tidak selalu harus melibatkan scheduler. Shared state lambat dan merusak skalabilitas
  Belakangan saya membuat library header-only yang mengimplementasikan sesuatu yang mirip dengan Swift actors menggunakan coroutine C++20. Jika tertarik, cari “coroactors”. Saat tidak ada kontensi, sekitar 10 juta request per detik; saat ada kontensi dan bergantung pada scheduler, 1 juta–3 juta request per detik pun saya anggap overhead-nya terlalu besar. Terutama jika dibandingkan dengan pemanggilan metode biasa pada shared state yang dilindungi mutex. Coroutine mudah menular, sehingga semakin banyak fungsi menjadi coroutine async, dan dalam codebase yang tidak sepele, pemanggilan coroutine atau message passing akan banyak terjadi. Jadi overhead harus serendah mungkin; kalau tidak, waktu akan lebih banyak habis untuk berpindah tugas daripada melakukan pekerjaan yang berguna

• Disebut berbasis actor, dan dijelaskan bahwa mengirim pesan ke actor setara dengan menjalankan fungsi actor di bawah mutex. Artinya, meskipun N thread mengirim pesan, hanya 1 thread yang menjalankan kode actor, sehingga diserialisasi seperti mutex
  Jadi secara teknis mungkin saja “sepenuhnya lock-free”, tetapi selama memakai actor, tidak ada peningkatan paralelisasi

  • Tidak selalu begitu. Dalam actor berbasis mutex, jika thread actor terhenti, mutex itu—yakni kode actor—tetap terkunci sampai thread semula dilanjutkan. Karena mutex yang dimiliki thread yang terhenti itu terkunci, meskipun ada lebih banyak paralelisme, kode actor tersebut tidak bisa “dimulai ulang” atau “dilanjutkan”
    Implementasi ini sangat mengandalkan fungsi yang dapat dimulai ulang agar pekerjaan actor yang sudah berjalan tetapi terhenti bisa diambil dan dilanjutkan oleh thread paralel lain. Lihat halaman 3 dari dokumen desain yang bagus ini: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
    Jadi secara ketat mungkin bukan “lebih paralel” (karena jumlah actornya sama), tetapi tampaknya lebih mampu memanfaatkan paralelisme yang lebih besar untuk menyelesaikan kumpulan pekerjaan yang sama
  • Di mana ada pernyataan bahwa “mengirim pesan ke actor setara dengan menjalankan fungsi actor di bawah mutex”? Sepemahaman saya, model actor berarti pengiriman pesan dan eksekusi asinkron. Justru jika ada N actor, N thread bisa berjalan secara paralel
  • Benar bahwa tidak ada peningkatan paralelisasi, tetapi ini juga tidak mengurangi paralelisme. Ini cara lain untuk memikirkan konkurensi, dan menurut saya lebih mudah
    Jika lebih mudah dipikirkan, akan lebih jelas juga di mana kontensi terjadi pada resource yang sama, dan dalam praktiknya membantu meningkatkan paralelisme potensial. Jika Anda melihat peluang tertentu untuk SMP meningkatkan kecepatan, dalam model actor Anda bisa sedikit menyimpang dengan membuat antrean pesan diterima oleh beberapa thread; jika itu tidak mungkin, tinggal tambahkan lebih banyak actor agar data dibagi dengan lebih baik

• Adakah yang pernah men-debug atau memprofiling critical section dengan kontensi tinggi pada STM dibandingkan implementasi mutex tradisional? Pada akhirnya tetap dibutuhkan sesuatu untuk menengahi akses bersamaan ke memori bersama, dan tidak ada makan siang gratis. Mutex sudah sangat teroptimasi, mudah diprofiling, dan dipahami dengan baik
  Sebaliknya, saya tidak yakin STM sudah berada pada level yang sama. Bukankah transaksi bisa dicoba ulang tanpa batas(?)?

  • Dalam kasus ini, penengahnya adalah scheduler. Dialah yang benar-benar memanggil blok asinkron dan, jika gagal, berpotensi mencobanya lagi. Di kode asli ada blok atomik, eksekusi berurutan blok, dan blok dengan state untuk menjamin hanya satu akses pada satu waktu
    Intinya ada di scheduler.cpp dan menggunakan std::coroutines
    Mirip dengan async/await di bahasa lain. Scheduler memiliki antrean task (coroutine) dan thread pool (N>0) untuk menjalankannya
    Di sini, task yang memuat data saling mengirim pesan. Sebagai imbalan meningkatnya penggunaan memori, tidak diperlukan lock
  • Dalam STM tanpa kelaparan, jumlah retry transaksi sebenarnya dibatasi. Salah satu contohnya adalah 2PLSF, dan ada banyak pendekatan lain https://zenodo.org/record/7886718

• Terasa seperti BEAM?
  https://youtu.be/bo5WL5IQAd0?feature=shared

• Saya tidak melihat ada penyebutan soal betapa sulitnya men-debug engine seperti ini

• Saya tidak punya waktu membaca implementasinya, tetapi dari README saja terdengar seperti sistem terdistribusi klasik di antara thread game. Pola seperti retry-backoff sepertinya akan umum

  • Paper-nya menjelaskan lebih rinci tanpa harus menggali implementasi, dan tampaknya cukup lebih maju daripada itu
    https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...

• Lock-free memang terdengar keren, tetapi menurut saya kode yang memakai operasi atomik pada tingkat yang bermakna seharusnya disertai bukti formal, dan kalau bisa bukti yang diverifikasi mesin. Menggunakan urutan atomik yang bukan sequential consistency dengan benar itu terlalu sulit. Saya sudah beberapa kali melihat kode yang salah ditulis, dan bug yang muncul dari situ adalah yang terburuk

• Di mana demo gamenya? Agar bisa dianggap game engine saat ini, dibutuhkan juga tool nyata, exporter seperti Maya atau 3DSMax, serta tool kolaborasi, metrik, notifikasi, dan semacamnya

  • Saya tidak setuju. “Game engine” tidak harus berarti “sesuatu yang bisa menggantikan Unity atau Unreal”

• Disebut “lock-free”, tetapi sepertinya belum
  export std::mutex iolock{};
export std::mutex errlock{};
SDL_PollEvent