Front Matter

Data-Oriented Design

Richard Fabian

8th October 2018

Contents

1 Data-Oriented Design 3 1.1 It's all about the data . . . . . . . . . . . . . . 4 1.2 Data is not the problem domain . . . . . . . 6 1.3 Data and statistics . . . . . . . . . . . . . . . 12 1.4 Data can change . . . . . . . . . . . . . . . . 14 1.5 How is data formed? . . . . . . . . . . . . . . 18 1.6 The framework . . . . . . . . . . . . . . . . . . 21 1.7 Conclusions and takeaways . . . . . . . . . . 25

2 Relational Databases 27 2.1 Complex state . . . . . . . . . . . . . . . . . . 28 2.2 The framework . . . . . . . . . . . . . . . . . . 29 2.3 Normalising your data . . . . . . . . . . . . . 32 2.4 Normalisation . . . . . . . . . . . . . . . . . . 36 2.5 Operations . . . . . . . . . . . . . . . . . . . . 51 2.6 Summing up . . . . . . . . . . . . . . . . . . . 53 2.7 Stream Processing . . . . . . . . . . . . . . . 54 2.8 Why does database technology matter? . . . 55

3 Existential Processing 57 3.1 Complexity . . . . . . . . . . . . . . . . . . . . 58 3.2 Debugging . . . . . . . . . . . . . . . . . . . . 60 3.3 Why use an if . . . . . . . . . . . . . . . . . . 61 3.4 Types of processing . . . . . . . . . . . . . . . 66 3.5 Don't use booleans . . . . . . . . . . . . . . . 68 3.6 Don't use enums quite as much . . . . . . . 73 3.7 Prelude to polymorphism . . . . . . . . . . . 75 3.8 Dynamic runtime polymorphism . . . . . . . 76 3.9 Event handling . . . . . . . . . . . . . . . . . 79

i

4 Component Based Objects 83 4.1 Components in the wild . . . . . . . . . . . . 85 4.2 Away from the hierarchy . . . . . . . . . . . . 88 4.3 Towards managers . . . . . . . . . . . . . . . 91 4.4 There is no entity . . . . . . . . . . . . . . . . 94

5 Hierarchical Level of Detail 97 5.1 Existence . . . . . . . . . . . . . . . . . . . . . 98 5.2 Mementos . . . . . . . . . . . . . . . . . . . . 101 5.3 JIT mementos . . . . . . . . . . . . . . . . . . 103 5.4 Alternative axes . . . . . . . . . . . . . . . . . 106 5.5 Collective LOD . . . . . . . . . . . . . . . . . . 110

6 Searching 113 6.1 Indexes . . . . . . . . . . . . . . . . . . . . . . 113 6.2 Data-oriented Lookup . . . . . . . . . . . . . 115 6.3 Finding low and high . . . . . . . . . . . . . . 120 6.4 Finding random . . . . . . . . . . . . . . . . . 121

7 Sorting 125 7.1 Do you need to? . . . . . . . . . . . . . . . . . 125 7.2 Maintaining . . . . . . . . . . . . . . . . . . . 128 7.3 Sorting for your platform . . . . . . . . . . . . 128

8 Optimisations 135 8.1 When should we optimise? . . . . . . . . . . 137 8.2 Feedback . . . . . . . . . . . . . . . . . . . . . 138 8.3 A strategy . . . . . . . . . . . . . . . . . . . . 142 8.4 Tables . . . . . . . . . . . . . . . . . . . . . . . 146 8.5 Transforms . . . . . . . . . . . . . . . . . . . . 151 8.6 Spatial sets . . . . . . . . . . . . . . . . . . . . 152 8.7 Lazy evaluation . . . . . . . . . . . . . . . . . 153 8.8 Necessity . . . . . . . . . . . . . . . . . . . . . 154 8.9 Varying length sets . . . . . . . . . . . . . . . 155 8.10 Joins as intersections . . . . . . . . . . . . . 158 8.11 Data-driven techniques . . . . . . . . . . . . 159 8.12 Structs of arrays . . . . . . . . . . . . . . . . 161

9 Helping the compiler 163 9.1 Reducing order dependence . . . . . . . . . . 163

10 Maintenance and reuse 179 10.1 Cosmic hierarchies . . . . . . . . . . . . . . . 180 10.2 Debugging . . . . . . . . . . . . . . . . . . . . 180 10.3 Reusability . . . . . . . . . . . . . . . . . . . . 183 10.4 Reusable functions . . . . . . . . . . . . . . . 186 10.5 Unit testing . . . . . . . . . . . . . . . . . . . 187 10.6 Refactoring . . . . . . . . . . . . . . . . . . . . 188

11 What's wrong? 189 11.1 The harm . . . . . . . . . . . . . . . . . . . . . 190 11.2 Mapping the problem . . . . . . . . . . . . . . 196 11.3 Internalised state . . . . . . . . . . . . . . . . 202 11.4 Instance oriented development . . . . . . . . 204 11.5 Hierarchical design vs change . . . . . . . . . 206 11.6 Divisions of labour . . . . . . . . . . . . . . . 209 11.7 Reusable generic code . . . . . . . . . . . . . 211