Kehilangan cache dan kegunaan dalam Sistem Entitas

Akhir-akhir ini saya telah meneliti dan menerapkan Sistem Entitas untuk kerangka kerja saya. Saya pikir saya membaca sebagian besar artikel, reddits, dan pertanyaan tentang hal itu yang dapat saya temukan, dan sejauh ini saya pikir saya cukup memahami ide itu.

Namun, itu menimbulkan beberapa pertanyaan tentang perilaku C ++ secara keseluruhan, bahasa tempat saya mengimplementasikan sistem entitas, serta beberapa masalah kegunaan.

Jadi, salah satu pendekatan akan menyimpan array komponen dalam entitas secara langsung, yang saya tidak lakukan karena itu merusak cache lokalitas ketika iterasi melalui data. Karena itu, saya memutuskan untuk memiliki satu array per tipe komponen, sehingga semua komponen dari tipe yang sama bersebelahan dalam memori, yang seharusnya menjadi solusi optimal untuk iterasi cepat.

Tetapi, ketika saya beralih ke array komponen untuk melakukan sesuatu dengan mereka dari suatu sistem pada implementasi gameplay yang sebenarnya, saya perhatikan bahwa saya hampir selalu bekerja dengan dua atau lebih tipe komponen sekaligus. Misalnya, sistem render menggunakan komponen Transform dan Model bersama-sama untuk benar-benar melakukan panggilan render. Pertanyaan saya adalah, karena saya tidak mengulangi secara linear satu array yang berdekatan pada satu waktu dalam kasus ini, apakah saya langsung mengorbankan keuntungan kinerja dari mengalokasikan komponen dengan cara ini? Apakah ini masalah ketika saya mengulangi, dalam C ++, dua array berdekatan yang berbeda dan menggunakan data dari keduanya pada setiap siklus?

Hal lain yang ingin saya tanyakan adalah bagaimana seseorang harus menyimpan referensi ke komponen atau entitas, karena sifat dari bagaimana komponen diletakkan dalam memori, mereka dapat dengan mudah beralih posisi dalam array atau array dapat dialokasikan kembali untuk memperluas atau menyusut, meninggalkan pointer komponen saya atau menangani tidak valid. Bagaimana Anda merekomendasikan untuk menangani kasus-kasus ini, karena saya sering menemukan diri saya ingin beroperasi pada transformasi dan komponen lain setiap frame dan jika pegangan atau pointer saya tidak valid, sangat berantakan untuk membuat pencarian setiap frame.

Pertama, saya tidak akan mengatakan bahwa dalam hal ini Anda mengoptimalkan terlalu dini, tergantung pada kasus penggunaan Anda. Bagaimanapun, Anda telah mengajukan pertanyaan yang menarik dan karena saya memiliki pengalaman dengan ini sendiri, saya akan mempertimbangkan. Saya akan mencoba menjelaskan bagaimana saya akhirnya melakukan sesuatu dan apa yang saya temukan di jalan.

• Setiap entitas memegang vektor pegangan komponen generik yang dapat mewakili jenis apa pun.
• Setiap pegangan komponen dapat direferensikan untuk menghasilkan pointer T * mentah. *Lihat di bawah.
• Setiap jenis komponen memiliki kumpulan sendiri, blok memori yang berkelanjutan (ukuran tetap dalam kasus saya).

Perlu dicatat bahwa tidak, Anda tidak akan dapat selalu melintasi kumpulan komponen dan melakukan hal yang bersih dan ideal. Ada, seperti yang Anda katakan, tautan yang tak terhindarkan antara komponen, di mana Anda benar-benar perlu memproses hal-hal suatu entitas pada suatu waktu.

Namun, ada beberapa kasus (seperti yang saya temukan) di mana memang, Anda benar-benar dapat menulis loop for untuk jenis komponen tertentu dan memanfaatkan garis cache CPU Anda. Bagi mereka yang tidak tahu atau ingin tahu lebih banyak, lihat https://en.wikipedia.org/wiki/Locality_of_reference . Pada catatan yang sama, jika memungkinkan, cobalah untuk menjaga ukuran komponen Anda kurang dari atau sama dengan ukuran garis cache CPU Anda. Ukuran baris saya adalah 64 byte, yang saya yakini umum.

