Wie profitiert man vom CPU-Cache in einer Spiel-Engine mit Entity-Komponenten-Systemen?

15

Ich habe oft in den ECS-Game-Engine-Dokumentationen gelesen, dass eine gute Architektur ist, um den CPU-Cache mit Bedacht einzusetzen.

Ich kann mir jedoch nicht vorstellen, wie wir vom CPU-Cache profitieren können.

Wenn Komponenten in einem Array (oder einem Pool) im zusammenhängenden Speicher gespeichert werden, ist dies eine gute Möglichkeit, den CPU-Cache zu verwenden, ABER nur, wenn die Komponenten nacheinander gelesen werden.

Wenn wir Systeme verwenden, benötigen sie eine Entitätenliste, die eine Liste von Entitäten mit Komponenten mit bestimmten Typen enthält.

Diese Listen geben die Komponenten jedoch auf zufällige Weise und nicht nacheinander wieder.

Wie kann man ein ECS entwerfen, um den Cachetreffer zu maximieren?

EDIT:

Beispielsweise benötigt ein physisches System eine Entitätsliste für eine Entität mit den RigidBody- und Transform-Komponenten (es gibt einen Pool für RigidBody- und einen Pool für Transform-Komponenten).

Die Schleife zum Aktualisieren von Entitäten sieht also folgendermaßen aus:

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
}

Das Problem besteht darin, dass sich die RigidBody-Komponente von entity1 am Index 2 ihres Pools und die Tranform-Komponente von entity1 am Index 0 ihres Pools befinden kann (da einige Entitäten einige Komponenten haben können und nicht die andere, und weil Entitäten hinzugefügt / gelöscht werden / Komponenten zufällig).

Selbst wenn Komponenten im Arbeitsspeicher zusammenhängend sind, werden sie zufällig gelesen und haben daher mehr Cache-Fehler, oder?

Gibt es keine Möglichkeit, die nächsten Komponenten in der Schleife vorab abzurufen?

Johnmph
quelle
Können Sie uns zeigen, wie Sie die einzelnen Komponenten zuordnen?
concept3d
Mit einem einfachen Pool-Allokator und einem Handle-Manager für die Verwaltung der Verlagerung von Komponenten im Pool (um die Komponenten zusammenhängend im Speicher zu halten).
Johnmph
In Ihrer Beispielschleife wird davon ausgegangen, dass Komponentenaktualisierungen pro Entität verschachtelt sind. In vielen Fällen ist es möglich, Komponenten in großen Mengen nach Komponententyp zu aktualisieren (z. B. zuerst alle Starrbody-Komponenten und dann alle Transformationen mit den fertigen Starrbody-Daten und dann alle Rendering-Daten mit den neuen Transformationen aktualisieren ...) - dies kann den Cache verbessern Verwenden Sie für jedes Komponenten-Update. Ich denke, diese Art von Struktur ist das, was Nick Wiggill unten vorschlägt.
DMGregory
Es ist mein schlechtes Beispiel, in der Tat, es ist eher das System "alle Transformationen mit den fertigen Starrkörperdaten aktualisieren" als das System "Physik". Das Problem bleibt jedoch das gleiche: In diesen Systemen (Update-Transformation mit starrem Körper, Update-Rendering mit Transformation, ...) müssen mehrere Komponententypen gleichzeitig vorhanden sein.
Johnmph
Nicht sicher, ob dies auch relevant sein kann? gamasutra.com/view/feature/6345/…
DMGregory

Antworten:

13

Mick Wests Artikel erklärt den vollständigen Prozess der Linearisierung von Daten von Entitätskomponenten. Bei der Tony Hawk-Serie funktionierte es vor Jahren mit viel weniger beeindruckender Hardware als heute, um die Leistung erheblich zu verbessern. Grundsätzlich verwendete er globale, vorab zugewiesene Arrays für jeden bestimmten Typ von Entitätsdaten (Position, Punktzahl und so weiter) und referenzierte jedes Array in einer bestimmten Phase seiner systemweiten update()Funktion. Sie können davon ausgehen, dass sich die Daten für jede Entität in jedem dieser globalen Arrays auf demselben Arrayindex befinden. Wenn also der Player zuerst erstellt wird, befinden sich die Daten möglicherweise [0]in jedem Array unter.

Noch spezifischer für die Cache-Optimierung sind die Folien von Christer Ericsson für C und C ++.

Um ein bisschen mehr Details zu geben, sollten Sie versuchen, zusammenhängende Speicherblöcke (am einfachsten als Arrays zuzuweisen) für jeden Datentyp (z. B. Position, xy und z) zu verwenden, um eine gute Referenzlokalität zu gewährleisten, wobei jeder dieser Datenblöcke einzeln verwendet wird update()Phasen aus Gründen der zeitlichen Lokalität, dh um sicherzustellen, dass der Cache nicht über den LRU-Algorithmus der Hardware geleert wird, bevor Sie innerhalb eines bestimmten update()Aufrufs Daten wiederverwenden, die Sie wiederverwenden möchten . Wie Sie bereits angedeutet haben, möchten Sie Ihre Entitäten und Komponenten nicht über als diskrete Objekte zuweisen new, da dann Daten unterschiedlicher Typen auf jeder Entitätsinstanz verschachtelt werden, wodurch die Referenzlokalität verringert wird.

