Datenorientiertes Design - unpraktisch bei mehr als 1-2 Strukturmitgliedern?

23

Das übliche Beispiel für datenorientiertes Design ist die Kugelstruktur:

struct Ball
{
  float Radius;
  float XYZ[3];
};

und dann machen sie einen Algorithmus, der einen std::vector<Ball>Vektor iteriert .

Dann geben sie Ihnen das Gleiche, aber implementiert in Data Oriented Design:

struct Balls
{
  std::vector<float> Radiuses;
  std::vector<XYZ[3]> XYZs;
};

Was gut ist und alles, wenn Sie zuerst alle Radien durchlaufen, dann alle Positionen und so weiter. Wie bewegen Sie jedoch die Kugeln im Vektor? Wenn Sie in der Originalversion eine haben std::vector<Ball> BallsAll, können Sie einfach eine BallsAll[x]nach der anderen verschieben BallsAll[y].

Um dies jedoch für die datenorientierte Version zu tun, müssen Sie für jede Eigenschaft dasselbe tun (zweimal im Fall von Kugelradius und Position). Aber es wird schlimmer, wenn Sie viel mehr Eigenschaften haben. Sie müssen einen Index für jeden "Ball" führen und wenn Sie versuchen, ihn zu bewegen, müssen Sie den Zug in jedem Vektor von Eigenschaften ausführen.

Beeinträchtigt dies nicht die Leistung von Data Oriented Design?

ulak klinge
quelle

Antworten:

23

Eine andere Antwort gab einen hervorragenden Überblick darüber, wie Sie den zeilenorientierten Speicher schön einkapseln und eine bessere Übersicht geben würden. Da Sie aber auch nach der Leistung fragen, lassen Sie mich Folgendes ansprechen: Ein SoA-Layout ist keine Wunderwaffe . Es ist ein ziemlich guter Standard (für die Cache-Nutzung; weniger für die einfache Implementierung in den meisten Sprachen), aber es ist nicht alles vorhanden, auch nicht bei datenorientiertem Design (was auch immer das genau bedeutet). Es ist möglich, dass die Autoren einiger von Ihnen gelesener Einführungen diesen Punkt verpasst haben und nur das SoA-Layout präsentieren, weil sie denken, dass dies der gesamte Punkt von DOD ist. Sie würden sich irren und zum Glück fallen nicht alle in diese Falle .

Wie Sie wahrscheinlich bereits bemerkt haben, profitieren nicht alle primitiven Daten davon, in ein eigenes Array gezogen zu werden. Ein SoA-Layout ist von Vorteil, wenn auf die Komponenten, die Sie in separate Arrays aufteilen, normalerweise separat zugegriffen wird. Auf nicht jedes winzige Teil wird isoliert zugegriffen, z. B. wird fast immer ein Positionsvektor ausgelesen und aktualisiert, sodass Sie diesen natürlich nicht aufteilen. Tatsächlich hat Ihr Beispiel das auch nicht getan! Wenn Sie normalerweise gemeinsam auf alle Eigenschaften eines Balls zugreifen , da Sie die meiste Zeit damit verbringen, Bälle in Ihrer Ballsammlung zu tauschen, ist es sinnlos, sie zu trennen.

DOD hat jedoch eine zweite Seite. Sie können nicht alle Vorteile des Caches und der Organisation nutzen, indem Sie Ihr Speicherlayout um 90 ° drehen und das Wenigste tun, um die daraus resultierenden Kompilierungsfehler zu beheben. Unter diesem Banner werden noch andere Tricks gelehrt. Zum Beispiel "existenzbasierte Verarbeitung": Wenn Sie Bälle häufig deaktivieren und erneut reaktivieren, fügen Sie dem Ballobjekt kein Flag hinzu, und lassen Sie die Aktualisierungsschleife Bälle mit dem Flag "false" ignorieren. Verschieben Sie den Ball von einer "aktiven" Sammlung in eine "inaktive" Sammlung, und überprüfen Sie in der Aktualisierungsschleife nur die "aktive" Sammlung.