Dalam kasus saya, membuat upaya menerapkan sistem itu sepadan. Saya melihat keuntungan kinerja yang terlihat (tentu saja diprofilkan). Anda harus memutuskan sendiri apakah itu ide yang bagus. Keuntungan terbesar dalam kinerja yang saya lihat di 1000+ entitas.

Hal lain yang ingin saya tanyakan adalah bagaimana seseorang harus menyimpan referensi ke komponen atau entitas, karena sifat dari bagaimana komponen diletakkan dalam memori, mereka dapat dengan mudah beralih posisi dalam array atau array dapat dialokasikan kembali untuk memperluas atau menyusut, meninggalkan pointer komponen saya atau menangani tidak valid. Bagaimana Anda merekomendasikan untuk menangani kasus-kasus ini, karena saya sering menemukan diri saya ingin beroperasi pada transformasi dan komponen lain setiap frame dan jika pegangan atau pointer saya tidak valid, sangat berantakan untuk membuat pencarian setiap frame.

Saya juga memecahkan masalah ini secara pribadi. Saya akhirnya memiliki sistem di mana:

• Setiap pegangan komponen memegang referensi ke indeks kumpulan
• Ketika komponen 'dihapus' atau 'dihapus' dari kumpulan, komponen terakhir di dalam kumpulan itu dipindahkan (secara harfiah dengan std :: move) ke lokasi yang sekarang bebas, atau tidak ada jika Anda baru saja menghapus komponen terakhir.
• Ketika 'swap' terjadi, saya memiliki panggilan balik yang memberi tahu pendengar mana pun, sehingga mereka dapat memperbarui petunjuk konkret apa pun (misalnya T *).

* Saya menemukan bahwa berusaha untuk selalu menangani komponen dereference saat runtime di bagian tertentu dari kode penggunaan tinggi dengan jumlah entitas yang saya hadapi adalah masalah kinerja. Karena itu, saya sekarang mempertahankan beberapa pointer T mentah dalam kinerja bagian penting dari proyek saya, tetapi sebaliknya saya menggunakan pegangan komponen generik, yang harus digunakan jika memungkinkan. Saya membuatnya valid seperti yang disebutkan di atas, dengan sistem panggilan balik. Anda mungkin tidak perlu pergi sejauh itu.

Di atas semua itu, cobalah saja. Sampai Anda mendapatkan skenario dunia nyata, apa pun yang dikatakan orang di sini hanyalah satu cara dalam melakukan sesuatu, yang mungkin tidak sesuai untuk Anda.

Apakah itu membantu? Saya akan mencoba mengklarifikasi apa pun yang tidak jelas. Juga segala koreksi dihargai.

Untuk menjawab ini saja:

Pertanyaan saya adalah, karena saya tidak mengulangi secara linear satu array yang berdekatan pada satu waktu dalam kasus ini, apakah saya langsung mengorbankan keuntungan kinerja dari mengalokasikan komponen dengan cara ini? Apakah ini masalah ketika saya mengulangi, dalam C ++, dua array berdekatan yang berbeda dan menggunakan data dari keduanya pada setiap siklus?

Tidak (setidaknya tidak harus). Pengontrol cache harus, dalam banyak kasus, dapat menangani pembacaan dari lebih dari satu array yang berdekatan secara efisien. Bagian yang penting adalah mencoba jika memungkinkan untuk mengakses setiap array secara linear.

Untuk menunjukkan ini, saya menulis tolok ukur kecil (peringatan tolok ukur yang biasa berlaku).

Dimulai dengan struct vektor sederhana:

struct float3 { float x, y, z; };

Saya menemukan bahwa loop yang menjumlahkan setiap elemen dari dua array terpisah dan menyimpan hasilnya dalam sepertiga dilakukan persis sama dengan versi di mana data sumber disisipkan dalam satu array dan hasilnya disimpan dalam sepertiga. Namun saya menemukan, jika saya menghubungkan hasilnya dengan sumbernya, kinerjanya menurun (sekitar faktor 2).

