Bagaimana sistem entitas cache-efisien?

Akhir-akhir ini, saya telah banyak membaca tentang sistem entitas untuk diimplementasikan dalam mesin game C ++ / OpenGL saya. Dua manfaat utama yang sering saya dengar tentang sistem entitas adalah

1. konstruksi mudah entitas jenis baru, karena tidak harus kusut dengan hierarki warisan yang kompleks, dan
2. efisiensi cache, yang saya mengalami kesulitan memahami.

Teorinya sederhana, tentu saja; setiap komponen disimpan secara bersebelahan dalam satu blok memori, sehingga sistem yang peduli dengan komponen itu bisa saja mengulangi seluruh daftar, tanpa harus melompat-lompat di memori dan membunuh cache. Masalahnya adalah saya tidak dapat benar-benar memikirkan situasi di mana ini sebenarnya praktis.

Pertama, mari kita lihat bagaimana komponen disimpan, dan bagaimana mereka saling referensi. Sistem harus dapat bekerja dengan lebih dari satu komponen, yaitu sistem rendering dan fisika perlu mengakses komponen transformasi. Saya telah melihat sejumlah implementasi yang mungkin mengatasi hal ini, dan tidak ada satupun yang melakukannya dengan baik.

Anda dapat memiliki komponen menyimpan pointer ke komponen lain, atau pointer ke entitas yang menyimpan pointer ke komponen. Namun, segera setelah Anda melemparkan pointer ke dalam campuran, Anda sudah membunuh efisiensi cache. Anda dapat memastikan bahwa setiap larik komponen adalah 'n' besar, di mana 'n' adalah jumlah entitas yang hidup dalam sistem, tetapi pendekatan ini sangat memboroskan memori; ini membuatnya sangat sulit untuk menambahkan tipe komponen baru ke mesin, tetapi masih membuang efisiensi cache, karena Anda melompat dari satu array ke yang berikutnya. Anda bisa menyisipkan array entitas Anda, alih-alih mempertahankan array yang terpisah, tetapi Anda masih membuang-buang memori; membuatnya sangat mahal untuk menambahkan komponen atau sistem baru, tetapi sekarang dengan manfaat tambahan membatalkan semua tingkat lama Anda dan menyimpan file.

Ini semua mengasumsikan bahwa entitas diproses secara linear dalam daftar, setiap frame atau centang. Pada kenyataannya, ini tidak sering terjadi. Katakanlah Anda menggunakan renderer sektor / portal, atau sebuah octree, untuk melakukan penyisihan oklusi. Anda mungkin dapat menyimpan entitas secara bersebelahan dalam suatu sektor / simpul, tetapi Anda akan melompat-lompat, suka atau tidak. Kemudian Anda memiliki sistem lain, yang mungkin lebih suka entitas yang disimpan dalam urutan lain. AI mungkin baik-baik saja dengan menyimpan entitas dalam daftar besar, sampai Anda mulai bekerja dengan AI LOD; kemudian, Anda ingin membagi daftar itu berdasarkan jarak ke pemain, atau beberapa metrik LOD lainnya. Fisika akan ingin menggunakan octree itu. Script tidak peduli, mereka harus dijalankan, apa pun yang terjadi.

Saya bisa melihat pemisahan komponen antara "logika" (misalnya ai, skrip, dll) dan "dunia" (misalnya rendering, fisika, audio, dll), dan mengelola setiap daftar secara terpisah, tetapi daftar ini masih harus berinteraksi satu sama lain. AI tidak ada gunanya, jika tidak dapat memengaruhi kondisi transformasi atau animasi yang digunakan untuk rendering entitas.

Bagaimana sistem entitas "efisien cache" di mesin game dunia nyata? Mungkin ada pendekatan hibrid yang digunakan semua orang, tetapi tidak dibicarakan, seperti menyimpan entitas dalam array secara global dan merujuknya di dalam octree?

Dua manfaat utama yang sering saya dengar tentang sistem entitas adalah 1) konstruksi mudah entitas jenis baru karena tidak harus kusut dengan hierarki warisan yang kompleks, dan 2) efisiensi cache.

Perhatikan bahwa (1) adalah manfaat desain berbasis komponen , bukan hanya ES / ECS. Anda dapat menggunakan komponen dengan banyak cara yang tidak memiliki bagian "sistem" dan mereka bekerja dengan baik (dan banyak game indie dan AAA menggunakan arsitektur seperti itu).

