[C++] Notizen zu Datenorientierung

[CodingCat]

Damit nicht alles in den üblichen Threads versinkt, werde ich hier Notizen zu meinem Übergang zu mehr datenorientiertem Entwurf sammeln.
Eigene Erfahrungen, elegantere Lösungen, Anmerkungen und Fragen bitte hier kundtun.

Bewegliche Objekte

Die Grundidee von datenorientiertem Entwurf ist es, gemeinsam verarbeitete Daten gemäß der Verarbeitungsreihenfolge auch im Speicher beisammen zu halten. Das funktioniert am besten in zustandsarmen Anwendungen, in denen alle Daten von vorneherein bekannt und unveränderlich sind. Leider sind diese Voraussetzungen in der Realität kaum anzutreffen.

Sobald Daten ohne feste Maximalzahl hinzugefügt werden können, muss Speicher realloziiert werden, der Speicherbereich kann sich nach belieben verschieben, bestehende feste Zeiger auf Datenelemente werden ungültig. Abhilfe schaffen Indizes, welche die Position des referenzierten Datenelements relativ zur Basisadresse des Speicherbereichs angeben.

Können weiterhin Daten aus der Mitte entfernt werden, so müssen einzelne Elemente (im ungeordneten Fall) oder Elementbereiche (im geordneten Fall) verschoben werden. Hier helfen auch feste Indizes nicht mehr, denn auch die relative Position eines referenzierten Elements ändert sich im Lauf der Programmausführung. Abhilfe schaffen Handles, welche wie Einzelobjekte fix im Speicher liegen und ihrererseits mit Indizes die individuellen Datenelemente referenzieren. Diese Handles werden stets gemeinsam mit den Datenelementen aktualisiert, bei Einfüge- oder Löschoperationen werden die enthaltenen Indizes korrigiert. Für solche Handles bietet sich ein Pool Allocator mit eingebetteter Free List an.

Mit Handles und Indizes haben wir die Zahl der Indirektionen bei einfachen Datenzugriff nun von einer auf drei erhöht. Obendrein ist die Verwaltungslogik für Datenelemente wesentlich komplexer geworden, Elemente müssen verschoben werden, Handles müssen verwaltet und aktualisiert werden. Der Fall, in dem wir Gewinnen, ist die Verarbeitung sehr vieler Elemente am Stück, in Reihenfolge ihrer Positionierung im Speicher. Es ist klar, dass sich dieser Aufwand nur dann lohnt, wenn die Verarbeitung in der Gruppe der Regelfall und Einzelzugriff der Einzelfall ist.

[CodingCat]

Parallele Arrays

Arbeitet man (z.B. aus oben genannten Gründen) mit Indizes, lassen sich die Daten großer komplexer Datenelemente entsprechend ihrer Verarbeitungsstufen gruppieren, um in einzelnen Verarbeitungsstufen ungenutzte Datenteile dort gar nicht erst in die Caches zu laden. Betrachtet man zum Beispiel einen simplen Renderer, so werden dort im Culling nur die Ausdehnungen der darzustellenden Objekte benötigt, nicht jedoch Geometrie, Shaders und andere Ressourcen. Im Rendering hingegen spielen die Ausdehnungen keine Rolle, dafür werden die Grafikressourcen benötigt.

Mit objektorientiertem Entwurf hat man es hier schwer, die jeweils irrelevanten Daten bei der Traversierung aller Objekte aus der Speicherhierarchie herauszuhalten. Im datenorientierten Fall hingegen erfordert dies nicht mehr als die Aufteilung eines Datenarrays in zwei parallele Datenarrays. Die Teildaten einzelner Datenelemente liegen dabei in beiden Arrays an der gleichen relativen Position, haben also den gleichen Index. So enthielte im genannten Beispiel ein Array nur die Ausdehnungen der darzustellenden Objekte, das andere Array nur die Grafikressourcen. Ein Objekt lässt sich nach wie vor über einen einzigen Index referenzieren: bounds[index] liefert die Ausdehnung, graphics[index] die Grafikressourcen.

[CodingCat]

Liegen Daten intern erstmal schön lückenlos hintereinander, sollte nicht nur die interne Datenverarbeitung davon profitieren. Datenorientierter Entwurf muss (und sollte) nicht heißen, dass sämtliche Errungenschaften bezüglich Aufgabenteilung und Entkopplung in den Wind geschlagen werden. Vielmehr sollte auch der Entwurf der öffentlichen API dem datenorientierten Grundsatz folgen, "Where there's one, there's many". (Meine etwas entschärfte Version lautet übrigens: "Where there's more than one, there's many.")

Rückgabe vieler Elemente

Betrachten wir folgendes generische API-Beispiel:

Code: Alles auswählen

size_t GetElementCount() const;
Element GetElement(size_t idx) const;

Diese API ist nicht nur extrem unbequem zu benutzen, sondern obendrein unnötig ineffizient. Haben wir einen Compiler mit Link-time Code Generation zur Verfügung, so werden sämtliche Get-Aufrufe mit etwas Glück herausoptimiert, andernfalls haben wir für jedes Element einen vollkommen unnötigen Funktionsauruf.

Viele APIs bieten deshalb folgende Variante:

Code: Alles auswählen

size_t GetElementCount() const;
size_t GetElements(Element *elements, size_t maxCount) const;

