Bagaimana cara memanfaatkan cache cpu di mesin game sistem komponen entitas?

Saya sering membaca dalam dokumentasi mesin game ECS yang merupakan arsitektur yang baik untuk menggunakan cache cpu dengan bijak.

Tapi saya tidak tahu bagaimana kita bisa mendapat manfaat dari cpu cache.

Jika komponen disimpan dalam array (atau kumpulan), dalam memori yang berdekatan, itu adalah cara yang baik untuk menggunakan cache cpu TAPI hanya jika kita membaca komponen secara berurutan.

Ketika kita menggunakan sistem, mereka membutuhkan daftar entitas yang merupakan daftar entitas yang memiliki komponen dengan tipe tertentu.

Tetapi daftar ini memberikan komponen secara acak, tidak berurutan.

Jadi bagaimana merancang ECS ​​untuk memaksimalkan hit cache?

EDIT:

Sebagai contoh, sistem Fisika membutuhkan daftar entitas untuk entitas yang memiliki komponen RigidBody dan Transform (Ada kumpulan untuk RigidBody dan kumpulan untuk komponen Transform).

Jadi loop untuk memperbarui entitas akan seperti ini:

for (Entity eid in entitiesList) {
    // Get rigid body component
    RigidBody *rigidBody = entityManager.getComponentFromEntity<RigidBody>(eid);

    // Get transform component
    Transform *transform = entityManager.getComponentFromEntity<Transform>(eid);

    // Do something with rigid body and transform component
}

Masalahnya adalah bahwa komponen RigidBody dari entitas1 dapat berada di indeks 2 dari kumpulannya dan komponen Tranform dari entitas1 pada indeks 0 dari kumpulannya (karena beberapa entitas dapat memiliki beberapa komponen dan bukan yang lain dan karena menambah / menghapus entitas / komponen secara acak).

Jadi, bahkan jika komponen bersebelahan dalam memori, mereka dibaca secara acak sehingga akan memiliki lebih banyak cache miss, bukan?

Kecuali ada cara untuk mengambil komponen berikutnya dalam loop?

Artikel Mick West menjelaskan proses linearisasi data komponen entitas, secara lengkap. Ini bekerja untuk seri Tony Hawk, bertahun-tahun lalu, pada perangkat keras yang jauh lebih mengesankan daripada yang kita miliki saat ini, untuk sangat meningkatkan kinerja. Dia pada dasarnya menggunakan global, pra-alokasi array untuk setiap tipe data entitas yang berbeda (posisi, skor dan yang lainnya) dan mereferensikan setiap array dalam fase berbeda dari update()fungsi seluruh sistemnya . Anda dapat mengasumsikan bahwa data untuk setiap entitas akan berada pada indeks array yang sama di setiap array global ini, jadi misalnya, jika pemain dibuat terlebih dahulu, mungkin datanya ada di [0]dalam setiap array.

Bahkan lebih spesifik untuk optimasi cache, slide Christer Ericsson untuk C dan C ++.

Untuk memberikan sedikit lebih detail, Anda harus mencoba menggunakan blok memori yang berdekatan (paling mudah dialokasikan sebagai array) per setiap jenis data (misalnya posisi, xy dan z), untuk memastikan lokalitas referensi yang baik, memanfaatkan setiap blok data tersebut secara berbeda. update()fase demi temporal locality yaitu untuk memastikan cache tidak memerah melalui algoritma LRU perangkat keras sebelum Anda menggunakan kembali data yang ingin Anda gunakan kembali, dalam update()panggilan yang diberikan . Seperti yang telah Anda katakan, apa yang tidak ingin Anda lakukan adalah mengalokasikan entitas dan komponen Anda sebagai objek diskrit melalui new, karena data dari berbagai jenis pada setiap instance entitas kemudian akan disatukan, mengurangi lokalitas referensi.

Jika Anda memiliki saling ketergantungan antara komponen (data) sehingga Anda benar-benar tidak mampu memisahkan data dari data terkait (mis. Transform + Fisika, Transform + Renderer) maka Anda dapat memilih untuk mereplikasi Transform data dalam array Fisika dan Renderer , memastikan bahwa semua data terkait sesuai dengan lebar garis cache untuk setiap operasi yang kritis-kinerja.

Ingat juga bahwa L2 dan L3 cache (jika Anda dapat menganggap ini untuk platform target Anda) melakukan banyak hal untuk meringankan masalah yang mungkin diderita oleh cache L1, seperti lebar garis yang terbatas. Jadi, bahkan pada L1 yang ketinggalan, ini adalah jaring pengaman yang paling sering mencegah pemanggilan ke memori utama, yang urutan besarnya lebih lambat dari pemanggilan ke tingkat cache apa pun.

Catatan tentang menulis data. Menulis tidak memanggil ke memori utama. Secara default, sistem saat ini telah mengaktifkan cache kembali : menulis nilai hanya menulisnya ke cache (awalnya), bukan ke memori utama, sehingga Anda tidak akan mengalami hambatan oleh ini. Hanya ketika data diminta dari memori utama (tidak akan terjadi ketika sedang dalam cache) dan basi, memori utama itu akan diperbarui dari cache.