Jika saya mengakses data secara acak, kinerja yang diderita oleh faktor antara 10 dan 20.

Pengaturan waktu (10.000.000 elemen)

akses linear

• pisahkan array 0.21s
• sumber interleaved 0.21s
• sumber dan hasil interleaved 0.48s

akses acak (batalkan komentar acak_shuffle)

• pisahkan array 2.42s
• sumber interleaved 4.43s
• sumber dan hasil interleaved 4.00s

Sumber (dikompilasi dengan Visual Studio 2013):

#include <Windows.h>
#include <vector>
#include <algorithm>
#include <iostream>

struct float3 { float x, y, z; };

float3 operator+( float3 const &a, float3 const &b )
{
    return float3{ a.x + b.x, a.y + b.y, a.z + b.z };
}

struct Both { float3 a, b; };

struct All { float3 a, b, res; };


// A version without any indirection
void sum( float3 *a, float3 *b, float3 *res, int n )
{
    for( int i = 0; i < n; ++i )
        *res++ = *a++ + *b++;
}

void sum( float3 *a, float3 *b, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = a[*index] + b[*index];
}

void sum( Both *both, float3 *res, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        res[*index] = both[*index].a + both[*index].b;
}

void sum( All *all, int *index, int n )
{
    for( int i = 0; i < n; ++i, ++index )
        all[*index].res = all[*index].a + all[*index].b;
}

class PerformanceTimer
{
public:
    PerformanceTimer() { QueryPerformanceCounter( &start ); }
    double time()
    {
        LARGE_INTEGER now, freq;
        QueryPerformanceCounter( &now );
        QueryPerformanceFrequency( &freq );
        return double( now.QuadPart - start.QuadPart ) / double( freq.QuadPart );
    }
private:
    LARGE_INTEGER start;
};