GetElements() kopiert maximal maxCount Elemente in den gegebenen Speicherbereich und gibt die Anzahl der tatsächlich kopierten Elemente zurück. Hier sparen wir uns die Funktionsaufrufe pro Element, benötigen aber gegebenenfalls einen sehr großen temporären Speicherbereich, um alle Elemente aufzunehmen. Bequemer als die erste Variante ist diese Variante damit in den seltensten Fällen.

Im Optimalfall haben wir bei datenorientiertem Entwurf intern ohnehin alle Daten schön gruppiert in parallelen Arrays. In diesem Fall hindert uns nichts daran, teile dieser Daten direkt öffentlich zugänglich zu machen. Hier bietet sich eine Range-Struktur an:

Code: Alles auswählen

template <class Index>
struct Range
{
	typedef Index index_type; ///< Index type;
	typedef Index iterator;   ///< Index type;

	Index Begin; ///< Beginning of the range.
	Index End;   ///< End of the range.

	/// Empty range constructor.
	Range()
		: Begin(), End() { }
	/// Range constructor.
	Range(Index begin, Index end)
		: Begin(begin), End(end) { }
};

/// Makes a range from the given pointers.
/// @relatesalso Range
template <class Pointer>
inline Range<Pointer> MakeRange(Pointer begin, Pointer end)
{
	return Range<Pointer>(begin, end);
}

/// Makes a range from the given pointers.
/// @relatesalso Range
template <class Pointer>
inline Range<Pointer> MakeRangeN(Pointer begin, size_t count)
{
	return Range<Pointer>(begin, static_cast<Pointer>(begin + count));
}

/// @relates Range
/// @{

/// Gets the size.
template <class Pointer>
inline size_t Size(const Range<Pointer> &range) { return range.End - range.Begin; }

/// Gets the beginning (for each compatibility).
template <class Pointer>
inline Pointer begin(const Range<Pointer> &range) { return range.Begin; }
/// Gets the end (for each compatibility).
template <class Pointer>
inline Pointer end(const Range<Pointer> &range) { return range.End; }

Damit lässt sich die API für Elementzugriff in eine sehr kompakte Form bringen:

Code: Alles auswählen

Range<const Element*> GetElements() const;

Diese eine Funktion liefert uns sowohl Elementanzahl als auch Direktzugriff auf alle Elemente. Obendrein erlauben uns die Überladungen von begin und end eine direkte Nutzung in C++11' Range-Based For:

Code: Alles auswählen

Range<const Element*> elements = foo.GetElements();
Size(elements); // Liefert Elementzahl
elements.Begin[0]; // Liefert erstes Element
elements.End[-1]; // Liefert letztes Element

// Traversierung in Range-Based For
for (auto &&element : foo.GetElements())
{
   element.foobar; // Nutze Element
}

[Jonathan]

Wenn ich meinen Renderer neu schreibe, werde ich darauf auch auf jeden Fall achten. OOP ist ja ganz schön und hilft auch echt, komplexe Probleme einfach zu halten, aber irgendwann wird der Verwaltungskram um die Daten herum einfach zu viel. Wenn man die Wahl hat, irgendeinen Zeiger durch zig Konstruktoren durchzugeben, oder endlose Getter-Ketten im untersten Objekt zu benutzen, macht beides irgendwie keinen Spaß. Und natürlich soetwas wie Laden und Speichern von Dateien, wo man dann jedes Objekt einzeln speichert und in jedem Objekt noch zig kleine Variablen.
Bei meinem aktuellen Renderer nervt mich das echt ein wenig, obwohl sich die Klassen Aufteilung im Grunde sehr solide und sinnvoll anhört.

Das Problem am datenorientierten Ansatz sehe ich im Moment noch darin, dass man vorher alles möglichst gut planen sollte. Durch die "flache Struktur", also alle Daten liegen irgendwo in riesigen Arrays, entstehen bestimmt schnell Probleme, die man mit einer schönen OOP-Kapselung nicht hätte. Aber wenn erst einmal alles aufgeräumt an einer Stelle liegt, erhoffe ich mir, wesentlich schneller durchzublicken, als wenn alles in kleinen Objekten in irgendwelchen kleinen Dateien schlummert.

Wirklich gemacht hab ich in diese Richtung noch nichts, aber ich werde die Diskussion hier mit Interesse verfolgen. Gerade durch sowas wie erhöte Cache-Trefferraten und einlesen von Dateien in großen Blöcken erwarte ich einen deutlichen Geschwindigkeitsvorteil.

[CodingCat]

Das Problem am datenorientierten Ansatz sehe ich im Moment noch darin, dass man vorher alles möglichst gut planen sollte. Durch die "flache Struktur", also alle Daten liegen irgendwo in riesigen Arrays, entstehen bestimmt schnell Probleme, die man mit einer schönen OOP-Kapselung nicht hätte. Aber wenn erst einmal alles aufgeräumt an einer Stelle liegt, erhoffe ich mir, wesentlich schneller durchzublicken, als wenn alles in kleinen Objekten in irgendwelchen kleinen Dateien schlummert.

Du musst für Datenorientierung nicht sämtliche Objektorientierung fallen lassen. Letztlich schiebst du die Objektorientierung einfach nur eine Ebene höher, an Stelle von Einzelobjekten hast du dann Gruppenobjekte. Auch Polymorphie ist damit nach wie vor kein Problem, polymorph sind eben nur die Gruppen an Stelle der Einzelobjekte. Das hat den netten Nebeneffekt, dass sämtliche virtuellen Methodenaufrufe nur einmal für alle Objekte desselben Typs aufgelöst werden müssen.

