Data-oriented design

Object-oriented design starts from things: a Particle class with methods. Data-oriented design (DOD) starts from what the program does to its data, how often, and in which order, and lays the data out so the hardware can do that fast. Same algorithms, same big-O, often 5–10× faster.

This lesson covers:

• what the hardware actually charges you for;
• hot/cold splitting, struct of arrays, and arrays of structs of arrays;
• dense storage with generational handles instead of pointers;
• removing virtual dispatch from hot loops by grouping by type;
• branch prediction, and when the compiler removes the branch for you;
• batching.

Timings below were measured at -O2 on this course's machine. Lesson snippets run unoptimised under sanitizers, which changes timings a lot (ASan adds work to every memory access), so the numbers they print won't match. Copy a snippet and build it with -O2 locally to reproduce the effects.

1. What things cost

Rough latencies on a current desktop CPU:

Memory moves in 64-byte cache lines, and the prefetcher streams sequential lines in ahead of you. So the cost of a loop is mostly: how many cache lines does it touch, and can the prefetcher predict them? Two questions drive every technique below:

1. How many of the bytes I load do I actually use?
2. Is my access pattern sequential?

2. Hot/cold splitting

A struct that mixes fields used every frame (hot) with fields used rarely (cold) drags the cold bytes through the cache on every pass:

#include <chrono>
#include <cstddef>
#include <print>
#include <vector>

struct Fat {            // everything in one struct
    float x, vx;        // hot: updated every frame
    char name[56];      // cold: only read when printing
};

template <class F>
long long micros(F f) {
    auto t0 = std::chrono::steady_clock::now();
    f();
    return std::chrono::duration_cast<std::chrono::microseconds>(std::chrono::steady_clock::now() - t0).count();
}

int main() {
    constexpr std::size_t n = 1 << 18;
    std::vector<Fat> fat(n, Fat{1.0f, 0.5f, {}});
    std::vector<float> x(n, 1.0f), vx(n, 0.5f);      // hot fields only

    long long a = micros([&] { for (auto& p : fat) p.x += p.vx; });
    long long b = micros([&] { for (std::size_t i = 0; i < n; ++i) x[i] += vx[i]; });
    std::println("sizeof(Fat) = {}: each update loads a whole 64-byte line for 8 useful bytes", sizeof(Fat));
    std::println("fat structs {} us, hot arrays {} us (timings vary; see the note above)", a, b);
}

At -O2 with a million particles the hot arrays were ~10× faster (1.3 ms vs 13 ms): the fat loop uses 8 of every 64 bytes it loads, and the hot loop is contiguous floats the compiler vectorises.

The fix is to split by access frequency, not by "what belongs together":

struct ParticlesHot  { std::vector<float> x, y, vx, vy, life; };   // every frame
struct ParticlesCold { std::vector<std::string> name; std::vector<std::uint32_t> colour; };

3. AoS, SoA and AoSoA

• Array of structs (AoS): std::vector<Particle>. Natural; good when you use all fields of an element together.
• Struct of arrays (SoA): one array per field. Best when loops touch a subset of fields across many elements — every loaded byte is used, and each array is a clean stream for SIMD.
• Array of structs of arrays (AoSoA): blocks of, say, 8 elements stored SoA inside each block. Keeps SIMD-friendly lanes and keeps one element's fields within a few cache lines. Used in high-performance physics and rendering.

Count the lines. A toy cache (4 sets × 2 ways × 16-byte lines: room for 8 lines) runs two passes of "find the max x" over 16 particles of four floats each:

SoA has costs: adding or removing an element touches every array, and you lose the convenience of p.x. The particle system in this skill's build pays that price deliberately: one compaction pass moves every array at once.

4. Handles instead of pointers

Dense arrays move things around: push_back reallocates, swap-and-pop moves the last element into a hole. Pointers and iterators into them go stale, and using a stale pointer is undefined behaviour you can't test for.

Plain indices don't dangle in memory, but they go stale logically: after an erase and a reinsert, index 3 may name a different object. The standard solution is a generational handle: {slot index, generation}.

• A slot table maps a slot to the element's current position in the dense array.
• Each slot has a generation counter, bumped on every erase.
• A handle is valid only while its generation equals the slot's.

A stale handle is then just a number that fails a comparison: use-after-free becomes a well-defined nullptr.

Worked example: a tiny generational pool

#include <cstdint>
#include <optional>
#include <print>
#include <vector>

struct Handle { std::uint32_t index, generation; };

// Fixed slots, no dense array: the simplest generational structure.
class Pool {
public:
    Handle add(int value) {
        for (std::uint32_t i = 0; i < slots_.size(); ++i)
            if (!slots_[i].value) {                      // reuse a free slot
                slots_[i].value = value;
                return {i, slots_[i].generation};
            }
        slots_.push_back({value, 1});                    // generations start at 1
        return {static_cast<std::uint32_t>(slots_.size() - 1), 1};
    }
    void remove(Handle h) {
        if (int* p = get(h)) {
            slots_[h.index].value.reset();
            ++slots_[h.index].generation;                // old handles now fail
        }
    }
    int* get(Handle h) {
        if (h.index >= slots_.size()) return nullptr;
        Slot& s = slots_[h.index];
        return s.generation == h.generation && s.value ? &*s.value : nullptr;
    }

private:
    struct Slot { std::optional<int> value; std::uint32_t generation; };
    std::vector<Slot> slots_;
};