int main( int argc, char* argv[] )
{
    const int count = 10000000;

    std::vector< float3 > a( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > b( count, float3{ 1.f, 2.f, 3.f } );
    std::vector< float3 > res( count );

    std::vector< All > all( count, All{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );
    std::vector< Both > both( count, Both{ { 1.f, 2.f, 3.f }, { 1.f, 2.f, 3.f } } );

    std::vector< int > index( count );
    int n = 0;
    std::generate( index.begin(), index.end(), [&]{ return n++; } );
    //std::random_shuffle( index.begin(), index.end() );

    PerformanceTimer timer;
    // uncomment version to test
    //sum( &a[0], &b[0], &res[0], &index[0], count );
    //sum( &both[0], &res[0], &index[0], count );
    //sum( &all[0], &index[0], count );
    std::cout << timer.time();
    return 0;
}

Jawaban Singkat: Profil kemudian dioptimalkan.

Jawaban panjang:

Tetapi, ketika saya beralih ke array komponen untuk melakukan sesuatu dengan mereka dari suatu sistem pada implementasi gameplay yang sebenarnya, saya perhatikan bahwa saya hampir selalu bekerja dengan dua atau lebih tipe komponen sekaligus.

Apakah ini masalah ketika saya mengulangi, dalam C ++, dua array berdekatan yang berbeda dan menggunakan data dari keduanya pada setiap siklus?

C ++ tidak bertanggung jawab atas kesalahan cache, karena ini berlaku untuk bahasa pemrograman apa pun. Ini ada hubungannya dengan cara kerja arsitektur CPU modern.

Masalah Anda mungkin menjadi contoh yang baik tentang apa yang disebut optimasi pra-matang .

Menurut pendapat saya, Anda dioptimalkan terlalu dini untuk lokalitas cache tanpa melihat pola akses memori program. Tetapi pertanyaan yang lebih besar adalah apakah Anda benar-benar membutuhkan pengoptimalan semacam ini?

Agner's Fog menyarankan Anda untuk tidak mengoptimalkan sebelum profil aplikasi Anda dan / atau tahu pasti di mana hambatannya. (Ini semua disebutkan dalam panduannya yang sangat bagus. Tautan di bawah)

Sangat berguna untuk mengetahui bagaimana cache disusun jika Anda membuat program yang memiliki struktur data besar dengan akses non-sekuensial dan Anda ingin mencegah pertikaian cache. Anda dapat melewati bagian ini jika Anda puas dengan pedoman yang lebih heuristik.

Sayangnya yang Anda lakukan sebenarnya berasumsi bahwa mengalokasikan satu jenis komponen per larik akan memberi Anda kinerja yang lebih baik, sementara pada kenyataannya Anda mungkin telah menyebabkan lebih banyak cache yang hilang atau bahkan pertengkaran cache.

Anda harus melihat panduan pengoptimalan C ++ yang luar biasa .

Hal lain yang ingin saya tanyakan adalah bagaimana seseorang harus menyimpan referensi ke komponen atau entitas, karena sifat dari bagaimana komponen diletakkan dalam memori.

Secara pribadi saya akan mengalokasikan komponen yang paling sering digunakan bersama dalam satu blok memori tunggal, sehingga mereka memiliki alamat "dekat". Misalnya array akan terlihat seperti itu:

[{ID0 Transform Model PhysicsComp }{ID10 Transform Model PhysicsComp }{ID2 Transform Model PhysicsComp }..] dan kemudian mulai mengoptimalkan dari sana jika kinerjanya tidak "cukup baik".

Pertanyaan saya adalah, karena saya tidak mengulangi secara linear satu array yang berdekatan pada satu waktu dalam kasus ini, apakah saya langsung mengorbankan keuntungan kinerja dari mengalokasikan komponen dengan cara ini?

Kemungkinannya adalah Anda akan mendapatkan lebih sedikit cache secara keseluruhan dengan array "vertikal" terpisah per tipe komponen daripada interleaving komponen yang melekat pada suatu entitas dalam blok ukuran variabel "horizontal".

Alasannya adalah karena, pertama, representasi "vertikal" akan cenderung menggunakan lebih sedikit memori. Anda tidak perlu khawatir tentang penyelarasan untuk array homogen yang dialokasikan secara berdekatan. Dengan tipe non-homogen yang dialokasikan ke dalam kumpulan memori, Anda harus khawatir tentang perataan karena elemen pertama dalam larik dapat memiliki ukuran dan persyaratan perataan yang sama sekali berbeda dari yang kedua. Akibatnya, Anda harus sering menambahkan bantalan, seperti contoh sederhana:

// Assuming 8-bit chars and 64-bit doubles.
struct Foo
{
    // 1 byte
    char a;

    // 1 byte
    char b;
};

struct Bar
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Katakanlah kita ingin interleave Foodan Bardan menyimpannya tepat di samping satu sama lain dalam memori:

// Assuming 8-bit chars and 64-bit doubles.
struct FooBar
{
    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'

    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;
};

Sekarang alih-alih mengambil 18 byte untuk menyimpan Foo dan Bar di wilayah memori yang terpisah, dibutuhkan 24 byte untuk menggabungkannya. Tidak masalah jika Anda menukar pesanan:

// Assuming 8-bit chars and 64-bit doubles.
struct BarFoo
{
    // 8 bytes
    double opacity;

    // 8 bytes
    double radius;

    // 1 byte
    char a;

    // 1 byte
    char b;

    // 6 bytes padding for 64-bit alignment of 'opacity'
};

Jika Anda mengambil lebih banyak memori dalam konteks akses berurutan tanpa meningkatkan pola akses secara signifikan, maka Anda biasanya akan mengalami lebih banyak kesalahan cache. Selain itu, langkah untuk berpindah dari satu entitas ke entitas lain meningkat dan ke ukuran variabel, membuat Anda harus mengambil lompatan berukuran variabel dalam memori untuk berpindah dari satu entitas ke entitas lain hanya untuk melihat mana yang memiliki komponen yang Anda inginkan. tertarik pada.

Jadi menggunakan representasi "vertikal" seperti yang Anda lakukan untuk menyimpan tipe komponen sebenarnya lebih mungkin lebih optimal daripada alternatif "horisontal". Yang mengatakan, masalah dengan kesalahan cache dengan representasi vertikal dapat dicontohkan di sini:

Di mana panah hanya mengindikasikan bahwa entitas "memiliki" komponen. Kita dapat melihat bahwa jika kita mencoba mengakses semua gerakan dan merender komponen dari entitas yang memiliki keduanya, kita berakhir melompati semua tempat di memori. Pola akses sporadis semacam itu dapat membuat Anda memuat data ke dalam garis cache untuk mengakses, katakanlah, komponen gerak, lalu mengakses lebih banyak komponen dan meminta agar data sebelumnya digusur, hanya untuk memuat kembali wilayah memori yang sama yang sudah diusir untuk gerakan lain komponen. Sehingga bisa sangat boros memuat wilayah memori yang sama persis lebih dari satu kali ke dalam garis cache hanya untuk mengulang dan mengakses daftar komponen.

Mari kita bersihkan kekacauan itu sedikit sehingga kita bisa melihat lebih jelas:

Perhatikan bahwa jika Anda menghadapi skenario semacam ini, biasanya lama setelah game mulai berjalan, setelah banyak komponen dan entitas telah ditambahkan dan dihapus. Secara umum ketika permainan dimulai, Anda dapat menambahkan semua entitas dan komponen yang relevan bersama-sama, pada titik mana mereka mungkin memiliki pola akses sekuensial yang sangat teratur dengan lokalitas spasial yang baik. Setelah banyak pemindahan dan penyisipan, Anda mungkin akhirnya mendapatkan sesuatu seperti kekacauan di atas.

Cara yang sangat mudah untuk memperbaiki situasi itu adalah dengan hanya mengurutkan komponen Anda berdasarkan ID entitas / indeks yang memilikinya. Pada titik itu Anda mendapatkan sesuatu seperti ini:

Dan itu pola akses yang lebih ramah cache. Itu tidak sempurna karena kita dapat melihat bahwa kita harus melewatkan beberapa komponen rendering dan gerakan di sana-sini karena sistem kita hanya tertarik pada entitas yang memiliki keduanya , dan beberapa entitas hanya memiliki komponen gerak dan beberapa hanya memiliki komponen rendering , tetapi Anda setidaknya akhirnya dapat memproses beberapa komponen yang berdekatan (lebih banyak dalam praktiknya, biasanya, karena sering kali Anda akan melampirkan komponen menarik yang relevan, seperti mungkin lebih banyak entitas dalam sistem Anda yang memiliki komponen gerak akan memiliki komponen rendering daripada tidak).

Yang paling penting, setelah Anda mengurutkan ini, Anda tidak akan memuat data wilayah memori ke dalam garis cache hanya untuk kemudian memuatnya kembali dalam satu lingkaran.

Dan ini tidak memerlukan desain yang sangat kompleks, hanya semacam radix linear-waktu berlalu setiap sekarang dan kemudian, mungkin setelah Anda memasukkan dan menghapus banyak komponen untuk jenis komponen tertentu, pada titik mana Anda dapat menandainya sebagai perlu disortir. Jenis radix yang diimplementasikan secara wajar (Anda bahkan dapat memparalelkannya, yang saya lakukan) dapat mengurutkan sejuta elemen dalam sekitar 6ms pada quad-core i7 saya, seperti yang dicontohkan di sini:

Sorting 1000000 elements 32 times...
mt_sort_int: {0.203000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_sort: {1.248000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
mt_radix_sort: {0.202000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
std::sort: {1.810000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]
qsort: {2.777000 secs}
-- small result: [ 22 48 59 77 79 80 84 84 93 98 ]

Di atas adalah untuk mengurutkan sejuta elemen 32 kali (termasuk waktu untuk memcpyhasil sebelum dan sesudah pengurutan). Dan saya berasumsi sebagian besar waktu Anda tidak akan benar-benar memiliki komponen juta + untuk disortir, jadi Anda harus dengan mudah dapat menyelinap ini sekarang dan di sana tanpa menyebabkan gagap frame rate yang terlihat.