OOP ist ja ganz schön und hilft auch echt, komplexe Probleme einfach zu halten, aber irgendwann wird der Verwaltungskram um die Daten herum einfach zu viel. Wenn man die Wahl hat, irgendeinen Zeiger durch zig Konstruktoren durchzugeben, oder endlose Getter-Ketten im untersten Objekt zu benutzen, macht beides irgendwie keinen Spaß. Und natürlich soetwas wie Laden und Speichern von Dateien, wo man dann jedes Objekt einzeln speichert und in jedem Objekt noch zig kleine Variablen.
Bei meinem aktuellen Renderer nervt mich das echt ein wenig, obwohl sich die Klassen Aufteilung im Grunde sehr solide und sinnvoll anhört.

Geht mir ähnlich. Wirklich schön an der datenorientierten Gruppierung nach Objekttyp ist, dass man tatsächlich ganz natürlich für Gruppen optimieren kann. So hast du zum Beispiel alle Meshes schön sortiert vorliegen und kannst Bereiche gleicher Meshes für Instancing einfach in deinem entsprechenden Array ablesen, anstatt Instanzen in irgendwelchen Instancing Managern registrieren zu müssen.

[Jonathan]

Du musst für Datenorientierung nicht sämtliche Objektorientierung fallen lassen. Letztlich schiebst du die Objektorientierung einfach nur eine Ebene höher, an Stelle von Einzelobjekten hast du dann Gruppenobjekte.

Hm, hört sich gut an. Wenn ich das ganze mal anfangen sollte, werde ich meine Planung hier vorstellen, dann kann man das Thema mal am konkreten Fall diskutieren, was sicherlich noch mehr Einblicke bringt.

[Punika]

Hi

ich finde den Beitrag recht interessant, was ich aber noch nicht ganz verstehe ist der Vorteil der Handles. Nehmen wir einfach mal ein einfaches Beispiel. Du hast ein Array von Transformationen (z.B. von allen Objekten in der Welt). Nehmen wir mal an das ein paar deaktiviert sind, oder eben ein paar Objekte neu hinzugekommen sind oder ein paar gelöscht wurden sind. Nun hast du ja auch dein Array von Handles aktualisiert. Aber soweit ich verstanden habe änderst du nicht dein Transformationen Array?
Oder änderst du beides, und dann die Frage wie oft? Wenn ich mir nämlich die meisten Docs dazu ansehe verzichtet man oft darauf das Array neu zu erstellen und nimmt in den oben genannten Fällen es manchmal in Kauf das hier 2-3 Transformationen mehr berechnet werden.
Und falls du die änderst, kannst du da irgendwelche Performance Werte angeben. Tendenz reicht ;)
Im großen und ganzen, wenn ich es richtig verstanden habe, ist der große Vorteil von Datenorientierung die Reduzierung von Cache Misses. Mich würde mal interessieren wie du dann z.B. Bäume aufbaust. Liegen die Nodes dann im Array so wie du sie traversierst?
Und als letzte Frage, wie sieht das mit Laden und Speichern aus. Lädst du Objekte traditionell als eigene Objekte (z.B. Meshes) und erstellt dann deine Arrays passend für den Renderer?

Vielleicht noch eine Frage :) Ich denke mal das ein einzelnes Entity/Actor...was weiß ich... im Endeffekt nur ein Handle ist in die einzelnen Arrays (z.B. Transformation, Mesh, Licht usw.), haben dabei deine Handles irgendeine Logik was sie sind? Also ich denke darüber nach eben Componenten Datenorientiert umzubauen. Nun bräuchte ich entweder so eine Art Liste von Handles die ein Entity hat, die dann meine Komponenten dar stellen oder als Lösung zu sagen, mit einem Handle kann ich auf alles "zugreifen" bzw. kann ich dem Handle auch Fragen stellen ob ich ein Mesh habe, ob ich ein Licht habe. Nützlich wäre es eben dann Arrays aufzubauen, je nach dem was sichtbar/aktualisiert werden muss. Um dann die restliche Zeit komplett Datenorientiert meine Welt zu zeichnen bzw. zu aktualisieren.

Grüße

Lutz

[CodingCat]

ich finde den Beitrag recht interessant, was ich aber noch nicht ganz verstehe ist der Vorteil der Handles. Nehmen wir einfach mal ein einfaches Beispiel. Du hast ein Array von Transformationen (z.B. von allen Objekten in der Welt). Nehmen wir mal an das ein paar deaktiviert sind, oder eben ein paar Objekte neu hinzugekommen sind oder ein paar gelöscht wurden sind. Nun hast du ja auch dein Array von Handles aktualisiert. Aber soweit ich verstanden habe änderst du nicht dein Transformationen Array?

Es werden stets alle Arrays parallel gehalten, d.h. wenn ein Entity in der Liste wegen Löschung eines anderen verschoben wird, werden die Einträge in allen Arrays parallel verschoben und das Handle wird entsprechend aktualisiert, so dass es wieder mit einem Index in allen Arrays die richtigen Elemente referenziert. Performance ist mir an dieser Stelle unwichtig, weil ich davon ausgehe, das fast nie einzelne Entities gelöscht werden. Hinzufügen geht am Ende der Arrays, da muss also nichts verschoben oder aktualisiert werden, Performance kein Problem.

Im großen und ganzen, wenn ich es richtig verstanden habe, ist der große Vorteil von Datenorientierung die Reduzierung von Cache Misses. Mich würde mal interessieren wie du dann z.B. Bäume aufbaust. Liegen die Nodes dann im Array so wie du sie traversierst?

