Data-oriented design

from Wikipedia, the free encyclopedia

Data-oriented design (DOD) is an approach to optimizing programs that strives for efficient use of the CPU cache and is used, for example, in the development of video games and Internet browsers. The method of data-oriented design involves planning the memory layout of all structures in the program in such a way that the data required by a procedure are as close as possible to each other in the memory (memory location).

Proponents of this paradigm include Stoyan Nikolov, Mike Acton and Scott Meyers .

motivation

DOD became popular in the mid to late 2010s during the 7th generation of game consoles , Xbox 360 , PlayStation 3, and Wii . Historically, game consoles often have relatively weak CPUs when compared to contemporary desktop computers , but they have more powerful graphics processors (GPUs). In order to get as much out of the CPU as possible, the so-called Von Neumann bottleneck has to be avoided. Von Neumann's bottleneck refers to the problem that modern CPUs process data much faster than the comparatively slow main memory can load. Attempts are made to solve this problem with technologies such as fast cache memories that are directly integrated into the CPU. However, it often happens that data requested by the CPU are not loaded in the cache and therefore a request has to be made to the main memory. This is known as a cache miss . In order to minimize this, data that are used by the CPU at the same time or in close proximity to one another in time should be close to one another in the memory (memory locality) in order to improve memory access patterns and minimize the bottleneck effect.

Contrast to object orientation

The principles of object-oriented programming can result in poor data locality. In particular, the use of polymorphism can help. In the C ++ programming language , this concept is implemented using vTables , for example , which means that a pointer has to be resolved in order to execute a virtual method .

If virtual methods of many individual objects have to be called, this can definitely affect the runtime. In DOD, however, the use of virtual methods is avoided. Instead, the data of the objects are organized in compound data types and an external function / method is used to apply the desired operation to all objects, which are ideally located within an array, one after the other, which is intended to avoid multiple resolving of pointers. In short, the attempt is made to distribute data that are often used together on composite data types and arrays in such a way that they are close to one another in the memory (memory location) in order to enable more efficient access.

literature

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

See also

Individual evidence

  1. ↑ Data-Oriented Design (Or Why You Might Be Shooting Yourself in The Foot With OOP) . Noel Llopis. 4th December 2009.
  2. ↑ Robert Nystrom: Design Patterns for Game Programming, MITP-Verlag , 2015, p. 526 [1]
  3. ↑ a b CppCon 2018: Stoyan Nikolov “OOP Is Dead, Long Live Data-oriented Design” . CppCon.
  4. ↑ CppCon 2014: Mike Acton "Data-Oriented Design and C ++" . CppCon.
  5. ↑ code :: dive conference 2014 - Scott Meyers: Cpu Caches and Why You Care . NOKIA Technology Center Wrocław.
  6. ^ Richard Fabian: What's wrong with OOP? In: http://www.dataorienteddesign.com . Data Orientated Design, June 25, 2013, accessed July 8, 2020 .
  7. ↑ Norman F. Schneidewind: Computer, Network, Software, and Hardware Engineering with Applications, John Wiley & Sons, 2012, p. 266 [2]