Was ist datenorientiertes Design?

156

Ich habe diesen Artikel gelesen und dieser Typ spricht weiter darüber, wie jeder davon profitieren kann, datenorientiertes Design mit OOP zu mischen. Er zeigt jedoch keine Codebeispiele.

Ich habe dies gegoogelt und konnte keine wirklichen Informationen darüber finden, geschweige denn Codebeispiele. Ist jemand mit diesem Begriff vertraut und kann ein Beispiel geben? Ist das vielleicht ein anderes Wort für etwas anderes?

data-oriented-design Ryeguy
quelle
7
Dieser Artikel in Game Developer ist jetzt in einfach zu lesender Blog-Form verfügbar
Edmundito
58
Habt ihr jemals etwas gegoogelt, eine nette gezielte SO-Frage gefunden und dann gemerkt, dass ihr es vor Jahren gefragt habt?
Ryeguy
1
Hier ist eine Zusammenfassung von DOD-Inhalten im Web
legends2k
14
@ryeguy, ich hatte eine Frage, habe sie gegoogelt, eine nette SO-Frage gefunden und dann festgestellt, dass ich sie vor Jahren beantwortet habe.
Michael Deardeuff
4
Ich habe etwas gegoogelt und eine nette SO-Frage gefunden und weißt du was? Ich habe weder gefragt noch geantwortet :)
Nadjib Mami

Antworten:

287

Verwechseln Sie dies zunächst nicht mit datengesteuertem Design.

Mein Verständnis von datenorientiertem Design ist, dass es darum geht, Ihre Daten für eine effiziente Verarbeitung zu organisieren. Insbesondere in Bezug auf Cache-Fehler usw. Bei Data Driven Design geht es dagegen darum, dass Daten einen Großteil Ihres Programmverhaltens steuern (sehr gut beschrieben durch Andrew Keiths Antwort ).

Angenommen, Ihre Anwendung enthält Kugelobjekte mit Eigenschaften wie Farbe, Radius, Sprungkraft, Position usw.

Objektorientierter Ansatz

In OOP würden Sie Bälle wie folgt beschreiben:

class Ball {
  Point  position;
  Color  color;
  double radius;

  void draw();
};

Und dann würden Sie eine Sammlung solcher Bälle erstellen:

vector<Ball> balls;

Datenorientierter Ansatz

In Data Oriented Design schreiben Sie den Code jedoch eher wie folgt:

class Balls {
  vector<Point>  position;
  vector<Color>  color;
  vector<double> radius;

  void draw();
};

Wie Sie sehen, gibt es keine Einheit mehr, die einen Ball darstellt. Ballobjekte existieren nur implizit.

Dies kann in Bezug auf die Leistung viele Vorteile haben. Normalerweise möchten wir viele Bälle gleichzeitig operieren. Hardware möchte normalerweise, dass große, kontinuierliche Speicherblöcke effizient arbeiten.

Zweitens können Sie Operationen ausführen, die nur einen Teil der Eigenschaften eines Balls betreffen. Wenn Sie beispielsweise die Farben aller Kugeln auf verschiedene Weise kombinieren, soll Ihr Cache nur Farbinformationen enthalten. Wenn jedoch alle Ball-Eigenschaften in einer Einheit gespeichert sind, ziehen Sie auch alle anderen Eigenschaften eines Balls ein. Auch wenn du sie nicht brauchst.

Cache-Verwendungsbeispiel

Angenommen, jeder Ball benötigt 64 Bytes und ein Punkt 4 Bytes. Ein Cache-Slot benötigt beispielsweise auch 64 Bytes. Wenn ich die Position von 10 Bällen aktualisieren möchte, muss ich 10 * 64 = 640 Bytes Speicher in den Cache ziehen und 10 Cache-Fehler erhalten. Wenn ich jedoch die Positionen der Kugeln als separate Einheiten bearbeiten kann, dauert dies nur 4 * 10 = 40 Bytes. Das passt in einen Cache-Abruf. Somit erhalten wir nur 1 Cache-Fehler, um alle 10 Bälle zu aktualisieren. Diese Zahlen sind willkürlich - ich gehe davon aus, dass ein Cache-Block größer ist.