Bäume habe ich nicht. Um die Daten für Baumtraversierung zu optimieren, musst du sie jedoch einfach nur in Traversierungsreihenfolge in den Speicher legen. Dann entspricht eine Traversierung wieder nur einem linearen Scan, ggf. mit Sprüngen.

Und als letzte Frage, wie sieht das mit Laden und Speichern aus. Lädst du Objekte traditionell als eigene Objekte (z.B. Meshes) und erstellt dann deine Arrays passend für den Renderer?

Ganz genau, ich habe die Meshes erstmal als Objekte rumliegen, die Buffers etc. referenzieren, und lasse dann den MeshController-Manager, das Gruppenobjekt für MeshControllers (vermutlich das, was du Komponenten nennst), für das Rendering der Entities, an die ein MeshController geheftet wurde, die Mesh-Objekte auseinandernehmen und zu flachen Datenarrays für den Renderer neu zusammensetzen.

Vielleicht noch eine Frage :) Ich denke mal das ein einzelnes Entity/Actor...was weiß ich... im Endeffekt nur ein Handle ist in die einzelnen Arrays (z.B. Transformation, Mesh, Licht usw.), haben dabei deine Handles irgendeine Logik was sie sind? Also ich denke darüber nach eben Componenten Datenorientiert umzubauen. Nun bräuchte ich entweder so eine Art Liste von Handles die ein Entity hat, die dann meine Komponenten dar stellen oder als Lösung zu sagen, mit einem Handle kann ich auf alles "zugreifen" bzw. kann ich dem Handle auch Fragen stellen ob ich ein Mesh habe, ob ich ein Licht habe.

An dieser Stelle habe ich in der Tat einfach eine Liste von Controller-Handles pro Entity, die ebenfalls als Entity-Daten-Array linear hintereinander liegen (d.h. jedes Entity referenziert ein Intervall von Controller-Handles). Für allgemeine Update-Funktionalität sehe ich hier momentan auch kaum einen sinnvollen Weg, auf Einzelobjektpolymorphie zu verzichten. Meine Controller-Handles sind deshalb gleichzeitig polymorphe Objekte, die virtuelle Aufrufe einfach an das Gruppenobjekt der jeweiligen Controller-Klasse weiterleiten. Dieser Teil ist nicht sonderlich datenorientiert, hier habe ich aber auch keinen großen Ehrgeiz, weil derlei generische Updates sich ohnehin auf einen vergleichsweise kleinen Teil dynamischer Objekte beschränken sollten. Wenn mir was besseres einfällt, gebe ich Bescheid. ;)

Nützlich wäre es eben dann Arrays aufzubauen, je nach dem was sichtbar/aktualisiert werden muss. Um dann die restliche Zeit komplett Datenorientiert meine Welt zu zeichnen bzw. zu aktualisieren.

Genau so läuft das dann. Sichtbare Objekte werden per Index eingesammelt, für diese pro gerenderter Render Queue die Passes eingesammelt, diese Passes sortiert etc. Auch für die Updates baue ich ein Index-Array von veränderten Entities. Das lässt sich ganz einfach bewerkstelligen, indem man sich pro Entity in ein Flag speichert, ob das Entity in diesem Aktualisierungszyklus bereits verändert wurde; sofern nicht, wird bei der (dann ersten) Änderung der Index des veränderten Entities in die Aktualisierungsliste aufgenommen. So hat man direkt eine Aktualisierungsliste ohne Duplikate.

[Punika]

Es werden stets alle Arrays parallel gehalten, d.h. wenn ein Entity in der Liste wegen Löschung eines anderen verschoben wird, werden die Einträge in allen Arrays parallel verschoben und das Handle wird entsprechend aktualisiert, so dass es wieder mit einem Index in allen Arrays die richtigen Elemente referenziert. Performance ist mir an dieser Stelle unwichtig, weil ich davon ausgehe, das fast nie einzelne Entities gelöscht werden. Hinzufügen geht am Ende der Arrays, da muss also nichts verschoben oder aktualisiert werden, Performance kein Problem.

Okay, dann hatte ich das so im Großen und Ganzen richtig verstanden. Wie machst du denn das, bei Objekten die z.B. deaktiviert oder nur sehr kurzlebig sind (z.B. Explosionen oder sowas). Behältst du da einfach die im Array drin, hast aber eine Art Flag die dir ansagt ob du den Eintrag aktualisieren musst oder nicht? Überlege gerade wie ich vernünftig von Sprüngen durch if Abfragen etc. weg komme. Eine simple Möglichkeit wäre z.B. eben diese Einträge drinnen zu lassen aber mit Werte zu versehen die nichts in der Logik ändern. Bei Transformationen ja recht einfach. Die dürfen eben nur keine Rolle später bei Kollision oder sonstigem Spielen. Was du ja wie beschrieben durch Index Arrays sowieso rausfilterst.

Bäume habe ich nicht. Um die Daten für Baumtraversierung zu optimieren, musst du sie jedoch einfach nur in Traversierungsreihenfolge in den Speicher legen. Dann entspricht eine Traversierung wieder nur einem linearen Scan, ggf. mit Sprüngen.

Nur aus Interesse halber, Sichtbarkeit ohne eine Art von Baum?