Model objek Unity standar (menggunakan GameObjectdan MonoBehaviourobjek) bukan ECS, tetapi desain berbasis komponen. Fitur Unity ECS yang lebih baru tentu saja merupakan ECS yang sebenarnya.

Sistem harus dapat bekerja dengan lebih dari satu komponen, yaitu sistem rendering dan fisika perlu mengakses komponen transformasi.

Beberapa ECS mengurutkan wadah komponen mereka dengan Entity ID, yang berarti bahwa komponen yang sesuai di masing-masing kelompok akan berada dalam urutan yang sama.

Ini berarti bahwa jika Anda melakukan iterasi linear pada komponen grafis, Anda juga akan melakukan iterasi linear pada komponen transformasi yang sesuai. Anda mungkin melewatkan beberapa transformasi (karena Anda mungkin memiliki volume pemicu fisika yang tidak Anda render atau semacamnya) tetapi karena Anda selalu melewatkan ke depan dalam memori (dan dengan jarak yang tidak terlalu besar, biasanya) Anda masih akan pergi untuk mendapatkan keuntungan efisiensi.

Ini mirip dengan bagaimana Anda menjadikan Structure Of Arrays (SOA) sebagai pendekatan yang disarankan untuk HPC. CPU dan cache dapat menangani beberapa array linear hampir sama baiknya dengan berurusan dengan satu array linear, dan jauh lebih baik daripada berurusan dengan akses memori acak.

Strategi lain yang digunakan dalam beberapa implementasi ECS - termasuk Unity ECS - adalah mengalokasikan Komponen berdasarkan Pola Dasar dari Entitas terkait mereka. Artinya, semua Entitas dengan tepat set Komponen ( PhysicsBody, Transform) akan dialokasikan secara terpisah dari Entitas dengan berbagai komponen (misalnya PhysicsBody, Transform, dan Renderable ).

Sistem dalam desain seperti itu bekerja dengan terlebih dahulu menemukan semua Pola Dasar yang sesuai dengan persyaratannya (yang memiliki seperangkat Komponen yang disyaratkan), mengulangi daftar Pola Dasar itu, dan mengulangi Komponen yang disimpan dalam setiap Pola Dasar yang cocok. Ini memungkinkan akses komponen O (1) yang sepenuhnya linier dan benar dalam Pola Dasar dan memungkinkan Sistem untuk menemukan Entitas yang kompatibel dengan overhead yang sangat rendah (dengan mencari daftar kecil Pola Dasar daripada mencari ratusan ribu Entitas yang berpotensi).

Anda dapat memiliki komponen menyimpan pointer ke komponen lain, atau pointer ke entitas yang menyimpan pointer ke komponen.

Komponen yang merujuk komponen lain pada entitas yang sama tidak perlu menyimpan apa pun. Untuk referensi komponen pada entitas lain, cukup simpan ID entitas.

Jika suatu komponen diizinkan ada lebih dari satu kali untuk satu entitas dan Anda perlu merujuk pada instance tertentu, simpan ID entitas lain dan indeks komponen untuk entitas itu. Namun, banyak implementasi ECS tidak mengizinkan kasus ini, khususnya karena membuat operasi ini kurang efisien.

Anda dapat memastikan bahwa setiap array komponen 'n' besar, di mana 'n' adalah jumlah entitas yang hidup dalam sistem

Gunakan pegangan (mis. Indeks + marka pembangkitan) dan bukan pointer dan kemudian Anda dapat mengubah ukuran array tanpa takut merusak referensi objek.

Anda juga dapat menggunakan pendekatan "chunked array" (array array) yang mirip dengan banyak std::dequeimplementasi umum (meskipun tanpa ukuran chunked yang sangat kecil dari implementasi tersebut) jika Anda ingin mengizinkan pointer untuk beberapa alasan atau jika Anda telah mengukur masalah dengan array mengubah ukuran kinerja.

Kedua, ini semua mengasumsikan bahwa entitas diproses secara linier dalam daftar setiap frame / centang, tetapi dalam kenyataannya ini tidak sering terjadi

Itu tergantung pada entitas. Ya, untuk banyak kasus penggunaan, itu tidak benar. Memang, inilah mengapa saya sangat menekankan perbedaan antara desain berbasis komponen (baik) dan sistem-entitas (bentuk khusus CBD).

Beberapa komponen Anda tentu akan mudah diproses secara linear. Bahkan dalam kasus penggunaan "pohon berat" yang biasa kita telah melihat peningkatan kinerja dari menggunakan array yang sangat padat (kebanyakan dalam kasus yang melibatkan N dari beberapa ratus paling banyak, seperti agen AI dalam permainan khas).