Es zeigt jedoch, wie sich das Speicherlayout stark auf die Cache-Treffer und damit auf die Leistung auswirken kann. Dies wird nur an Bedeutung gewinnen, wenn sich der Unterschied zwischen CPU- und RAM-Geschwindigkeit vergrößert.

So gestalten Sie den Speicher

In meinem Ball-Beispiel habe ich das Problem stark vereinfacht, da Sie normalerweise für jede normale App wahrscheinlich gleichzeitig auf mehrere Variablen zugreifen. ZB werden Position und Radius wahrscheinlich häufig zusammen verwendet. Dann sollte Ihre Struktur sein:

class Body {
  Point  position;
  double radius;
};

class Balls {
  vector<Body>  bodies;
  vector<Color>  color;

  void draw();
};

Der Grund, warum Sie dies tun sollten, ist, dass, wenn Daten zusammen in separaten Arrays abgelegt werden, das Risiko besteht, dass sie um dieselben Slots im Cache konkurrieren. Wenn Sie also einen laden, wird der andere weggeworfen.

Im Vergleich zur objektorientierten Programmierung beziehen sich die Klassen, die Sie am Ende erstellen, nicht auf die Entitäten in Ihrem mentalen Modell des Problems. Da Daten basierend auf der Datennutzung zusammengefasst werden, haben Sie nicht immer sinnvolle Namen, um Ihren Klassen in datenorientiertem Design zu geben.

Beziehung zu relationalen Datenbanken

Das Denken hinter Data Oriented Design ist sehr ähnlich zu dem, was Sie über relationale Datenbanken denken. Das Optimieren einer relationalen Datenbank kann auch eine effizientere Verwendung des Caches beinhalten, obwohl in diesem Fall der Cache kein CPU-Cache, sondern Seiten im Speicher ist. Ein guter Datenbankdesigner wird wahrscheinlich auch Daten, auf die selten zugegriffen wird, in eine separate Tabelle aufteilen, anstatt eine Tabelle mit einer großen Anzahl von Spalten zu erstellen, wenn nur einige der Spalten jemals verwendet werden. Er kann sich auch dafür entscheiden, einige der Tabellen zu denormalisieren, damit nicht von mehreren Stellen auf der Festplatte auf Daten zugegriffen werden muss. Genau wie bei Data Oriented Design werden diese Entscheidungen getroffen, indem untersucht wird, wie die Datenzugriffsmuster aussehen und wo der Leistungsengpass liegt.

Erik Engheim
quelle
4
Danke dafür, du hast es sehr gut erklärt.
Ryeguy
4
gut gesagt; Ich habe jedoch nur eine Frage. Nehmen wir an, wir haben eine Struktur struct balls {vector<vec3> pos; vector<vec3> velocity;}, die nicht aktualisiert, dass die Position jedes Balls den Cache tatsächlich zerstört, da Sie sich zwischen dem Geschwindigkeitsvektor und dem Positionsvektor hin und her bewegen würden (ja, moderne Maschinen und Cache-Zeilen und all das, das ist auch nur eine Illustration)?
Falstro
14
Es könnte. Denken Sie jedoch daran, dass nicht das gesamte Pos-Array gleichzeitig eingezogen wird. Nur eine Cache-Zeile und möglicherweise ein Prefetching. Ebenso mit Geschwindigkeit. Damit sie sich gegenseitig in den Papierkorb werfen können, muss jeder entsprechende Teil von pos und Vektor derselben Cacheline zugeordnet werden. Das kann natürlich passieren, weshalb empfohlen wird, Variablen, die zusammen verwendet werden, in einer Struktur zusammenzufassen. So wären z. B. Geschwindigkeit und pos in einem Vektor, während Farbe in einem anderen Vektor wäre.
Erik Engheim
1
@roe Sie sollten Eigenschaften zusammenfassen, auf die zusammen zugegriffen wird. Zwischen den Eigenschaften sollten überhaupt keine Abhängigkeiten bestehen. Diese Struktur wäre also besser struct balls { vector<color> colors; vector<body> bodies; /* contains position and velocity */ }.
Danijar
2
@danijar Ich habe die Erklärung mit Ihren Vorschlägen aktualisiert. Ich hätte viel mehr darüber sagen können, aber das wird wirklich nur zu einem Artikel.
Erik Engheim
18

