Wie sind Entity-Systeme Cache-effizient?

In letzter Zeit habe ich viel über Entity-Systeme gelesen, die in meine C ++ / OpenGL-Game-Engine implementiert werden sollen. Die beiden Hauptvorteile, die ich ständig über Entitätssysteme lobte, sind:

1. die einfache Konstruktion neuer Arten von Entitäten, da Sie sich nicht mit komplexen Vererbungshierarchien herumschlagen müssen, und
2. Cache-Effizienz, die ich habe Probleme zu verstehen.

Die Theorie ist natürlich einfach; Jede Komponente wird zusammenhängend in einem Speicherblock gespeichert, sodass das System, das sich um diese Komponente kümmert, einfach die gesamte Liste durchlaufen kann, ohne im Speicher herumspringen und den Cache löschen zu müssen. Das Problem ist, dass ich mir keine Situation vorstellen kann, in der dies tatsächlich praktisch ist.

Schauen wir uns zunächst an, wie die Komponenten gespeichert sind und wie sie aufeinander verweisen. Systeme müssen in der Lage sein, mit mehr als einer Komponente zu arbeiten, dh sowohl das Rendering- als auch das Physiksystem müssen auf die Transformationskomponente zugreifen können. Ich habe eine Reihe möglicher Implementierungen gesehen, die dies ansprechen, und keine von ihnen macht es gut.

Sie können festlegen, dass Komponenten Zeiger auf andere Komponenten oder Zeiger auf Entitäten speichern, die Zeiger auf Komponenten speichern. Sobald Sie jedoch Zeiger in den Mix werfen, wird die Cache-Effizienz bereits beeinträchtigt. Sie können sicherstellen, dass jedes Komponentenarray "n" groß ist, wobei "n" die Anzahl der Entitäten ist, die im System vorhanden sind. Dies macht es sehr schwierig, der Engine neue Komponententypen hinzuzufügen, führt jedoch zu einer Verschlechterung der Cache-Effizienz, da Sie von einem Array zum nächsten springen. Sie könnten Ihr Entity-Array verschachteln, anstatt separate Arrays zu behalten, aber Sie verschwenden immer noch Speicher. Dies macht das Hinzufügen neuer Komponenten oder Systeme unerschwinglich, bietet jedoch den zusätzlichen Vorteil, dass alle alten Ebenen ungültig werden und Dateien gespeichert werden.

Dies setzt voraus, dass Entities in einer Liste, in jedem Frame oder Tick linear verarbeitet werden. In der Realität ist dies nicht oft der Fall. Angenommen, Sie verwenden einen Sektor- / Portal-Renderer oder einen Octree, um Okklusions-Culling durchzuführen. Möglicherweise können Sie Entitäten zusammenhängend innerhalb eines Sektors / Knotens speichern, aber Sie werden herumspringen, ob es Ihnen gefällt oder nicht. Dann haben Sie andere Systeme, die möglicherweise Entitäten bevorzugen, die in einer anderen Reihenfolge gespeichert sind. AI ist möglicherweise in Ordnung, Objekte in einer großen Liste zu speichern, bis Sie anfangen, mit AI LOD zu arbeiten. Dann möchten Sie diese Liste entsprechend der Entfernung zum Player oder einer anderen LOD-Metrik aufteilen. Die Physik wird dieses Oktree benutzen wollen. Skripte kümmern sich nicht darum, sie müssen ausgeführt werden, egal was passiert.

Ich konnte sehen, wie Komponenten zwischen "Logik" (z. B. ai, Skripte usw.) und "Welt" (z. B. Rendering, Physik, Audio usw.) aufgeteilt und jede Liste separat verwaltet wurden, aber diese Listen müssen immer noch miteinander interagieren. KI ist sinnlos, wenn sie den Transformations- oder Animationsstatus, der für das Rendern eines Objekts verwendet wird, nicht beeinflussen kann.

Wie sind Entity-Systeme in einer echten Game-Engine "Cache-effizient"? Vielleicht gibt es einen hybriden Ansatz, den alle verwenden, aber nicht darüber reden, wie Entitäten in einem Array global zu speichern und innerhalb des Octrees zu referenzieren?

Die beiden Hauptvorteile, die ich ständig über Entity-Systeme lobte, sind: 1) die einfache Konstruktion neuer Entity-Typen, da keine komplexen Vererbungshierarchien erforderlich sind, und 2) die Cache-Effizienz.

Beachten Sie, dass (1) ein Vorteil des komponentenbasierten Designs ist und nicht nur von ES / ECS. Sie können Komponenten auf viele Arten verwenden, die nicht über den "System" -Teil verfügen, und sie funktionieren einwandfrei (und viele Indie- und AAA-Spiele verwenden solche Architekturen).