Beberapa pengembang juga telah menemukan bahwa keuntungan kinerja dari menggunakan struktur data yang dialokasikan secara linier yang diorientasikan melebihi keuntungan kinerja dari menggunakan struktur berbasis pohon yang "lebih pintar". Itu semua tergantung pada gim dan kasus penggunaan tertentu, tentu saja.

Katakanlah Anda menggunakan sektor / portal renderer atau sebuah octree untuk melakukan penyisihan oklusi. Anda mungkin dapat menyimpan entitas secara bersamaan dalam suatu sektor / simpul, tetapi Anda akan melompat-lompat apakah Anda suka atau tidak.

Anda akan terkejut betapa array masih membantu. Anda melompat-lompat di wilayah memori yang jauh lebih kecil daripada "di mana saja" dan bahkan dengan semua lompatan Anda masih jauh lebih mungkin berakhir dalam sesuatu dalam cache. Dengan pohon dengan ukuran tertentu atau kurang, Anda bahkan mungkin dapat mengambil semuanya menjadi cache dan tidak pernah memiliki cache miss pada pohon itu.

Ada juga struktur pohon yang dibangun untuk hidup dalam susunan yang padat. Misalnya, dengan octree Anda, Anda dapat menggunakan struktur seperti tumpukan (orang tua sebelum anak-anak, saudara kandung bersebelahan) dan memastikan bahwa bahkan ketika Anda "menelusuri" pohon itu, Anda selalu beralih ke depan dalam susunan, yang membantu CPU mengoptimalkan akses memori / pencarian cache.

Yang merupakan poin penting untuk dibuat. CPU x86 adalah binatang yang kompleks. CPU secara efektif menjalankan pengoptimal mikrokode pada kode mesin Anda, memecahnya menjadi mikrokode yang lebih kecil dan menyusun ulang instruksi, memprediksi pola akses memori, dll. Pola akses data lebih penting daripada yang mungkin dengan mudah terlihat jika yang Anda miliki hanyalah pemahaman tingkat tinggi dari cara kerja CPU atau cache.

Kemudian Anda memiliki sistem lain, yang mungkin lebih suka entitas disimpan dalam urutan lain.

Anda bisa menyimpannya beberapa kali. Setelah Anda menghapus array ke detail minimum, Anda mungkin menemukan Anda benar-benar menghemat memori (karena Anda telah menghapus pointer 64-bit dan dapat menggunakan indeks yang lebih kecil) dengan pendekatan ini.

Anda bisa interleave array entitas Anda alih-alih menjaga array yang terpisah, tetapi Anda masih membuang-buang memori

Ini bertentangan dengan penggunaan cache yang baik. Jika yang Anda pedulikan hanyalah data transformasi dan grafik, mengapa membuat mesin menghabiskan waktu untuk menarik semua data lain untuk fisika dan AI serta input dan debug, dan sebagainya?

Itulah poin yang biasanya dibuat dalam mendukung objek game ECS vs monolitik (meskipun tidak benar-benar berlaku ketika membandingkan dengan arsitektur berbasis komponen lainnya).

Untuk apa nilainya, sebagian besar implementasi ECS "tingkat produksi" yang saya sadari menggunakan penyimpanan interleaved. Pendekatan pola dasar yang populer yang saya sebutkan sebelumnya (digunakan dalam Unity ECS, misalnya) sangat eksplisit dibangun untuk menggunakan penyimpanan yang disisipkan untuk Komponen yang terkait dengan Pola Dasar.

AI tidak ada gunanya jika tidak dapat memengaruhi kondisi transformasi atau animasi yang digunakan untuk rendering entitas.

Hanya karena AI tidak dapat secara efisien mengakses transformasi data secara linear tidak berarti bahwa tidak ada sistem lain yang dapat menggunakan optimasi tata letak data secara efektif. Anda dapat menggunakan array yang dikemas untuk mengubah data tanpa menghentikan sistem logika game dari melakukan sesuatu dengan cara ad hoc sistem logika game biasanya melakukan sesuatu.

Anda juga lupa kode cache . Ketika Anda menggunakan pendekatan sistem ECS (tidak seperti beberapa arsitektur komponen yang lebih naif) Anda menjamin bahwa Anda menjalankan loop kecil kode yang sama dan tidak melompat bolak-balik melalui tabel fungsi virtual ke bermacam-macam Updatefungsi acak yang bertebaran di seluruh biner Anda. Jadi dalam kasus AI, Anda benar-benar ingin menyimpan semua komponen AI Anda yang berbeda (karena tentu saja Anda memiliki lebih dari satu sehingga Anda dapat menyusun perilaku!) Dalam ember terpisah dan memproses setiap daftar secara terpisah untuk mendapatkan penggunaan cache kode yang terbaik.

