Datenorientiertes Design

Datenorientiertes Design (DOD) ist ein Ansatz zur Optimierung von Computerprogrammen, der die effiziente Nutzung des CPU-Caches anstrebt und beispielsweise bei der Entwicklung von Computerspielen und Webbrowsern Verwendung findet. Die Methode des datenorientierten Designs beinhaltet, das Speicherlayout aller Strukturen im Programm so zu planen, dass Daten, welche von einer Prozedur gebraucht werden, möglichst nahe beieinander im Speicher liegen (Speicherlokalität).

Verfechter dieses Paradigmas sind unter anderem Stoyan Nikolov, Mike Acton und Scott Meyers.

Motivation

DOD wurde Mitte bis Ende der 2010er Jahre, während der 7. Generation von Spielkonsolen, Xbox 360, PlayStation 3 und Wii, populär. Historisch gesehen haben Spielkonsolen oft relativ schwache CPUs, wenn sie mit den zeitgenössischen Desktop-Computern verglichen werden, dafür jedoch stärkere Grafikprozessoren (GPUs). Um trotzdem möglichst viel aus den CPUs herauszuholen, muss der sogenannte Von-Neumann’sche Flaschenhals umgangen werden. Mit dem Von Neumann’sche Flaschenhals ist die Problematik gemeint, dass moderne CPUs wesentlich schneller Daten verarbeiten als die vergleichsweise langsamen Hauptspeicher laden können. Dieses Problem versucht man unter anderem mit Technologien wie schnellen Cache-Speichern, die direkt in die CPU integriert sind, zu lösen. Allerdings kommt es häufig vor, dass Daten, die die CPU anfordert, nicht im Cache geladen sind und somit eine Anfrage an den Hauptspeicher erfolgen muss. Dies wird als cache-miss bezeichnet. Um diese zu minimieren, sollten Daten, die von der CPU gleichzeitig oder zeitlich nahe beieinander verwendet werden, im Speicher nahe bei einander liegen (Speicherlokalität), um so Speicherzugriffsmuster zu verbessern und den Effekt des Flaschenhalses zu minimieren.

Gegensatz zur Objektorientierung

Die Prinzipien der objektorientierten Programmierung können in schlechter Datenlokalität münden, heterogene, verstreute Daten werden in Objekten zusammengefasst. Insbesondere kann die Nutzung von Polymorphie dazu beitragen, dass Objekte mit heterogenen, verstreute Daten in stark unterschiedlichen Kontexten verarbeitet werden. In der Programmiersprache C++ ist dieses Konzept bspw. mittels vTables implementiert, was dazu führt, dass zur Ausführung einer virtuellen Methode ein Pointer auf eine Speicheradresse aufgelöst werden muss. Wenn virtuelle Methoden vieler einzelner Objekte aufgerufen werden müssen, werden viele Pointer mehrfach aufgelöst, was die Caches füllt und die Laufzeit negativ beeinträchtigt.

Bei Nutzung des Datenorientierten Designs (DOD) wird die Nutzung virtueller Methoden vermieden. Stattdessen werden Daten im Verbund organisiert und eine externe Funktion, Methode oder Subroutine wird genutzt, um die gewünschte Operation auf alle Objekte hintereinander weg anzuwenden, womit das mehrfache Auflösen von Pointern umgangen wird. Kurzgefasst wird versucht, Daten, die häufig gemeinsamen gebraucht werden, so auf Verbunddatentypen und Arrays zu verteilen, dass sie im Speicher nahe beieinander liegen (Speicherlokalität), um effizientere Verarbeitung zu ermöglichen.

Siehe auch

• CPU-Cache
• Objektorientierte Programmierung

Literatur

• Noel Llopis: High‐Performance Programming with Data‐Oriented Design in: Eric Lengyel: Game Engine Gems 2, CRC Press, 2011, S. 251 ff. [3]

Weblinks

• Memory access pattern
• Unity-DOTS