Data-Oriented Design

Sun, Jun 19, 2022

Data-Oriented Design (DOD) handlar om att sätta sitt data i främsta rummet, och aktivt resonera kring hur data struktureras och organiseras i minnet för maximera prestanda.

Varför är DOD relevant och viktigt?

I sin föreläsning Data-Oriented Design and C++ (YouTube) från CppCon 2014 presenterar Mike Acton sin syn på vad DOD är för någonting och inleder med att konstatera att “The purpose of all programs, and all parts of those programs, is to transform data from one form to another”. Acton menar att alla problem därför är dataproblem, och till dessa problem hör att förstå kostnaden med att arbeta med datat (läsa, skriva, etc). Han resonerar vidare att sammanhanget hjälper oss att förstå datat bättre, och att vi måste titta på data över tid för att förstå omfattningen av t ex kostnaden för data (t ex om data som är dyrt att läsas läses väldigt ofta, så är kostnaden större).

Den yttersta nyttan med DOD är högre prestanda, och det är lätt att förstå hur detta är relevant i spelbranschen där Mike Acton hör hemma, men av föreläsningen att döma så verkar Acton tycka att DOD är relevant för all systemutveckling. Acton hävdar att den främsta anledningen till att vi måste prata om DOD är tre stycken utbredda lögner:

  1. Mjukvaran är plattformen.
  2. Koden ska designas runt en model av världen.
  3. Koden är viktigare än datat.

Actons resonemang för att ovanstående är lögner är:

  1. Hårdvaran är plattformen. Olika hårdvara kräver olika lösningar, och generell portabilitet mellan olika typer av hårdvara är inte realistiskt. Vi bör alltid kunna ta reda på den minsta gemensamma nämnaren när det kommer till hårdvaran.
  2. Att modellera datat efter den riktiga världen är att idealisera problemet och bortse från dom faktiska begränsningarna i data och hårdvara.
  3. Varje programs syfte är att transformera data, och utvecklarens ansvar är att den transformeringen blir korrekt. Därför är datat viktigare än koden.

Tillämpandet av dessa tre “lögner”, menar Acton, leder till:

  • Dålig prestanda
  • Dålig parallellisering
  • Dålig möjlighet till optimisering
  • Dålig stabilitet
  • Dålig testbarhet

DOD i praktiken

I sin presentation från CppCon går Mike Acton sedan in på hur DOD ser ut i praktiken. Fem år senare håller emellertid Andrew Kelley ett föredrag på Handmade Seattle 2021, som heter A Practical Guide to Applying Data-Oriented Design, som uttalat är en uppföljare till Actons föredrag, och som mer pedagogiskt förklarar hur DOD ser ut i praktiken - när det används i Zig-kompilatorn.

Kärnan i Kelleys presentation är att de flesta CPU-instruktioner är “billigare” än att läsa data från primärminne (eller ännu värre, allokera minne på stacken). Så för att uppnå maximal prestanda så måste vi tänka på hur datat ser ut i minnet för att i så stor utsträckning som möjligt utnyttja CPUns cache (helst L1). För CPUn är snabb, men minnet är långsamt, menar Kelley, och presenterar en strategi för att realisera DOD: identifiera var du har många objekt i minnet, och reducera storleken på var och ett av dessa objekt.

Andrew Kelley fortsätter sedan med att lista ett antal strategier för att i sin tur reducera storleken på dessa objekt/structar:

  1. Använd index istället för pekare (index i en array istället för pekare till minnet).
  2. Representera booleska-värden utanför dina objekt (t ex i en separat array).
  3. Använd struct-of-arrays (det vill säga, en array per element i din struct).
  4. Spara udda data i hash maps (alltså värden som statistiskt sett är ovanliga).
  5. Använd “kodning” istället för OOP/polymorfism (vilket är en kombination av 1-4 istället för arv).

I strategierna ovan så handlar 1 och 4 om att direkt använda färre bytes av minnet, medan 2,3 och 5 handlar om att undvika padding, vilket blir en indirekt minnesanvändning. Padding kan uppstå när vi blandar olika datatyper i en struct eftersom moderna CPUer är optimerade för naturally aligned data. Att spara “padding” i cachen är ett uppenbart slöseri.

Andrew Kelley går sedan igenom utfallet av att använda dessa strategier på Zig-kompilatorn och hur det minskar antalet cache-missar, hur färre instruktioner anropas, hur färre CPU-cykler används, osv. Kelley nämner även dessa optimeringar i S2, E7 (YouTube) av Sourcegraph podcast och genomgången av Zig Roadmap 2023 (YouTube) från Zig Milan Party 2022.