Dengan antrian acara yang tertunda (di mana sistem membuat daftar acara tetapi tidak mengirimkannya sampai sistem selesai memproses semua entitas) Anda dapat memastikan bahwa cache kode Anda digunakan dengan baik sambil menyimpan acara.

Menggunakan pendekatan di mana masing-masing sistem tahu antrian acara mana yang harus dibaca untuk frame, Anda bahkan dapat membuat acara membaca dengan cepat. Atau lebih cepat daripada tanpa, setidaknya.

Ingat, kinerja tidak mutlak. Anda tidak perlu menghilangkan setiap kesalahan cache tunggal terakhir untuk mulai melihat manfaat kinerja dari desain berorientasi data yang baik.

Masih ada penelitian aktif untuk membuat banyak sistem permainan bekerja lebih baik dengan arsitektur ECS dan pola desain yang berorientasi data. Demikian pula dengan beberapa hal luar biasa yang telah kita lihat dilakukan dengan SIMD dalam beberapa tahun terakhir (misalnya JSON parser), kita melihat semakin banyak hal dilakukan dengan arsitektur ECS yang tampaknya tidak intuitif untuk arsitektur game klasik tetapi menawarkan sejumlah manfaat (kecepatan, multi-threading, testabilitas, dll.).

Atau mungkin ada pendekatan hybrid yang digunakan semua orang tetapi tidak ada yang membicarakannya

Ini adalah apa yang saya anjurkan di masa lalu, terutama bagi orang-orang yang skeptis terhadap arsitektur ECS: menggunakan pendekatan berorientasi data yang baik untuk komponen di mana kinerja sangat penting. Gunakan arsitektur yang lebih sederhana di mana kesederhanaan meningkatkan waktu pengembangan. Jangan tanduk sepatu setiap komponen menjadi definisi komponen yang terlalu ketat seperti yang diusulkan ECS. Kembangkan arsitektur komponen Anda sedemikian rupa sehingga Anda dapat dengan mudah menggunakan pendekatan seperti ECS di mana mereka masuk akal dan menggunakan struktur komponen yang lebih sederhana di mana pendekatan seperti ECS tidak masuk akal (atau kurang masuk akal daripada struktur pohon, atau sebagainya) .

Saya pribadi yang baru saja insaf ke kekuatan ECS yang sebenarnya. Meskipun bagi saya, faktor penentu adalah sesuatu yang jarang disebutkan tentang ECS: itu membuat tes menulis untuk sistem permainan dan logika hampir sepele dibandingkan dengan desain berbasis komponen yang sarat logika yang sarat dengan kaitan yang telah saya kerjakan sebelumnya. Karena arsitektur ECS menempatkan semua logika dalam Sistem, yang hanya mengkonsumsi Komponen dan menghasilkan pembaruan Komponen, membangun set "tiruan" Komponen untuk menguji perilaku Sistem cukup mudah; karena sebagian besar logika gim harus hidup hanya di dalam Sistem, itu berarti menguji semua Sistem Anda akan memberikan cakupan kode yang cukup tinggi dari logika gim Anda. Sistem dapat menggunakan dependensi tiruan (mis. Antarmuka GPU) untuk pengujian dengan kompleksitas yang jauh lebih kecil atau dampak kinerja daripada Anda

Sebagai tambahan, Anda mungkin memperhatikan bahwa banyak orang berbicara tentang ECS ​​tanpa benar-benar memahami apa itu ECS. Saya melihat klasik Unity disebut sebagai ECS dengan frekuensi yang menyedihkan, menggambarkan bahwa terlalu banyak pengembang game menyamakan "ECS" dengan "Komponen" dan cukup banyak mengabaikan bagian "Sistem Entitas" sepenuhnya. Anda melihat banyak cinta menumpuk di ECS di Internet ketika sebagian besar orang benar-benar hanya menganjurkan desain berbasis komponen, bukan ECS yang sebenarnya. Pada titik ini, hampir tidak ada gunanya membantahnya; ECS telah rusak dari arti aslinya menjadi istilah umum dan Anda mungkin menerima bahwa "ECS" tidak berarti sama dengan "ECS berorientasi data". : /