Cache-Misses und Usability in Entity-Systemen

In letzter Zeit habe ich ein Entitätssystem für mein Framework recherchiert und implementiert. Ich glaube, ich habe die meisten Artikel, Reddits und Fragen darüber gelesen, die ich finden konnte, und bis jetzt glaube ich, dass ich die Idee gut genug verstehe.

Es wurden jedoch einige Fragen zum allgemeinen C ++ - Verhalten, der Sprache, in der ich das Entitätssystem implementiere, sowie einige Usability-Probleme aufgeworfen.

Ein Ansatz wäre also, ein Array von Komponenten direkt in der Entität zu speichern, was ich nicht getan habe, da dies die Cache-Lokalität beim Durchlaufen von Daten ruiniert. Aus diesem Grund habe ich mich für ein Array pro Komponententyp entschieden, sodass alle Komponenten desselben Typs im Speicher zusammenhängend sind. Dies sollte die optimale Lösung für eine schnelle Iteration sein.

Wenn ich jedoch Komponenten-Arrays iterieren möchte, um bei einer tatsächlichen Gameplay-Implementierung von einem System aus etwas mit ihnen zu tun, stelle ich fest, dass ich fast immer mit zwei oder mehr Komponententypen gleichzeitig arbeite. Beispielsweise verwendet das Rendersystem die Transform- und die Model-Komponente zusammen, um tatsächlich einen Renderaufruf auszuführen. Meine Frage ist, da ich in diesen Fällen nicht linear jeweils ein zusammenhängendes Array iteriere, opfere ich sofort die Leistungsverbesserungen, die durch die Zuweisung von Komponenten auf diese Weise erzielt werden? Ist es ein Problem, wenn ich in C ++ zwei verschiedene zusammenhängende Arrays durchlaufe und bei jedem Zyklus Daten aus beiden verwende?

Eine andere Frage, die ich stellen wollte, ist, wie man Verweise auf Komponenten oder Entitäten aufbewahren sollte, da diese aufgrund der Art der Speicherung der Komponenten leicht die Positionen im Array wechseln können oder das Array für die Erweiterung oder Neuzuweisung verwendet werden könnte Verkleinern, wodurch meine Komponentenzeiger oder -handles ungültig werden. Wie empfehlen Sie, diese Fälle zu behandeln, da ich häufig die Transformationen und andere Komponenten jedes Frames bearbeiten möchte und wenn meine Handles oder Zeiger ungültig sind, ist es ziemlich unübersichtlich, jedes Frame nachzuschlagen.

Erstens würde ich nicht sagen, dass Sie in diesem Fall je nach Anwendungsfall zu früh optimieren. Auf jeden Fall haben Sie eine interessante Frage gestellt, und da ich selbst Erfahrung damit habe, werde ich abwägen. Ich werde versuchen, nur zu erklären, wie ich Dinge getan habe und was ich auf dem Weg gefunden habe.

• Jede Entität enthält einen Vektor von generischen Komponentenhandles, die einen beliebigen Typ darstellen können.
• Jedes Komponentenhandle kann dereferenziert werden, um einen rohen T * -Zeiger zu erhalten. *Siehe unten.
• Jeder Komponententyp hat einen eigenen Pool, einen zusammenhängenden Speicherblock (in meinem Fall feste Größe).

Es sollte beachtet werden, dass Sie nicht immer in der Lage sind, einen Komponentenpool zu durchlaufen und die ideale, saubere Sache zu machen. Es gibt, wie Sie bereits sagten, unvermeidliche Verknüpfungen zwischen Komponenten, bei denen Sie wirklich Dinge zu einer Entität verarbeiten müssen.

Es gibt jedoch Fälle (wie ich festgestellt habe), in denen Sie buchstäblich eine for-Schleife für einen bestimmten Komponententyp schreiben und Ihre CPU-Cache-Zeilen optimal nutzen können. Wer keine Ahnung hat oder mehr wissen möchte, schaut unter https://en.wikipedia.org/wiki/Locality_of_reference nach . Versuchen Sie aus dem gleichen Grund, wenn möglich, die Größe Ihrer Komponenten auf oder unter der CPU-Cache-Zeilengröße zu halten. Meine Zeilengröße betrug 64 Bytes, was ich für gewöhnlich halte.

In meinem Fall hat sich die Implementierung des Systems gelohnt. Ich sah sichtbare Leistungssteigerungen (natürlich profiliert). Sie müssen selbst entscheiden, ob es eine gute Idee ist. Die größten Leistungszuwächse verzeichnete ich bei über 1000 Unternehmen.