Wenn Sie Abhängigkeiten zwischen Komponenten (Daten) haben, die es sich absolut nicht leisten können, einige Daten von den zugehörigen Daten zu trennen (z. B. Transformieren + Physik, Transformieren + Renderer), können Sie die Replikation von Transformationsdaten in den Arrays "Physik" und "Renderer" wählen Dies stellt sicher, dass alle relevanten Daten für jede leistungskritische Operation in die Cache-Zeilenbreite passen.

Denken Sie auch daran, dass der L2- und L3-Cache (sofern Sie dies für Ihre Zielplattform annehmen können) viel dazu beiträgt, die Probleme des L1-Caches, wie z. B. eine beschränkte Zeilenbreite, zu verringern. Dies sind also selbst bei einem L1-Fehler Sicherheitsnetze, die am häufigsten Callouts in den Hauptspeicher verhindern, der um Größenordnungen langsamer ist als Callouts in eine beliebige Cache-Ebene.

Hinweis zum Schreiben von Daten Das Schreiben wird nicht in den Hauptspeicher aufgerufen. Standardmäßig ist auf heutigen Systemen das Write-Back-Caching aktiviert: Beim Schreiben eines Werts wird dieser nur (anfangs) in den Cache und nicht in den Hauptspeicher geschrieben, sodass dies keine Engpässe mit sich bringt. Nur wenn Daten aus dem Hauptspeicher angefordert werden (dies geschieht nicht im Cache) und veraltet sind, wird der Hauptspeicher aus dem Cache aktualisiert.

Ingenieur
quelle
1
Nur ein Hinweis für alle, die C ++ noch nicht kennen: Es std::vectorhandelt sich im Grunde genommen um ein Array, dessen Größe sich dynamisch ändern lässt, und das daher auch zusammenhängend ist (de facto in älteren C ++ - Versionen und de jure in neueren C ++ - Versionen). Einige Implementierungen von std::dequesind auch "zusammenhängend genug" (wenn auch nicht von Microsoft).
Sean Middleditch
2
@ Johnmph Ganz einfach: Wenn Sie keine Referenzlokalität haben, haben Sie nichts. Wenn zwei Daten eng miteinander verbunden sind (z. B. räumliche und physikalische Informationen), dh wenn sie zusammen verarbeitet werden, müssen Sie sie möglicherweise als eine einzige verschachtelte Komponente komprimieren. Beachten Sie jedoch, dass jede andere Logik (z. B. KI), die diese räumlichen Daten nutzt, unter der Nichteinbeziehung der räumlichen Daten leiden kann . Es kommt also darauf an, was die meiste Leistung erfordert (in Ihrem Fall vielleicht die Physik). Ist das sinnvoll?
Ingenieur
1
@Johnmph Ja, ich stimme Nick voll und ganz zu. Es geht darum, wie sie im Speicher gespeichert sind. Wenn Sie eine Entität mit Zeigern auf zwei Komponenten haben, die weit im Speicher entfernt sind, haben Sie keine Lokalität. Sie müssen in eine Cache-Zeile passen.
concept3d
2
@ Johnmph: In der Tat geht Mick Wests Artikel von minimalen Abhängigkeiten aus. Also: Abhängigkeiten minimieren; Replizieren Daten entlang Cache - Zeilen , wo Sie diese Abhängigkeiten nicht minimieren kann ... zB umfassen Transformation neben sowohl Starrkörper und Render; und um Cache-Zeilen anzupassen, müssen Sie möglicherweise Ihre Datenatome so weit wie möglich reduzieren ... Dies könnte teilweise dadurch erreicht werden, dass Sie vom Fließkomma zum Festkomma (4 Bytes vs 2 Bytes) pro Dezimalpunktwert wechseln. Aber auf die eine oder andere Weise müssen Ihre Daten, egal wie Sie es tun, der Cache-Zeilenbreite entsprechen, wie in concept3d angegeben, um maximale Leistung zu erzielen.
Ingenieur
2
@ Johnmph. Nein. Wenn Sie Transformationsdaten schreiben, schreiben Sie diese einfach in beide Arrays. Es sind nicht die Schriften, um die Sie sich Sorgen machen müssen. Sobald Sie ein Schreiben abschicken, ist es so gut wie erledigt. Es sind die Lesevorgänge , die zu einem späteren Zeitpunkt in der Aktualisierung ausgeführt werden, wenn Sie Physics and Renderer ausführen und in einer einzigen Cache-Zeile direkt in der Nähe der CPU auf alle relevanten Daten zugreifen müssen . Auch, wenn Sie es wirklich alle zusammen müssen, dann tun Sie entweder weiter Replikationen oder Sie sicher , dass die Physik machen, verwandeln und machen eine einzelne Cache - Zeile passen ... 64 Byte ist üblich und ist eigentlich recht viele Daten ...!
Ingenieur