Wichtiger und relevanter für Ihr Beispiel: Wenn Sie so viel Zeit damit verbringen, das Balls-Array zu mischen, tun Sie möglicherweise etwas Falsches. Warum ist die Bestellung wichtig? Kannst du es egal machen? Wenn ja, würden Sie mehrere Vorteile erhalten:

  • Sie müssen die Sammlung nicht mischen (der schnellste Code ist überhaupt kein Code).
  • Sie können einfacher und effizienter hinzufügen und löschen (zum Beenden tauschen, zuletzt löschen).
  • Der verbleibende Code kann für weitere Optimierungen in Frage kommen (z. B. die Layoutänderung, auf die Sie sich konzentrieren).

Denken Sie also über Ihre Daten nach und wie Sie sie verarbeiten, anstatt SoA blind auf alles zu werfen . Wenn Sie feststellen, dass Sie die Positionen und Geschwindigkeiten in einer Schleife verarbeiten, dann gehen Sie die Maschen durch und aktualisieren Sie dann die Hitpoints. Versuchen Sie, Ihr Speicherlayout in diese drei Teile aufzuteilen. Wenn Sie feststellen, dass Sie isoliert auf die x-, y- und z-Komponenten der Position zugreifen, können Sie Ihre Positionsvektoren in eine SoA umwandeln. Wenn Sie feststellen, dass Sie mehr Daten mischen als tatsächlich etwas Nützliches tun, hören Sie vielleicht auf, sie zu mischen.

Gemeinschaft
quelle
18

Datenorientierte Denkweise

Datenorientiertes Design bedeutet nicht, SoAs überall anzuwenden. Es bedeutet einfach, Architekturen mit einem Schwerpunkt auf Datendarstellung zu entwerfen - insbesondere mit einem Schwerpunkt auf effizientem Speicherlayout und Speicherzugriff.

Das könnte möglicherweise zu SoA-Wiederholungen führen, wenn dies angemessen ist:

struct BallSoa
{
   vector<float> x;        // size n
   vector<float> y;        // size n
   vector<float> z;        // size n
   vector<float> r;        // size n
};

... dies ist häufig für die vertikale Schleifenlogik geeignet, bei der die Vektorkomponenten und der Radius eines Kugelzentrums nicht gleichzeitig verarbeitet werden (die vier Felder sind nicht gleichzeitig scharf), sondern einzeln (eine Schleife durch den Radius, weitere 3 Schleifen) durch einzelne Komponenten von Kugelzentren).

In anderen Fällen ist es möglicherweise sinnvoller, einen AoS zu verwenden, wenn auf die Felder häufig gemeinsam zugegriffen wird (wenn Ihre Loop-Logik alle Felder von Bällen durchläuft und nicht einzeln) und / oder wenn ein wahlfreier Zugriff auf einen Ball erforderlich ist:

struct BallAoS
{
    float x;
    float y;
    float z;
    float r;
};
vector<BallAoS> balls;        // size n

... in anderen Fällen kann es sinnvoll sein, einen Hybrid zu verwenden, der beide Vorteile in Einklang bringt:

struct BallAoSoA
{
    float x[8];
    float y[8];
    float z[8];
    float r[8];
};
vector<BallAoSoA> balls;      // size n/8

... Sie können sogar die Größe eines Balls mit Hilfe von Half-Floats auf die Hälfte komprimieren, um mehr Ballfelder in eine Cache-Zeile / Seite einzufügen.

struct BallAoSoA16
{
    Float16 x2[16];
    Float16 y2[16];
    Float16 z2[16];
    Float16 r2[16];
};
vector<BallAoSoA16> balls;    // size n/16

... vielleicht wird sogar der Radius nicht annähernd so oft abgerufen wie das Kugelzentrum (vielleicht behandelt Ihre Codebasis sie oft als Punkte und nur selten als Kugeln, z. B.). In diesem Fall wenden Sie möglicherweise eine Heiß- / Kaltfeld-Aufteilungstechnik an.