An dieser Stelle habe ich in der Tat einfach eine Liste von Controller-Handles pro Entity, die ebenfalls als Entity-Daten-Array linear hintereinander liegen (d.h. jedes Entity referenziert ein Intervall von Controller-Handles). Für allgemeine Update-Funktionalität sehe ich hier momentan auch kaum einen sinnvollen Weg, auf Einzelobjektpolymorphie zu verzichten. Meine Controller-Handles sind deshalb gleichzeitig polymorphe Objekte, die virtuelle Aufrufe einfach an das Gruppenobjekt der jeweiligen Controller-Klasse weiterleiten. Dieser Teil ist nicht sonderlich datenorientiert, hier habe ich aber auch keinen großen Ehrgeiz, weil derlei generische Updates sich ohnehin auf einen vergleichsweise kleinen Teil dynamischer Objekte beschränken sollten. Wenn mir was besseres einfällt, gebe ich Bescheid. ;)

Also beim Thema "zugriff" fiel mir Spontan eben Hash Tabellen ein. Damit hättest du ein Handle die du auf den verschiedenen Gruppenobjekten benutzen kannst. -> Index to Index sollte ja recht schnell sein. Wie du geschrieben hattest gehts ja wirklich nur darum mal gelegentlich vielleicht ein Licht ein oder auszuschalten und sonstiges. Wobei bei so etwas sich sowieso ein eigenes Array eignen würde, da man dann bei Multithreading das ganze schon mal auf ein Array begrenzen würde.

Genau so läuft das dann. Sichtbare Objekte werden per Index eingesammelt, für diese pro gerenderter Render Queue die Passes eingesammelt, diese Passes sortiert etc. Auch für die Updates baue ich ein Index-Array von veränderten Entities. Das lässt sich ganz einfach bewerkstelligen, indem man sich pro Entity in ein Flag speichert, ob das Entity in diesem Aktualisierungszyklus bereits verändert wurde; sofern nicht, wird bei der (dann ersten) Änderung der Index des veränderten Entities in die Aktualisierungsliste aufgenommen. So hat man direkt eine Aktualisierungsliste ohne Duplikate.

Weiß jetzt nicht genau ob ich es richtig verstanden habe. Nutzt du diese Index Arrays um neue Arrays zu bilden oder benutzt du diese um in deinen Update schleifen über das Array zu wandern? Und wenn du das so machst, hast du viele Sprünge dazwischen? Verhinderst du die Sprünge dadurch das die Sichtbaren Objekte sowieso im Datenarray schon an ihrer Position in der Welt sortiert sind?

Gruß

Lutz

[Krishty]

Leicht off-topic, aber eine interessante Nebenwirkung datenorientierter Programmierung ist die bessere Programmierbarkeit. Schreibt man Datenblöcke statt Objekte in Dateien, haben Kompressionsprogramme weitaus weniger Mühe, optimale Algorithmen und Modelle zu finden. Darum speichert eure Texturen headerless; speichert Normal Maps mit anderer Dateiendung als Albedo Maps (hatte ich bei meiner Sternendemo gemacht; den Link zu den Ergebnissen finde ich gerade nicht mehr); speichert 16-Bit-Stereo-Sounds woanders als 8-Bit-Mono; speichert XYZ woanders als UV; und plötzlich ist euer Paket nur noch halb so groß.

[CodingCat]

Exception Safety im Rahmen eines datenorientierten Entwurfs bereitet mir ernsthafte Kopfschmerzen. Die Prinzipien "Where there's one, there's many" und "Keep it simple" scheinen sich hier nicht unerheblich zu widersprechen. Woimmer man mehr als ein Objekt verarbeitet, ist höchst unklar, wie bei Auftreten von Ausnahmen weiter verfahren werden soll. Ein transaktionales Fehlschlagen durch lückenloses Zurücksetzen auf den Urzustand kommt in den meisten Fällen nicht in Frage; Ein Abbruch wirft die Frage auf, wie denn nun mit den halbverarbeiteten Daten weiter zu verfahren ist; Ein einstweiliges Fortfahren mit anschließendem Wurf eines Fehlerrepräsentanten ist wohl die robusteste Lösung, jedoch hässlich umzusetzen und nicht weniger undurchsichtig.

[CodingCat]

Okay, dann hatte ich das so im Großen und Ganzen richtig verstanden. Wie machst du denn das, bei Objekten die z.B. deaktiviert oder nur sehr kurzlebig sind (z.B. Explosionen oder sowas). Behältst du da einfach die im Array drin, hast aber eine Art Flag die dir ansagt ob du den Eintrag aktualisieren musst oder nicht? Überlege gerade wie ich vernünftig von Sprüngen durch if Abfragen etc. weg komme. Eine simple Möglichkeit wäre z.B. eben diese Einträge drinnen zu lassen aber mit Werte zu versehen die nichts in der Logik ändern. Bei Transformationen ja recht einfach. Die dürfen eben nur keine Rolle später bei Kollision oder sonstigem Spielen. Was du ja wie beschrieben durch Index Arrays sowieso rausfilterst.

Für kurzlebige Objekte würde man sich wohl immer einen Pool anlegen, in dem alle relevanten Ressourcen vorallokiert bereit liegen. Sprünge brauchst du nicht grundsätzlich, du kannst bei Hinzufügen/Entfernen solcher kurzlebigen Objekte auch einfach Referenzen zwischen einer Free List und einer Active List hin und her schieben.

Nur aus Interesse halber, Sichtbarkeit ohne eine Art von Baum?

Wenn schon alles so Cache-freundlich im Speicher liegt, einfach einmal über alle Objekte drüberlaufen. ;-)