Das Standard-Unity-Objektmodell (using GameObjectund MonoBehaviourobjects) ist kein ECS, sondern ein komponentenbasiertes Design. Die neuere Unity ECS-Funktion ist natürlich eine echte ECS.

Systeme müssen in der Lage sein, mit mehr als einer Komponente zu arbeiten, dh sowohl das Rendering- als auch das Physiksystem müssen auf die Transformationskomponente zugreifen können.

Einige ECS sortieren ihre Komponentencontainer nach Entitäts-ID, dh, die entsprechenden Komponenten in jeder Gruppe befinden sich in derselben Reihenfolge.

Wenn Sie also über eine Grafikkomponente linear iterieren, iterieren Sie auch über die entsprechenden Transformationskomponenten linear. Möglicherweise überspringen Sie einige der Transformationen (da Sie möglicherweise Volumes haben, die von der Physik ausgelöst werden und die Sie nicht rendern oder so). Da Sie jedoch im Speicher immer vorwärts springen (und normalerweise keine besonders großen Entfernungen zurücklegen), fahren Sie immer noch Effizienzgewinne haben.

Dies ähnelt dem empfohlenen Ansatz für HPC für die Struktur von Arrays (SOA). Die CPU und der Cache können mit mehreren linearen Arrays fast genauso gut umgehen wie mit einem einzelnen linearen Array und weitaus besser als mit wahlfreiem Speicherzugriff.

Eine andere Strategie, die in einigen ECS-Implementierungen - einschließlich Unity ECS - verwendet wird, besteht darin, Komponenten basierend auf dem Archetyp ihrer entsprechenden Entität zuzuweisen. Das heißt, alle Entities mit genau der Menge der Komponenten ( PhysicsBody, Transform) werden getrennt von den Entitäten mit unterschiedlichen Komponenten zugeordnet werden (zB PhysicsBody, Transform, und Renderable ).

Systeme in solchen Entwürfen finden zunächst alle Archetypen, die ihren Anforderungen entsprechen (mit dem erforderlichen Satz von Komponenten), iterieren diese Liste der Archetypen und iterieren die in jedem übereinstimmenden Archetyp gespeicherten Komponenten. Dies ermöglicht einen vollständig linearen und echten Zugriff auf O (1) -Komponenten innerhalb eines Archetyps und ermöglicht es Systemen, kompatible Entitäten mit sehr geringem Overhead zu finden (indem eine kleine Liste von Archetypen durchsucht wird, anstatt potenziell Hunderttausende von Entitäten zu durchsuchen).

Sie können festlegen, dass Komponenten Zeiger auf andere Komponenten oder Zeiger auf Entitäten speichern, die Zeiger auf Komponenten speichern.

Komponenten, die auf andere Komponenten derselben Entität verweisen, müssen nichts speichern. Um auf Komponenten anderer Entitäten zu verweisen, speichern Sie einfach die Entitäts-ID.

Wenn eine Komponente für eine einzelne Entität mehr als einmal vorhanden sein darf und Sie auf eine bestimmte Instanz verweisen müssen, speichern Sie die ID der anderen Entität und einen Komponentenindex für diese Entität. Viele ECS-Implementierungen lassen diesen Fall jedoch nicht zu, da diese Vorgänge dadurch weniger effizient werden.

Sie können sicherstellen, dass jedes Komponentenarray "n" groß ist, wobei "n" die Anzahl der Entitäten ist, die im System vorhanden sind

Verwenden Sie Ziehpunkte (z. B. Indizes + Generierungsmarkierungen) und keine Zeiger. Anschließend können Sie die Größe der Arrays ändern, ohne befürchten zu müssen, dass Objektreferenzen beschädigt werden.

Sie können auch einen "Chunked Array" -Ansatz (ein Array von Arrays) verwenden, der vielen gängigen std::dequeImplementierungen ähnelt (allerdings ohne die erbärmlich kleine Chunk-Größe dieser Implementierungen), wenn Sie aus irgendeinem Grund Zeiger zulassen möchten oder wenn Sie Probleme mit gemessen haben Array Resize Performance.

Zweitens wird vorausgesetzt, dass Entitäten in einer Liste bei jedem Frame / Tick linear verarbeitet werden, in der Realität ist dies jedoch nicht oft der Fall

Es hängt von der Entität ab. Ja, für viele Anwendungsfälle ist dies nicht der Fall. In der Tat betone ich deshalb so stark den Unterschied zwischen komponentenbasiertem Design (gut) und Entity-System (eine bestimmte Form von CBD).

Einige Ihrer Komponenten lassen sich problemlos linear verarbeiten. Sogar in normalen "baumlastigen" Anwendungsfällen haben wir definitiv Leistungssteigerungen durch die Verwendung dicht gepackter Arrays gesehen (meistens in Fällen, in denen ein N von höchstens ein paar hundert involviert ist, wie KI-Agenten in einem typischen Spiel).