struct BallAoSoA16Hot
{
    Float16 x2[16];
    Float16 y2[16];
    Float16 z2[16];
};
vector<BallAoSoA16Hot> balls;     // size n/16: hot fields
vector<Float16> ball_radiuses;    // size n: cold fields

Der Schlüssel zu einem datenorientierten Entwurf besteht darin, alle diese Arten von Darstellungen zu berücksichtigen, bevor Sie Ihre Entwurfsentscheidungen treffen, und sich nicht in eine suboptimale Darstellung mit einer dahinter liegenden öffentlichen Schnittstelle zu verstricken.

Die Speicherzugriffsmuster und die zugehörigen Layouts werden hervorgehoben, wodurch sie ein wesentlich größeres Problem darstellen als gewöhnlich. In gewissem Sinne kann es sogar Abstraktionen etwas abreißen. Ich habe durch die Anwendung dieser Denkweise mehr herausgefunden, dass ich std::dequez. B. hinsichtlich der algorithmischen Anforderungen nicht mehr so ​​viel betrachte wie die aggregierte zusammenhängende Blockdarstellung und wie der zufällige Zugriff darauf auf Speicherebene funktioniert. Es konzentriert sich ein wenig auf Implementierungsdetails, aber Implementierungsdetails wirken sich in der Regel genauso oder mehr auf die Leistung aus als die algorithmische Komplexität, die die Skalierbarkeit beschreibt.

Vorzeitige Optimierung

Ein Großteil des vorherrschenden Fokus des datenorientierten Designs wird zumindest auf den ersten Blick als gefährlich nahe an einer vorzeitigen Optimierung erscheinen. Die Erfahrung lehrt uns oft, dass solche Mikrooptimierungen am besten im Nachhinein und mit einem Profiler in der Hand angewendet werden.

Eine wichtige Botschaft des datenorientierten Designs ist es jedoch, Raum für solche Optimierungen zu lassen. Dies kann eine datenorientierte Denkweise ermöglichen:

Datenorientiertes Design kann Raum zum Atmen lassen, um effektivere Darstellungen zu erkunden. Es geht nicht unbedingt darum, das Speicherlayout auf einmal zu perfektionieren, sondern vielmehr darum, die entsprechenden Überlegungen im Voraus zu treffen, um immer optimalere Darstellungen zu ermöglichen.

Granulares objektorientiertes Design

Viele datenorientierte Designdiskussionen werden sich mit klassischen Vorstellungen von objektorientierter Programmierung messen. Dennoch würde ich eine Sichtweise anbieten, die nicht ganz so hart ist, wie OOP vollständig zu entlassen.

Die Schwierigkeit bei objektorientiertem Design besteht darin, dass wir häufig versucht sind, Schnittstellen auf einer sehr detaillierten Ebene zu modellieren, sodass wir uns auf eine skalare, einzelne Denkweise anstatt auf eine parallele Massen-Denkweise beschränken.

Stellen Sie sich als übertriebenes Beispiel eine objektorientierte Design-Denkweise vor, die auf ein einzelnes Pixel eines Bildes angewendet wird.

class Pixel
{
public:
    // Pixel operations to blend, multiply, add, blur, etc.

private:
    Image* image;          // back pointer to access adjacent pixels
    unsigned char rgba[4];
};

Hoffentlich macht das eigentlich niemand. Um das Beispiel wirklich grob zu machen, habe ich einen Rückwärtszeiger auf das Bild gespeichert, das das Pixel enthält, damit es auf benachbarte Pixel für Bildverarbeitungsalgorithmen wie Unschärfe zugreifen kann.

Der Bild-Zurück-Zeiger fügt sofort einen grellen Overhead hinzu, aber selbst wenn wir ihn ausgeschlossen haben (indem nur die öffentliche Schnittstelle von Pixeln Operationen bereitstellt, die für ein einzelnes Pixel gelten), erhalten wir eine Klasse, die nur ein Pixel darstellt.