Also beim Thema "zugriff" fiel mir Spontan eben Hash Tabellen ein. Damit hättest du ein Handle die du auf den verschiedenen Gruppenobjekten benutzen kannst. -> Index to Index sollte ja recht schnell sein. Wie du geschrieben hattest gehts ja wirklich nur darum mal gelegentlich vielleicht ein Licht ein oder auszuschalten und sonstiges. Wobei bei so etwas sich sowieso ein eigenes Array eignen würde, da man dann bei Multithreading das ganze schon mal auf ein Array begrenzen würde.

Eine Hash-Tabelle muss auch aktuell gehalten werden, da erscheint mir der Direktzugriff via Handle-Zeiger noch wesentlich durchschaubarer und effizienter.

Weiß jetzt nicht genau ob ich es richtig verstanden habe. Nutzt du diese Index Arrays um neue Arrays zu bilden oder benutzt du diese um in deinen Update schleifen über das Array zu wandern? Und wenn du das so machst, hast du viele Sprünge dazwischen? Verhinderst du die Sprünge dadurch das die Sichtbaren Objekte sowieso im Datenarray schon an ihrer Position in der Welt sortiert sind?

Ich laufe über das Array von Indizes sichtbarer Objekte. Sprünge im Sinne von Verzweigung vermeide ich dadurch gerade. Sprünge im Speicher wird es natürlich zwangsläufig geben, Sortierung nach Position habe ich angedacht aber vorerst nicht für notwendig befunden. Eine Sortierung nach Morton Codes hätte den Vorteil, dass man implizit gleich einen Quad-Tree mit linearem Speicherlayout erhält, welcher ggf. zur Sichtbarkeitsbestimmung in großen Szenen genutzt werden könnte.

[Krishty]

Ich kann nicht recht folgen: Daten haben keinen Zustand, wo sollten also Fehler auftreten?

[CodingCat]

Daten sind in diesem Fall der Zustand. Sobald Daten mutierbar sind, müssen auch dort Invarianten aufrecht erhalten werden. Ich bewege mich hier zugegebenermaßen in Datenorientierung im weitesten Sinne, nämlich dem von Verarbeitung im Kollektiv bei dafür optimiertem Speicher-Layout. Damit rede ich in diesem Fall eigentlich von Gruppenobjektorientierung, mit dem vorläufigen Fazit, dass Fehlerbehandlung mittels Ausnahmen ihre Vorzüge vorwiegend bei Einzelobjektorientierung hat.

[Krishty]

Welche Invarianten denn? Für mich sieht nur die Mengeninvariante kritisch aus (also: Es muss immer genau so viele Handles / Transformationsmatrizen / Bounding Volumes zugleich geben wie Objekte). Und das wäre für mich schlicht erst allokieren (weil nur das schiefgehen kann und umkehrbar ist), dann kopieren.

[CodingCat]

Welche Invarianten denn? Für mich sieht nur die Mengeninvariante kritisch aus (also: Es muss immer genau so viele Handles / Transformationsmatrizen / Bounding Volumes zugleich geben wie Objekte). Und das wäre für mich schlicht erst allokieren (weil nur das schiefgehen kann und umkehrbar ist), dann kopieren.

Genau so gehe ich im Moment vor. Diese Invariante ist in der Tat einigermaßen unproblematisch, wenn die Umkehrung auch lästig ist. Schlimmer ist der Fall, Einheiten mitsamt Komponenten ("Controllern") atomar in die Welt einzufügen. Da hängt ein gewaltiger Batzen Zustand dran (ggf. Graphikressourcen erzeugen, Einfügeoperation an Physik-API weitergeben ...). Hier wird ein Fehler zum echten Problem, weil ich am Ende auf keinen Fall halb eingefügte Einheiten haben möchte. Das Entfernen von Einheiten/Komponenten sollte sich mit einer nothrow-Garantie versehen lassen, was bleibt, ist noch mehr ekelhafter Umkehrcode im Fehlerfall.

[CodingCat]

Kurzes Update: Ich habe nun meine Faulheit überwunden und doch starke Ausnahmesicherheit mit vollständiger Rücksetzung im Ausnahmefall gewählt. Das Problem an dieser Stelle ist auch nicht die Datenorientierung, sondern die komplexe Verwaltungslogik obendrauf, die beim Anhängen von Controllern an Entities anfällt. Die Datenorientierung macht das Rücksetzen nur wesentlich unangenehmer (Schleifen über zurückzusetzende Teile, Index-Intervalle korrigieren ...), weil an dieser Stelle Verwaltungslogik und Datenverwaltung unglücklicherweise Teil einer einzigen unhandlichen atomaren Transaktion sind. Schlussendlich ist diese Stelle einzigartig im gesamten Programm, insofern kann ich mir komplexe Fehlerbehandlung hier durchaus mal leisten.

[BeRsErKeR]

Irgendwie kann ich mir nicht so recht vorstellen, dass der datenorientierte Ansatz wirklich Vorteile bringt. Dieser ganze Verwaltungsaufwand ist doch viel zu aufwendig und fehleranfällig, als dass er den Nutzen aufwiegt. Und wenn die Daten ständig verschoben werden, kann das doch auch nicht wirklich performant sein.

[CodingCat]

Der Witz ist gerade, dass die Daten am Ende überhaupt nicht mehr verschoben werden; diese ganze Verwaltungslogik brauche ich nur für die Unterstützung von Content Creation Tools (-> Map Editor).