Einige Entwickler haben auch festgestellt, dass die Leistungsvorteile der Verwendung datenorientierter, linear zugeteilter Datenstrukturen die Leistungsvorteile der Verwendung "intelligenterer" baumbasierter Strukturen überwiegen. Das hängt natürlich vom Spiel und den spezifischen Anwendungsfällen ab.

Angenommen, Sie verwenden einen Sektor- / Portal-Renderer oder ein Octree, um Okklusions-Culling durchzuführen. Möglicherweise können Sie Entitäten zusammenhängend in einem Sektor / Knoten speichern, aber Sie werden herumspringen, ob es Ihnen gefällt oder nicht.

Sie wären überrascht, wie viel das Array noch hilft. Sie springen in einer viel kleineren Speicherregion als "irgendwo" herum, und selbst bei all dem Springen ist die Wahrscheinlichkeit, dass Sie in einem Cache landen, noch viel größer. Mit einem Baum einer bestimmten Größe oder weniger können Sie möglicherweise sogar das gesamte Objekt vorab in den Cache laden, ohne jemals einen Cache-Fehler in diesem Baum zu haben.

Es gibt auch Baumstrukturen, die so gebaut sind, dass sie in dicht gedrängten Reihen leben. Zum Beispiel können Sie mit Ihrem Octree eine haufenartige Struktur verwenden (Eltern vor Kindern, Geschwister nebeneinander) und sicherstellen, dass Sie, selbst wenn Sie den Baum "aufbohren", immer im Array vorwärts iterieren, was hilfreich ist Die CPU optimiert die Speicherzugriffe / Cache-Lookups.

Welches ist ein wichtiger Punkt zu machen. Eine x86-CPU ist ein komplexes Biest. Die CPU führt effektiv einen Mikrocode-Optimierer auf Ihrem Maschinencode aus, zerlegt ihn in kleineren Mikrocode und ordnet Anweisungen neu, sagt Speicherzugriffsmuster usw. voraus. Datenzugriffsmuster sind wichtiger als offensichtlich, wenn Sie nur ein umfassendes Verständnis von haben wie die CPU oder der Cache funktionieren.

Dann haben Sie andere Systeme, die möglicherweise Entitäten bevorzugen, die in einer anderen Reihenfolge gespeichert sind.

Sie können sie mehrmals speichern. Sobald Sie Ihre Arrays auf das Nötigste reduziert haben, sparen Sie möglicherweise Speicher (da Sie Ihre 64-Bit-Zeiger entfernt haben und kleinere Indizes verwenden können).

Sie könnten Ihr Entity-Array verschachteln, anstatt separate Arrays zu behalten, aber Sie verschwenden immer noch Speicher

Dies steht einer guten Cache-Nutzung entgegen. Wenn Sie sich nur um die Transformationen und Grafikdaten kümmern, warum sollte die Maschine dann Zeit damit verbringen, all diese anderen Daten für Physik und KI sowie für Eingabe und Debug und so weiter einzuholen?

Das ist der Punkt, der normalerweise zugunsten von ECS im Vergleich zu monolithischen Spielobjekten gemacht wird (obwohl er im Vergleich zu anderen komponentenbasierten Architekturen nicht wirklich anwendbar ist).

Für das, was es wert ist, verwenden die meisten "produktiven" ECS-Implementierungen, von denen ich weiß, Interleaved Storage. Der bereits erwähnte verbreitete Archetype-Ansatz (der beispielsweise in Unity ECS verwendet wird) wurde sehr explizit entwickelt, um Interleaved Storage für Komponenten zu verwenden, die einem Archetype zugeordnet sind.

KI ist sinnlos, wenn sie den Transformations- oder Animationsstatus, der für das Rendern eines Objekts verwendet wird, nicht beeinflussen kann.

Nur weil AI nicht effizient auf Transformationsdaten linear zugreifen kann, bedeutet dies nicht, dass kein anderes System diese Datenlayoutoptimierung effektiv nutzen kann. Sie können ein gepacktes Array verwenden, um Daten zu transformieren, ohne dass Game-Logic-Systeme die Aufgaben ausführen, die normalerweise von Ad-hoc-Game-Logic-Systemen ausgeführt werden.

Sie vergessen auch den Code-Cache . Wenn Sie den Systemansatz von ECS verwenden (im Gegensatz zu einer eher naiven Komponentenarchitektur), stellen Sie sicher, dass Sie dieselbe kleine Codeschleife ausführen und nicht durch virtuelle Funktionstabellen zu einer Reihe von zufälligen UpdateFunktionen springen , die überall verstreut sind Ihre Binärdatei. Im KI-Fall möchten Sie also wirklich alle Ihre verschiedenen KI-Komponenten (da Sie mit Sicherheit mehr als eine haben, um Verhalten zu komponieren!) In separaten Buckets aufbewahren und jede Liste separat verarbeiten, um die bestmögliche Nutzung des Code-Cache zu erzielen.