An einer Klasse im unmittelbaren Overhead-Sinne in einem C ++ - Kontext ist jetzt nichts mehr auszusetzen außer diesem Rückzeiger. Die Optimierung von C ++ - Compilern ist großartig, wenn es darum geht, alle von uns erstellten Strukturen auf die kleinsten zu reduzieren.

Die Schwierigkeit dabei ist, dass wir eine gekapselte Schnittstelle mit einer zu genauen Pixelebene modellieren. Daher sind wir in dieser Art von granularem Design und Daten gefangen, die möglicherweise von einer Vielzahl von Client-Abhängigkeiten mit dieser PixelSchnittstelle verknüpft werden.

Lösung: Beseitigen Sie die objektorientierte Struktur eines granularen Pixels und beginnen Sie mit der Modellierung Ihrer Schnittstellen auf einer gröberen Ebene, die mit einer großen Anzahl von Pixeln (auf Bildebene) zu tun hat.

Durch die Modellierung auf Bulk-Image-Ebene haben wir erheblich mehr Optimierungsspielraum. Wir können zum Beispiel große Bilder als zusammengefügte Kacheln mit 16 x 16 Pixeln darstellen, die perfekt in eine 64-Byte-Cache-Zeile passen, aber einen effizienten vertikalen Nachbarzugriff auf Pixel mit einem typisch kleinen Schritt ermöglichen (wenn wir über eine Reihe von Bildverarbeitungsalgorithmen verfügen, die müssen vertikal auf benachbarte Pixel zugreifen) als datenorientiertes Hardcore-Beispiel.

Entwerfen auf einer gröberen Ebene

Das obige Beispiel für die Modellierung von Schnittstellen auf Bildebene ist ein einfaches Beispiel, da die Bildverarbeitung ein sehr ausgereiftes Gebiet ist, das bis zum Tod untersucht und optimiert wurde. Weniger offensichtlich könnte jedoch ein Partikel in einem Partikelemitter sein, ein Sprite gegen eine Sammlung von Sprites, eine Kante in einem Kantendiagramm oder sogar eine Person gegen eine Sammlung von Personen.

Der Schlüssel zum Ermöglichen datenorientierter Optimierungen (im Voraus oder im Nachhinein) besteht häufig darin, Schnittstellen in großen Mengen auf einer viel gröberen Ebene zu entwerfen. Die Idee, Schnittstellen für einzelne Entitäten zu entwerfen, wird durch die Idee ersetzt, Entitätensammlungen mit großen Operationen zu entwerfen, die sie in großen Mengen verarbeiten. Dies betrifft insbesondere und unmittelbar sequentielle Zugriffsschleifen, die auf alles zugreifen müssen und eine lineare Komplexität aufweisen müssen.

Datenorientiertes Design beginnt oft mit der Idee, Daten zu aggregierten Modellierungsdaten in großen Mengen zusammenzuführen. Eine ähnliche Denkweise spiegelt sich in den dazugehörigen Schnittstellendesigns wider.

Dies ist die wertvollste Lektion, die ich aus datenorientiertem Design gezogen habe, da ich nicht über ausreichende Kenntnisse der Computerarchitektur verfüge, um bei meinem ersten Versuch häufig das optimale Speicherlayout für etwas zu finden. Es wird zu etwas, zu dem ich mit einem Profiler in der Hand iteriere (und manchmal mit einigen Fehlern auf dem Weg, auf dem ich es nicht geschafft habe, die Dinge zu beschleunigen). Der Aspekt des Schnittstellendesigns bei datenorientiertem Design lässt mir jedoch Raum, nach immer effizienteren Datendarstellungen zu suchen.