int main() {
    Pool pool;
    Handle a = pool.add(10);
    pool.remove(a);
    Handle b = pool.add(20);                             // reuses a's slot
    std::println("same slot: {}", a.index == b.index);
    std::println("a: {}", pool.get(a) ? "found" : "stale");
    std::println("b: {}", *pool.get(b));
}

It prints same slot: true, a: stale, b: 20. Without the generation, a would silently find 20: the "ABA" problem of handles.

This pool iterates slowly (it skips holes), so the build task's SlotMap adds a dense array for iteration and a dense → slot array so erase can move the last element into the hole in O(1).

Faded example: swap-and-pop with bookkeeping

You have values (dense), owner (owner[i] is the slot of values[i]) and where (where[slot] is the dense index). Fill in the erase of the element in slot:

std::uint32_t hole = where[slot];
std::uint32_t last = static_cast<std::uint32_t>(values.size() - 1);
values[hole] = std::move(values[last]);
owner[hole]  = /* ??? */;
where[/* ??? */] = hole;
values.pop_back();
owner.pop_back();

5. Grouping by type instead of virtual dispatch

A std::vector<std::unique_ptr<Shape>> looks tidy, but a hot loop over it does a pointer chase per element (each object lives somewhere else on the heap) and an indirect call the CPU must predict, with no inlining and no vectorisation.

If the set of types is known, keep one array per type and process each array with a plain loop:

#include <memory>
#include <print>
#include <vector>

struct Shape { virtual ~Shape() = default; virtual float area() const = 0; };
struct Circle : Shape { float r; explicit Circle(float r) : r(r) {} float area() const override { return 3.14159f * r * r; } };
struct Square : Shape { float s; explicit Square(float s) : s(s) {} float area() const override { return s * s; } };

int main() {
    // OOP style: mixed objects, virtual call per element.
    std::vector<std::unique_ptr<Shape>> mixed;
    // DOD style: one dense array per type.
    std::vector<float> circle_r, square_s;
    for (int i = 0; i < 1000; ++i) {
        float v = static_cast<float>(i % 7 + 1);
        if (i % 2) { mixed.push_back(std::make_unique<Circle>(v)); circle_r.push_back(v); }
        else       { mixed.push_back(std::make_unique<Square>(v)); square_s.push_back(v); }
    }
    float a = 0, b = 0;
    for (auto& s : mixed) a += s->area();
    for (float r : circle_r) b += 3.14159f * r * r;
    for (float s : square_s) b += s * s;
    std::println("same total: {}", a == b ? "yes" : "within rounding");
}

Over a million shapes at -O2, the per-type arrays were ~6× faster (4.3 ms vs 27 ms). Variations on the idea:

• sort by type before processing, so the indirect branch is predictable;
• std::vector<std::variant<Circle, Square>> keeps one array and removes the heap allocations (each element is inline), though visit still branches per element;
• an entity-component layout, where each component type lives in its own dense array keyed by entity handles: the slot map in this skill's build is the core of one.

6. Branches and branch prediction

The CPU guesses which way each branch goes and runs ahead. A wrong guess throws away ~15–20 cycles of work. Branches that depend on random data are wrong half the time; the same branch on sorted data is almost always right:

#include <algorithm>
#include <print>
#include <random>
#include <vector>

int main() {
    std::vector<int> v(1 << 16);
    std::mt19937 rng(1);
    for (int& x : v) x = static_cast<int>(rng() % 256);

    auto sum_big = [&] {
        long long sum = 0;
        for (int x : v)
            if (x >= 128) sum += x;     // taken ~50% of the time, randomly
        return sum;
    };
    long long before = sum_big();
    std::ranges::sort(v);               // now: all not-taken, then all taken
    std::println("same answer either way: {}", before == sum_big());
}

Measured at -O2 this was a surprise: no difference. GCC turned the if into a branchless conditional (and vectorised it), so there was nothing to mispredict. Forbidding that transformation (-fno-if-conversion -fno-tree-vectorize) brought back the classic effect: unsorted 8× slower (29 ms vs 3.6 ms).

The lessons:

• Look at the generated code before optimising branches. Use the Compiler tab: a cmov/csel or vector compare means there is no branch.
• Where the compiler can't remove the branch (complex bodies, calls, early exits), sorting or partitioning the data first often helps, and so does a branchless formulation:

sum += (x >= 128) * x;                    // arithmetic instead of a branch
int lo = std::min(a, b);                  // usually a cmov

7. Batching

Doing one thing to many elements beats doing many things to one element:

• the loop body's code stays in the instruction cache;
• the data streams sequentially;
• the compiler can vectorise a simple body.

So instead of for each particle: integrate, collide, cull, draw, run integrate all; collide all; cull all; draw all. Each pass is a tight loop over just the arrays it needs. The particle update in the build task is two such passes: integrate everything, then compact the survivors in one sweep.

Summary

• Start from the data and the access pattern; count cache lines, not instructions.
• Split hot from cold; prefer SoA when loops touch few fields of many elements.
• Keep data dense; refer to it with generational handles, not pointers.
• Remove per-element indirection in hot loops: arrays per type, or sort by type.
• Check the assembly before "fixing" branches; sort or partition when the branch really is there.
• Batch work into simple passes over contiguous arrays.