Ja, fehleranfälliger ist die Verwaltung in diesem Fall definitiv. Ich versuche das durch entsprechende Hilfs-Templates und -Funktionen so weit wie möglich zu minimieren, ganz gelingt das jedoch nicht. Dafür werden andere Dinge sehr viel einfacher, nämlich die Verarbeitung. Wo du sonst Einzelobjekte extra in Gruppen registrieren musst, hast du mit datenorientiertem Entwurf bereits alles verarbeitungsfertig und ohne Umwege zugänglich im Speicher liegen.

[joggel]

Was ich mir definitiv als Anwendungfall vorstellen könnte, wäre das parallele Verarbeiten von Daten...

Vondaher Danke von mir, dass Du deine Erfahrung hier teilst!

[Krishty]

Ich muss dazusagen: Ich habe das Glück, dass die meisten meiner Datenstrukturen nach dem Laden niemals wieder angefasst werden, d.h.: Beim Laden wird einmal allokiert und gefüllt, und wenn das nicht geht, fehlt das zu ladende Objekt eben. Da muss nichts wieder aufgerollt werden; dementsprechend geht bei mir der Verwaltungsaufwand gegen Null. Ich habe keine Manager und keine Indizes und keine Handles, sondern einfach Funktionen, die Iteratoren (lies Zeiger) auf Anfang und Ende der Daten zurückgeben, die ich brauche.

[BeRsErKeR]

Der Witz ist gerade, dass die Daten am Ende überhaupt nicht mehr verschoben werden; diese ganze Verwaltungslogik brauche ich nur für die Unterstützung von Content Creation Tools (-> Map Editor).

Ja, fehleranfälliger ist die Verwaltung in diesem Fall definitiv. Ich versuche das durch entsprechende Hilfs-Templates und -Funktionen so weit wie möglich zu minimieren, ganz gelingt das jedoch nicht. Dafür werden andere Dinge sehr viel einfacher, nämlich die Verarbeitung. Wo du sonst Einzelobjekte extra in Gruppen registrieren musst, hast du mit datenorientiertem Entwurf bereits alles verarbeitungsfertig und ohne Umwege zugänglich im Speicher liegen.

Könntest du bitte mal eine grobe Skizzierung eines Beispiels zeigen? Z.B. einen kleinen Ausschnitt aus deinem Map-Editor, wo du das zweckdienlich anwendest und vorallem in welcher Form. Die Details würden mich interessieren. Vielleicht verstehe ich dann auch besser, was du für konkrete Ziele mit diesem Ansatz verfolgst.

[CodingCat]

Könntest du bitte mal eine grobe Skizzierung eines Beispiels zeigen? Z.B. einen kleinen Ausschnitt aus deinem Map-Editor, wo du das zweckdienlich anwendest und vorallem in welcher Form. Die Details würden mich interessieren. Vielleicht verstehe ich dann auch besser, was du für konkrete Ziele mit diesem Ansatz verfolgst.

Ich werde eine auführliche Antwort auf diese Frage noch etwas rausschieben, aber schlussendlich geht es darum, wie Krishty sagt, im normalen Programmablauf (lies: nicht Design-Time) statische optimierte Datenstrukturen zu haben und dann mit einfachen Iterationen direkt durch diese Datenstrukturen zu laufen. Solche optimierten Datenstrukturen haben oft die unangenehme Eigenschaft, dass sie sehr schwer oder zumindest wesentlich schwerer zu aktualisieren/verändern sind. Das macht zur Design-Time bei Änderungen wie dem Entfernen von Objekten oder dem Verändern der Szenenstruktur die in diesem Thread skizzierten Verwaltungsmechanismen notwendig.

Prinzipiell gibt es hier einen alternativen Weg, nämlich die Design-Time-Logik einfach vollständig von der Runtime-Logik zu trennen. Mit getrennten Datenstrukturen, einer unoptimierten veränderlichen und einer optimierten unveränderlichen, kommt man mit weniger komplexer Verwaltungslogik aus. Dafür müssen zwei vollständig getrennte Code-Pfade synchron gehalten werden, was mir erheblich zu viel Aufwand ist. (IIrc ist ein prominentes Beispiel hierfür die Frostbite Engine von DICE (Battlefield), die für den Editor einen großen Teil der Engine nochmal editorgerecht in C# nachbildet.)

[CodingCat]

Noch ein Wort zu Besitzsemantik und Ausnahmesicherheit. Ich hatte mir zunächst vorgestellt (gewünscht), dass Ausnahmesicherheit und Besitz mit der datenorientierten Verwaltung von Objektgruppen eine wesentlich geringere Rolle spielen. Meine naive Vorstellung war hier, dass das Verwaltungsobjekt/die Objektgruppe automatisch auch der Besitzer ist, und somit weitere Gedanken zu dem Thema entfallen.

Tatsächlich gilt dies so uneingeschränkt aber nur für geteilte Ressourcen mit unbestimmter Lebensdauer, wo man in der Regel ohnehin in jedem Entwurf eine zentrale Verwaltungseinheit hat, die das redundande Laden von Ressourcen (Shaders, Meshes, Texturen) vermeidet, indem sie für alle bereits geladenen Ressourcen ein Register anlegt. Diese Ressourcen können zu einem bestimmten Zeitpunkt (Programmende?), nachdem alle referenzierenden Objekte sicher zerstört wurden, gefahrlos kollektiv entladen werden.

Betrachtet man hingegen andere Objekte, wie zum Beispiel Einheiten einer Szene, dann spielt dort Besitz (zur Design-Zeit?) nach wie vor eine Rolle. Besitz und Existenz haben dort nämlich nicht alleine mit Speicherverwaltung zu tun, es geht viel mehr um die logische Existenz von Einheiten. Nur weil irgendwo eine Ausnahme fliegt, kann ein Objekt nicht plötzlich für den Rest der Programmausführung besitzlos und unantastbar, aber für alle sichtbar, in der Szene verweilen. Die Anforderungen und Garantien für den Zustand "in der Szene"/ "nicht mehr in der Szene" sind unabhängig von der Art des Entwurfs und der Art der Verwaltung. Auch wenn die Objekte im datenorientierten Entwurf physikalisch einen eindeutigen Besitzer haben, ist der logische Besitz damit nicht automatisch geregelt.

Im Übrigen ist dies besonders interessant im Hinblick auf andere Programmiersprachen mit Garbage Collection, wo Besitz in der Regel nicht strikt geregelt ist bzw. ggf. überhaupt nicht so strikt geregelt werden kann.

So, wenn das nicht Meta-Talk ist. ;-)