Mit einer verzögerten Ereigniswarteschlange (bei der ein System eine Liste von Ereignissen generiert, diese jedoch erst dann auslöst, wenn das System die Verarbeitung aller Entitäten abgeschlossen hat) können Sie sicherstellen, dass Ihr Code-Cache ordnungsgemäß verwendet wird, während Ereignisse gespeichert werden.

Mit einem Ansatz, bei dem jedes System weiß, aus welchen Ereigniswarteschlangen für den Frame gelesen werden muss, können Sie das Lesen von Ereignissen sogar beschleunigen. Zumindest schneller als ohne.

Denken Sie daran, Leistung ist nicht absolut. Sie müssen nicht jeden einzelnen Cache-Fehler beseitigen, um die Leistungsvorteile eines guten datenorientierten Designs zu erkennen.

Es wird immer noch aktiv geforscht, wie viele Spielesysteme mit ECS-Architektur und datenorientierten Entwurfsmustern besser funktionieren. Ähnlich wie einige der erstaunlichen Dinge, die wir in den letzten Jahren mit SIMD gesehen haben (z. B. JSON-Parser), werden immer mehr Dinge mit ECS-Architekturen gemacht, die für klassische Spielearchitekturen nicht intuitiv erscheinen, aber eine Reihe von Möglichkeiten bieten Vorteile (Geschwindigkeit, Multithreading, Testbarkeit usw.).

Oder vielleicht gibt es einen hybriden Ansatz, über den alle reden, aber niemand spricht

Dies ist, was ich in der Vergangenheit empfohlen habe, insbesondere für Leute, die der ECS-Architektur skeptisch gegenüberstehen: Verwenden Sie gute datenorientierte Ansätze für Komponenten, bei denen die Leistung kritisch ist. Verwenden Sie einfachere Architekturen, bei denen die Einfachheit die Entwicklungszeit verkürzt. Machen Sie nicht jede einzelne Komponente zu einer strengen Überdefinition der Komponenten, wie sie ECS vorschlägt. Entwickeln Sie Ihre Komponentenarchitektur so, dass Sie ECS-ähnliche Ansätze problemlos dort verwenden können, wo sie sinnvoll sind, und einfachere Komponentenstrukturen verwenden können, wo ECS-ähnliche Ansätze keinen Sinn ergeben (oder weniger sinnvoll sind als Baumstrukturen usw.). .

Ich persönlich bin ein relativ neuer Konvertit zur wahren Kraft von ECS. Für mich war der ausschlaggebende Faktor jedoch etwas, das selten an ECS erwähnt wurde: Es macht das Schreiben von Tests für Spielesysteme und Logik im Vergleich zu den eng gekoppelten logikgeladenen komponentenbasierten Designs, mit denen ich in der Vergangenheit gearbeitet habe, fast trivial. Da ECS-Architekturen die gesamte Logik in Systemen ablegen, die nur Komponenten verbrauchen und Komponentenaktualisierungen erzeugen, ist das Erstellen einer "Schein" -Komponentengruppe zum Testen des Systemverhaltens recht einfach. Da die meisten Spielelogiken ausschließlich in Systemen ausgeführt werden sollen, bedeutet dies, dass das Testen aller Ihrer Systeme eine relativ hohe Codeabdeckung Ihrer Spielelogik bietet. Systeme können Scheinabhängigkeiten (z. B. GPU-Schnittstellen) für Tests verwenden, bei denen die Komplexität oder Leistung weitaus geringer ist als bei Ihnen.

Abgesehen davon können Sie feststellen, dass viele Leute über ECS sprechen, ohne wirklich zu verstehen, was es überhaupt ist. Ich sehe die klassische Unity, die als ECS bezeichnet wird, mit bedrückender Häufigkeit. Dies zeigt, dass zu viele Spieleentwickler "ECS" mit "Komponenten" gleichsetzen und den Teil "Entity System" so gut wie ignorieren. Im Internet steckt eine Menge Liebe in ECS, wenn ein großer Teil der Menschen sich wirklich nur für komponentenbasiertes Design und nicht für tatsächliches ECS einsetzt. An dieser Stelle ist es fast sinnlos, darüber zu streiten. ECS wurde von seiner ursprünglichen Bedeutung in einen Oberbegriff umgewandelt, und Sie können auch akzeptieren, dass "ECS" nicht dasselbe bedeutet wie "datenorientiertes ECS". : /