Der Schlüssel liegt darin, Schnittstellen auf einer gröberen Ebene zu entwerfen, als wir normalerweise versucht sind. Dies hat häufig auch Nebeneffekte wie die Verringerung des mit virtuellen Funktionen, Funktionszeigeraufrufen, Dylib-Aufrufen und der Unfähigkeit, Inline-Funktionen zu verwenden, verbundenen dynamischen Dispatch-Overheads. Die Hauptidee, um all dies herauszunehmen, besteht darin, die Verarbeitung (falls zutreffend) in großen Mengen zu betrachten.

Thomas Owens
quelle
5

Was Sie beschrieben haben, ist ein Implementierungsproblem. OO-Design befasst sich ausdrücklich nicht mit Implementierungen.

Sie können Ihren spaltenorientierten Ball-Container hinter einer Schnittstelle einkapseln, die eine zeilen- oder spaltenorientierte Ansicht verfügbar macht. Sie können ein Ball-Objekt mit Methoden wie volumeund implementieren move, die lediglich die entsprechenden Werte in der zugrunde liegenden spaltenweisen Struktur ändern. Gleichzeitig könnte Ihr Ballcontainer eine Schnittstelle für einen effizienten spaltenweisen Betrieb darstellen. Mit geeigneten Vorlagen / Typen und einem cleveren Inlining-Compiler können Sie diese Abstraktionen ohne Laufzeitkosten verwenden.

Wie oft greifen Sie spaltenweise auf Daten zu, anstatt sie zeilenweise zu ändern? In typischen Anwendungsfällen für die Spaltenspeicherung hat die Reihenfolge der Zeilen keine Auswirkungen. Sie können eine beliebige Permutation der Zeilen definieren, indem Sie eine separate Indexspalte hinzufügen. Zum Ändern der Reihenfolge müssen nur die Werte in der Indexspalte ausgetauscht werden.

Effizientes Hinzufügen / Entfernen von Elementen könnte mit anderen Techniken erreicht werden:

  • Behalten Sie eine Bitmap mit gelöschten Zeilen bei, anstatt Elemente zu verschieben. Verdichten Sie die Struktur, wenn sie zu dünn wird.
  • Gruppieren Sie Zeilen in einer B-Tree-ähnlichen Struktur in entsprechend großen Blöcken, sodass beim Einfügen oder Entfernen an beliebigen Positionen nicht die gesamte Struktur geändert werden muss.

Der Client-Code sieht eine Folge von Ball-Objekten, einen veränderlichen Container mit Ball-Objekten, eine Folge von Radien, eine Nx3-Matrix usw .; es muss sich nicht um die hässlichen Details dieser komplexen (aber effizienten) Strukturen kümmern. Das ist es, was die Objektabstraktion für Sie bedeutet.

user2313838
quelle
+1 AoS Organisation ist perfekt anpassbar an eine nette Entity-orientierte API, obwohl es zugegebenermaßen hässlicher wird (im ball->do_something();Vergleich zu ball_table.do_something(ball)), es sei denn, Sie möchten eine kohärente Entität über einen Pseudo-Zeiger vortäuschen (&ball_table, index).
1
Ich gehe noch einen Schritt weiter: Die Schlussfolgerung zur Verwendung von SoA lässt sich nur aus den OO-Designprinzipien ziehen. Der Trick ist, dass Sie ein Szenario benötigen, in dem die Spalten ein grundlegenderes Objekt sind als die Zeilen. Bälle sind hier kein gutes Beispiel. Betrachten Sie stattdessen ein Gelände mit verschiedenen Eigenschaften wie Höhe, Bodentyp oder Niederschlag. Jede Eigenschaft wird als ScalarField-Objekt modelliert, das über eigene Methoden wie gradient () oder divergence () verfügt, die möglicherweise andere Field-Objekte zurückgeben. Sie können Dinge wie die Kartenauflösung einkapseln, und verschiedene Eigenschaften im Gelände können mit verschiedenen Auflösungen arbeiten.
16807
4

Kurze Antwort: Sie haben völlig Recht, und Artikel wie dieser verfehlen diesen Punkt völlig.