[Krishty]

*seufz*
Ich habe hier zig Listen, die ich bloß einmal pro Frame aufbaue und dann wieder wegschmeiße. Warum unterstützt C++ bloß keine Variable-Length Arrays?

Ich will nicht allokieren! Nicht, weil es Zeit kostet (tut es kaum) oder die Gefahr von Speicher-Lecks birgt (die ich eh nie habe) – sondern, weil eine Allokation globale Wirkung hat und eine globale Lösung für ein vollständig lokales Problem wäre.

Das kotzt mich echt an und macht mir ehrlich gesagt eine Menge Spaß an der Datenorientierung wieder kaputt.

[CodingCat]

Bekommt man nicht irgendwie ein Makro hin für auto frameList = stack_new(Type, N) mit #define stack_new(t, n) stack_array<t>(_alloca(sizeof(t) * n), n) und stack_array-Wrapper (Ktor -> Placement New für alle Elemente, Dtor -> Destruktoraufruf für alle Elemente)? (Viel weniger Code würden dir variable-length arrays vermutlich auch nicht ausspucken.)

[Krishty]

Uff … da war doch was …

Ja; ich habe dieses Makro tatsächlich irgendwo in meinem Text gehabt, aber letztens wieder rausgeschmissen. Es ist und bleibt schlicht frustrierend, damit zu arbeiten; in Anbetracht der Umstellung auf Clang habe ich auch keinen Bock auf einen weiteren Hack, den ich portieren muss.

[Punika]

Hallo

wollte die Diskussion mal mit einem praktischen Beispiel auffüllen.
Es geht um ein Animationssystem in datenorientierter Form. Dabei würde ich gerne Diskutieren wo Nachteile und Vorteile sind, und Verbesserungen möglich sind.
Ich habe das Animationssystem jetzt auf der kleinsten Stufe gehalten und habe diese Datenpakete bekommen:




Wie man sieht, sind die Channels und die daraus resultierende Ergebnisse super dazu geeignet. Was wir also am liebsten machen würden, einfach über diese beiden Arrays laufen und rechnen. Doch das geht leider nicht perfekt.
Denn im Moment ist es so, das z.B. geladenen Modelle auch diese Channels besitzen (damit haben wir da schon mal doppelte Daten), darum habe ich mir gedacht, das die Channel Streams eben nach dem Prinzip aufgebaut werden, was im Moment "läuft". Ich habe das ganze zwar noch nicht mit vielen Animationen gleichzeitig laufen lassen, habe aber über die Datenmenge die hier kopiert werden müsste ein wenig sorge.
Zudem wäre es ja perfekt wenn wir für die gleiche Animation die kompletten Channels kopieren (keine Sprünge vorhanden). Das würde nur wieder viel Speicher und Bandbreite brauchen.
Deshalb habe ich hier noch die Playback Daten eingefügt, diese können Gruppen von Channels angeben. Somit brauche ich keine Channel Duplikate mehr, habe aber jetzt Sprünge drin. Die könnte ich noch vorsortieren, um die Sprünge zu verringern.

Ein anderer Weg wäre, das ich für jeden Channel eine Liste von "Outputs" mache, damit würde ich eben dann über alle Channels laufen können, wobei jeder Channel mehrere Outputs hätte.

Hier weiß ich nicht was besser ist. Kann da jemand mit Erfahrung was sagen? Denke mal das kommt stark auf die Größe des CPU Caches an. (Wieviele Channels kann er im Cache behalten wenn er zwischendurch immer die Outputs laden muss...)

Was mir sonst eben noch ein wenig sorgen bereitet ist die Verwaltung. Neue Playbacks hinzufügen, alte löschen oder neu einfügen (für loops), bin mir noch nicht ganz sicher ob ich da zuviel Zeit verliere. Zum anderen habe ich eben immer 2 Kopien. Eine für das geladene Modell (für den Zugriff wenn es animiert wird) und zum anderen im Animationssystem.

Und worüber ich auch noch gerne reden würde: Ab welcher Stufe hört man auf Datenpunkte zu schnürren. Was mir eben in den Sinn kam war in den Channels: POS,ROT,SCALE noch mal in lineare Arrays zu schreiben und die Channels zeigen nur auf den Bereich. Habe nur das gefühl das man damit ungewollt wieder viele Cache Misses produziert.

Grüße

Lutz