Eine andere Frage, die ich stellen wollte, ist, wie man Verweise auf Komponenten oder Entitäten aufbewahren sollte, da diese aufgrund der Art der Speicherung der Komponenten leicht die Positionen im Array wechseln können oder das Array für die Erweiterung oder Neuzuweisung verwendet werden könnte Verkleinern, wodurch meine Komponentenzeiger oder -handles ungültig werden. Wie empfehlen Sie, diese Fälle zu behandeln, da ich häufig die Transformationen und andere Komponenten jedes Frames bearbeiten möchte und wenn meine Handles oder Zeiger ungültig sind, ist es ziemlich unübersichtlich, jedes Frame nachzuschlagen.

Ich habe dieses Problem auch persönlich gelöst. Am Ende hatte ich ein System, in dem:

• Jedes Komponentenhandle enthält einen Verweis auf einen Poolindex
• Wenn eine Komponente aus einem Pool 'gelöscht' oder 'entfernt' wird, wird die letzte Komponente in diesem Pool (buchstäblich mit std :: move) an den jetzt freien Speicherort verschoben oder keine, wenn Sie gerade die letzte Komponente gelöscht haben.
• Wenn ein 'Swap' auftritt, habe ich einen Rückruf, der alle Listener benachrichtigt, so dass sie alle konkreten Zeiger aktualisieren können (z. B. T *).

* Ich stellte fest, dass der Versuch, Komponentenhandles zur Laufzeit in bestimmten Abschnitten von häufig verwendetem Code mit der Anzahl der Entitäten, mit denen ich zu tun hatte, immer zu dereferenzieren, ein Leistungsproblem war. Aus diesem Grund behalte ich jetzt einige rohe T-Zeiger in leistungskritischen Teilen meines Projekts bei, aber ansonsten verwende ich die generischen Komponentenhandles, die nach Möglichkeit verwendet werden sollten. Ich halte sie wie oben erwähnt mit dem Rückrufsystem gültig. Möglicherweise müssen Sie nicht so weit gehen.

Vor allem aber probieren Sie es einfach aus. Bis Sie ein reales Szenario erhalten, ist alles, was hier jemand sagt, nur eine Möglichkeit, Dinge zu tun, die für Sie möglicherweise nicht angemessen sind.

Hilft das? Ich werde versuchen, alles Unklare zu klären. Auch eventuelle Korrekturen sind erwünscht.

Um genau das zu beantworten:

Meine Frage ist, da ich in diesen Fällen nicht linear jeweils ein zusammenhängendes Array iteriere, opfere ich sofort die Leistungsverbesserungen, die durch die Zuweisung von Komponenten auf diese Weise erzielt werden? Ist es ein Problem, wenn ich in C ++ zwei verschiedene zusammenhängende Arrays durchlaufe und bei jedem Zyklus Daten aus beiden verwende?

Nein (zumindest nicht unbedingt). Der Cache-Controller sollte in den meisten Fällen in der Lage sein, das Lesen von mehr als einem zusammenhängenden Array effizient zu handhaben. Der wichtige Teil ist, zu versuchen, wo immer möglich, linear auf jedes Array zuzugreifen.

Um dies zu demonstrieren, habe ich einen kleinen Benchmark geschrieben (es gelten die üblichen Vorbehalte).

Beginnen Sie mit einer einfachen Vektorstruktur:

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

Ich fand heraus, dass eine Schleife, die jedes Element zweier separater Arrays summiert und das Ergebnis in einem dritten Array speichert, genau so funktioniert wie eine Version, bei der die Quelldaten in einem einzelnen Array verschachtelt und das Ergebnis in einem dritten Array gespeichert wurden. Ich fand jedoch, wenn ich das Ergebnis mit der Quelle verschachtelte, litt die Leistung (um einen Faktor von 2).

Wenn ich zufällig auf die Daten zugreife, leidet die Leistung um einen Faktor zwischen 10 und 20.

Timings (10.000.000 Elemente)

linearer Zugang

• separate Arrays 0.21s
• verschachtelte Quelle 0,21s
• verschachtelte Quelle und Ergebnis 0,48s

zufälliger Zugriff (uncomment random_shuffle)

• separate Arrays 2.42s
• verschachtelte Quelle 4.43s
• verschachtelte Quelle und Ergebnis 4.00s

Quelle (kompiliert mit 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;
}

Kurze Antwort: Profil dann optimieren.