Mike Acton hielt kürzlich einen öffentlichen Vortrag über datenorientiertes Design :

Meine grundlegende Zusammenfassung wäre: Wenn Sie Leistung wünschen, dann denken Sie über den Datenfluss nach, finden Sie die Speicherschicht, die am wahrscheinlichsten mit Ihnen zusammenpasst, und optimieren Sie sie hart. Mike konzentriert sich auf L2-Cache-Fehler, weil er in Echtzeit arbeitet, aber ich stelle mir vor, dass dies auch für Datenbanken (Festplattenlesevorgänge) und sogar für das Web (HTTP-Anforderungen) gilt. Ich denke, es ist eine nützliche Methode zur Systemprogrammierung.

Beachten Sie, dass Sie nicht über Algorithmen und Zeitkomplexität nachdenken müssen, sondern sich nur darauf konzentrieren, den teuersten Operationstyp herauszufinden, auf den Sie dann mit Ihren verrückten CS-Fähigkeiten abzielen müssen.

Alexei Averchenko
quelle
14

Ich möchte nur darauf hinweisen, dass Noel speziell über einige der spezifischen Bedürfnisse spricht, denen wir bei der Spieleentwicklung gegenüberstehen. Ich nehme an, andere Sektoren, die eine weiche Echtzeitsimulation durchführen, würden davon profitieren, aber es ist unwahrscheinlich, dass es sich um eine Technik handelt, die eine spürbare Verbesserung der allgemeinen Geschäftsanwendungen zeigt. Diese Einrichtung soll sicherstellen, dass die zugrunde liegende Hardware bis zum letzten Stück Leistung herausgefordert wird.

Rechnung c
quelle
Einverstanden. Einige andere Bereiche, in denen datenorientiertes Design von Bedeutung ist, sind: Hardware und Firmware für Geräte mit hoher Bandbreite (z. B. Netzwerk oder Speicher); Wissenschaftliches Rechnen in großem Maßstab (z. B. Wettersimulation, Proteinfaltung), Signalverarbeitung (z. B. Audio, Bild, Video), Datenkomprimierung. Diese fallen unter die "Computational Science and Engineering", die manchmal als separates Hauptfach von der typischeren Informatik angeboten wird.
Rwong
-3

Ein datenorientiertes Design ist ein Design, bei dem die Logik der Anwendung aus Datensätzen anstelle von prozeduralen Algorithmen aufgebaut ist. Beispielsweise

prozeduraler Ansatz.

int animation; // this value is the animation index

if(animation == 0)
   PerformMoveForward();
else if(animation == 1)
  PerformMoveBack();
.... // etc

Datenentwurfsansatz

typedef struct
{
   int Index;
   void (*Perform)();
}AnimationIndice;

// build my animation dictionary
AnimationIndice AnimationIndices[] = 
  {
      { 0,PerformMoveForward }
      { 1,PerformMoveBack }
  }

// when its time to run, i use my dictionary to find my logic
int animation; // this value is the animation index
AnimationIndices[animation].Perform();

Datenentwürfe wie dieser fördern die Verwendung von Daten, um die Logik der Anwendung zu erstellen. Es ist einfacher zu verwalten, insbesondere in Videospielen, die möglicherweise Tausende von Logikpfaden haben, die auf Animationen oder einem anderen Faktor basieren.

Andrew Keith
quelle
14
Das ist eigentlich nicht richtig. Sie verwechseln datenorientiertes Design mit datengesteuertem Design. Ich tat das Gleiche, bis ich Noels Artikel las und feststellte, dass er über etwas ganz anderes sprach.
Erik Engheim
12
Auch ist Indice kein Wort. Es gibt "Index" und "Indizes" und einige dulden sogar "Indizes", aber "Index" ist niemals richtig.
Baxissimo