Die vollständige Antwort lautet: Der Ansatz "Struktur von Arrays" in Ihren Beispielen kann Leistungsvorteile für bestimmte Arten von Operationen ("Spaltenoperationen") und "Arrays von Structs" für andere Arten von Operationen ("Zeilenoperationen") bieten ", wie die oben erwähnten). Das gleiche Prinzip hat Datenbankarchitekturen beeinflusst, es gibt spaltenorientierte Datenbanken im Vergleich zu den klassischen zeilenorientierten Datenbanken

Das zweite, was Sie bei der Auswahl eines Designs berücksichtigen müssen, ist, welche Art von Operationen Sie in Ihrem Programm am meisten benötigen und ob diese von dem unterschiedlichen Speicherlayout profitieren. Das erste, was Sie jedoch berücksichtigen sollten, ist, ob Sie diese Leistung wirklich benötigen (ich denke, in der Spieleprogrammierung, in der der obige Artikel von Ihnen stammt, besteht diese Anforderung häufig).

Die meisten aktuellen OO-Sprachen verwenden ein Speicherlayout "Array-Of-Struct" für Objekte und Klassen. Das Erreichen der Vorteile von OO (wie das Erstellen von Abstraktionen für Ihre Daten, die Kapselung und der lokalere Umfang der Grundfunktionen) ist in der Regel mit dieser Art von Speicherlayout verbunden. Solange Sie kein Hochleistungs-Computing betreiben, würde ich SoA nicht als primären Ansatz betrachten.

Doc Brown
quelle
3
DOD bedeutet nicht immer SoA-Layout (Structure-of-Array). Es ist üblich, weil es oft mit dem Zugriffsmuster übereinstimmt, aber wenn ein anderes Layout besser funktioniert, sollten Sie es unbedingt verwenden. DOD ist viel allgemeiner (und unübersichtlicher) und eher ein Entwurfsparadigma als eine bestimmte Art, Daten darzustellen. Auch während der Artikel , den Sie verweisen weit von der besten Ressource ist und hat seine Fehler, ist es nicht SoA Layouts werben. Die "A" und "B" können Ballebenso wie einzelne " floats" oder " vec3s" (die selbst einer SoA-Transformation unterliegen würden) voll funktionsfähig sein .
2
... und das von Ihnen erwähnte zeilenorientierte Design ist immer in DOD enthalten. Es wird als Array of Structures (AoS) bezeichnet, und der Unterschied zu dem, was die meisten Ressourcen als "OOP-Methode" (besser oder schlechter) bezeichnen, besteht nicht im Zeilen- oder Spaltenlayout, sondern lediglich darin, wie dieses Layout dem Speicher zugeordnet wird (viele kleine Objekte) verknüpft über Zeiger gegen eine große fortlaufende Tabelle aller Datensätze). Zusammenfassend lässt sich sagen, dass Sie, obwohl Sie gute Argumente gegen die Missverständnisse von OP vorbringen, den gesamten DOD-Jazz falsch darstellen, anstatt OPs Verständnis von DOD zu korrigieren.
@delnan: danke für deinen kommentar, du hast wahrscheinlich recht, dass ich den begriff "soa" anstelle von "dod" hätte verwenden sollen. Ich habe meine Antwort entsprechend bearbeitet.
Doc Brown
Viel besser, Abstimmungen entfernt. Schauen Sie sich die Antwort von user2313838 an, wie SoA mit netten objektorientierten APIs (im Sinne von Abstraktionen, Kapselung und "lokalerem Umfang der Grundfunktionen") vereinheitlicht werden kann. Für das AoS-Layout ist dies natürlicher (da das Array ein dummer generischer Container sein kann, anstatt mit dem Elementtyp verheiratet zu sein), aber es ist machbar.
Und dieses github.com/BSVino/JaiPrimer/blob/master/JaiPrimer.md, das automatisch von SoA nach / von AoS konvertiert wird . ycombinator.com/item?id=10235766
Jerry Jeremiah