Lange Antwort:

Wenn ich jedoch Komponenten-Arrays iterieren möchte, um bei einer tatsächlichen Gameplay-Implementierung von einem System aus etwas mit ihnen zu tun, stelle ich fest, dass ich fast immer mit zwei oder mehr Komponententypen gleichzeitig arbeite.

Ist es ein Problem, wenn ich in C ++ zwei verschiedene zusammenhängende Arrays durchlaufe und bei jedem Zyklus Daten aus beiden verwende?

C ++ ist nicht für Cache-Fehler verantwortlich, da es für alle Programmiersprachen gilt. Dies hängt damit zusammen, wie moderne CPU-Architekturen funktionieren.

Ihr Problem könnte ein gutes Beispiel für eine so genannte vorzeitige Optimierung sein .

Meiner Meinung nach haben Sie zu früh für die Cache-Lokalität optimiert, ohne auf die Programmspeicherzugriffsmuster zu achten. Die größere Frage ist jedoch, ob Sie diese Art (Referenzort) der Optimierung wirklich brauchten.

Agner's Fog empfiehlt, dass Sie nicht optimieren sollten, bevor Sie Ihre Anwendung profilieren und / oder genau wissen, wo die Engpässe liegen. (Dies ist alles in seinem ausgezeichneten Leitfaden erwähnt. Link unten)

Es ist hilfreich zu wissen, wie ein Cache organisiert ist, wenn Sie Programme mit großen Datenstrukturen und nicht sequenziellem Zugriff erstellen und Cache-Konflikte vermeiden möchten. Sie können diesen Abschnitt überspringen, wenn Sie mit heuristischeren Richtlinien zufrieden sind.

Leider haben Sie tatsächlich angenommen, dass die Zuweisung eines Komponententyps pro Array zu einer besseren Leistung führt, während Sie in Wirklichkeit möglicherweise mehr Cache-Ausfälle oder sogar Cache-Konflikte verursacht haben.

Sie sollten sich auf jeden Fall seine exzellente C ++ - Optimierungsanleitung ansehen .

Eine andere Frage, die ich stellen wollte, ist, wie man Verweise auf Komponenten oder Entitäten aufbewahren sollte, da die Komponenten von Natur aus im Speicher abgelegt sind.

Ich persönlich werde die am häufigsten verwendeten Komponenten in einem einzigen Speicherblock zuordnen, damit sie "nahe" Adressen haben. Zum Beispiel sieht ein Array so aus:

[{ID0 Transform Model PhysicsComp }{ID10 Transform Model PhysicsComp }{ID2 Transform Model PhysicsComp }..] und dann mit der Optimierung beginnen, wenn die Leistung nicht "gut genug" war.

Meine Frage ist, da ich in diesen Fällen nicht linear jeweils ein zusammenhängendes Array iteriere, opfere ich sofort die Leistungsverbesserungen, die durch die Zuweisung von Komponenten auf diese Weise erzielt werden?

Es besteht die Möglichkeit, dass Sie mit separaten "vertikalen" Arrays pro Komponententyp insgesamt weniger Cache-Ausfälle erhalten, als wenn Sie die an eine Entität angehängten Komponenten sozusagen in einem "horizontalen" Block mit variabler Größe verschachteln.

Der Grund dafür ist, dass erstens die "vertikale" Darstellung dazu neigt, weniger Speicher zu verwenden. Sie müssen sich nicht um die Ausrichtung von zusammenhängend zugewiesenen homogenen Arrays kümmern. Bei inhomogenen Typen, die einem Speicherpool zugeordnet sind, müssen Sie sich um die Ausrichtung kümmern, da das erste Element im Array möglicherweise andere Größen- und Ausrichtungsanforderungen als das zweite hat. Infolgedessen müssen Sie häufig Auffüllungen hinzufügen, wie zum Beispiel:

// 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;
};

Nehmen wir an, wir möchten sie verschachteln Foound Bardirekt nebeneinander speichern:

// 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;
};

Anstatt nun 18 Bytes zu benötigen, um Foo und Bar in separaten Speicherbereichen zu speichern, sind 24 Bytes erforderlich, um sie zu verschmelzen. Es spielt keine Rolle, ob Sie die Bestellung tauschen:

// 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'
};

