Data-oriented design

Cache is life

DOD is a programing style that focus on the fact that the code in the end will run on some real hardware. While other paradigms try create a easy mental model for the programmer DOD aim to make it easy for the hardware to read and write the data. The problem that normally exist are as follows.

  • The CPU needs to wait for memory access if things are not in the memory cache. The faster a CPU get relative to the memory the more CPU cycles is wasted on waiting. That can apply to both waiting for code instructions to be loaded or data to be loaded.

  • When multi threading the CPU needs to wait for other resources to get unlocked so it can use them.

The goal is to get the maximum amount of flow of data without any stalls waiting for anything. This is done as follows.

  • Focus on data. How is it read, transformed and written.

  • Usage pattern

    • Activity - How often field is accessed. Often is hot and less often is cold.

    • Correlation - How often fields are used together.

  • Split data into hot and cold. A struct with the hot data that have a pointer to the cold data. All the hot data can then be one array and the cold another. If pure arrays and index are used on both one can skip the pointers.

  • Improve locality by keeping data that is accessed together close to each other.

  • Watch compiler padding so data structures do not bloat with padding.

  • Linear data is best.

  • The source data and the native data does not need to be the same.

  • Linearize data at runtime.

Reference

Data oriented design in practice - Stoyan Nikolov - Meeting C++ 2018

OOP Is Dead, Long Live Data-oriented Design - 2018

The Story behind The Truth: Designing a Data Model - 2017

Explaining Data Oriented Design - 2015

Allocation Adventures 1: The DataComponent - 2015

Data-Oriented Hash Table - 2015

Data oriented design and c++ - 2014. Slides.

What is Data-Oriented Game Engine Design? - 2014

Mike Acton "Data-Oriented Design and C++ - 2014

Data Oriented Design : Starting Up - 2013

Adventures in data-oriented design - 2013

Part 4: Skinning it to 11

Part 3c: External References

Part 3b: Internal References

Part 3a: Ownership

Part 2: Hierarchical data

Part 1: Mesh data

Behind the Mirror - Adding Reflection to C++ - 2011

Culling the Battlefield Data Oriented Design in Practice - 2011

Data-Oriented Design Now And In The Future - 2011

Data-Oriented Design Now And In The Future - 2011

Data Oriented Design – The Numbers - 2010

Introduction to Data Oriented Design - 2010

Data oriented design links - 2010

Musings on Data-Oriented Design - 2010

Is Data-Oriented Design a Paradigm? - 2010

Data Oriented Luddites - 2010

A Step Towards Data Orientation - 2010

Is Data-Oriented Design a Paradigm? - 2010

Musings on Data-Oriented Design - 2010

Be nice to your cache - 2010

The Latency Elephant - 2009

Great Presentation on Data-Oriented Design - 2009

Data-Oriented Design (Or Why You Might Be Shooting Yourself in The Foot With OOP) - 2009

Data-Oriented Design (Or Why You Might Be Shooting Yourself in The Foot With OOP) - 2009

Data Locality - 2009

Data Alignment - 2009. Part I & Part II.

A Templated C++ Attribute Library for Object Persistence and Export - 2008

Data-Oriented Design

Data-Oriented Design book

Practical Examples in Data Oriented Design

Memory Optimization

Adventures in data-oriented design – Part 3a: Ownership- 2013

Data Oriented Design : Starting Up - 2013

https://www.randygaul.net/2013/05/05/data-oriented-design-starting-up/

Data oriented design is not about SoA and ECS - 2020

https://www.polymonster.co.uk/blog/dod-ecs

How we made particles twice as fast through cache optimisation

http://joostdevblog.blogspot.com/2020/03/how-we-made-particles-twice-as-fast.html