Wenn Sie in einem Kontext mit sequenziellem Zugriff mehr Speicher beanspruchen, ohne die Zugriffsmuster wesentlich zu verbessern, treten in der Regel mehr Cache-Fehler auf. Darüber hinaus nimmt der Schritt von einer Entität zur nächsten und zu einer variablen Größe zu, sodass Sie einen Sprung in den Speicher machen müssen, um von einer Entität zur nächsten zu gelangen, nur um zu sehen, welche die von Ihnen verwendeten Komponenten enthalten. ' Ich bin interessiert an.

Die Verwendung einer "vertikalen" Darstellung zum Speichern von Komponententypen ist daher mit größerer Wahrscheinlichkeit optimal als "horizontale" Alternativen. Das Problem mit Cache-Fehlern bei der vertikalen Darstellung kann hier beispielhaft dargestellt werden:

Wo die Pfeile einfach anzeigen, dass die Entität eine Komponente "besitzt". Wir können sehen, dass wir, wenn wir versuchen, auf alle Bewegungs- und Renderkomponenten von Entitäten zuzugreifen, die beides enthalten, am Ende überall im Gedächtnis herumspringen. Bei dieser Art von sporadischem Zugriffsmuster können Sie Daten in eine Cache-Zeile laden, um beispielsweise auf eine Bewegungskomponente zuzugreifen, dann auf mehrere Komponenten zuzugreifen und diese früheren Daten zu entfernen, um dann denselben Speicherbereich erneut zu laden, der bereits für eine andere Bewegung entfernt wurde Komponente. Das kann also sehr verschwenderisch sein, wenn genau dieselben Speicherbereiche mehr als einmal in eine Cache-Zeile geladen werden, nur um eine Liste von Komponenten zu durchlaufen und darauf zuzugreifen.

Räumen wir das Chaos ein wenig auf, damit wir klarer sehen können:

Beachten Sie, dass es in der Regel lange nach dem Start des Spiels dauert, bis viele Komponenten und Entitäten hinzugefügt und entfernt wurden, wenn Sie auf ein solches Szenario stoßen. Im Allgemeinen können Sie zu Beginn des Spiels alle Entitäten und relevanten Komponenten zusammenfassen. Zu diesem Zeitpunkt verfügen sie möglicherweise über ein sehr geordnetes, sequenzielles Zugriffsmuster mit guter räumlicher Lokalität. Nach vielen Umzügen und Einfügungen kann es jedoch vorkommen, dass Sie so etwas wie das obige Chaos bekommen.

Eine sehr einfache Möglichkeit, diese Situation zu verbessern, besteht darin, Ihre Komponenten einfach nach der Entitäts-ID / dem Index zu sortieren, deren Eigentümer sie sind. An diesem Punkt erhalten Sie so etwas:

Und das ist ein viel Cache-freundlicheres Zugriffsmuster. Es ist nicht perfekt, da wir sehen, dass wir hier und da einige Rendering- und Bewegungskomponenten überspringen müssen, da unser System nur an Entitäten interessiert ist, die beide haben, und einige Entitäten nur eine Bewegungskomponente und einige nur eine Rendering-Komponente haben Sie sind jedoch letztendlich in der Lage, einige zusammenhängende Komponenten zu verarbeiten (in der Praxis ist dies in der Regel der Fall, da Sie häufig relevante Komponenten hinzufügen, z. B., dass mehr Entitäten in Ihrem System, die über eine Bewegungskomponente verfügen, über eine Renderkomponente verfügen als nicht).

Am wichtigsten ist, dass Sie nach dem Sortieren der Daten keinen Speicherbereich mehr in eine Cache-Zeile laden, um sie dann in einer einzigen Schleife neu zu laden.

Und dies erfordert kein extrem komplexes Design, nur hin und wieder einen Radix-Sortierdurchlauf in linearer Zeit, möglicherweise nachdem Sie eine Reihe von Komponenten für einen bestimmten Komponententyp eingefügt und entfernt haben. An diesem Punkt können Sie sie als markieren sortiert werden müssen. Eine vernünftig implementierte Radix-Sortierung (Sie können sie sogar parallelisieren, was ich auch tue) kann eine Million Elemente in ungefähr 6 ms auf meinem Quad-Core i7 sortieren, wie hier gezeigt:

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 ]

Oben wird eine Million Elemente 32-mal sortiert (einschließlich der Zeit bis zu den memcpyErgebnissen vor und nach dem Sortieren). Und ich gehe davon aus, dass Sie die meiste Zeit nicht wirklich über eine Million Komponenten sortieren müssen. Deshalb sollten Sie dies hier und da problemlos tun können, ohne dass es zu merklichen Bildstörungen kommt.