Step 2 of 5

Arrays of structs vs structs of arrays

Object-oriented code naturally stores each thing as one struct, and many things as an array of those structs (AoS, array of structs):

struct Particle { double x, y, z, vx, vy, vz, mass, charge; };   // 64 bytes
std::vector<Particle> particles;
for (auto& p : particles) p.x += p.vx * dt;                   // uses 16 of every 64 bytes

Each Particle is exactly one 64-byte cache line, and this loop needs only x and vx from it. Three quarters of every line it loads is wasted bandwidth.

A struct of arrays (SoA) flips the layout: one array per field.

struct Particles {
    std::vector<double> x, y, z, vx, vy, vz, mass, charge;
};
for (std::size_t i = 0; i < ps.x.size(); i++) ps.x[i] += ps.vx[i] * dt;   // every byte loaded is used

Now the loop streams through two dense arrays, and every byte it loads is useful. The compiler can also process several elements per instruction (SIMD, the vector units in every modern processor), because the x values sit next to each other. For 4 million particles and 10 passes, the AoS loop took 254 ms and the SoA loop 34 ms (GCC -O2, 4-core Linux machine): 7 times faster for the same arithmetic.

#include <iostream>
#include <vector>

struct Particle { double x, y, z, vx, vy, vz, mass, charge; };

int main() {
    std::size_t n = 1'000'000;
    std::cout << "one particle: " << sizeof(Particle) << " bytes\n";
    std::cout << "x += vx touches " << n * sizeof(Particle) / 1'000'000 << " MB as AoS, "
              << n * 2 * sizeof(double) / 1'000'000 << " MB as SoA\n";
}

one particle: 64 bytes
x += vx touches 64 MB as AoS, 16 MB as SoA

When to use which

• SoA wins when hot loops use a few fields of many objects: physics, particle systems, analytics over columns (column-oriented databases like ClickHouse are SoA at the storage level), game engines' entity systems.
• AoS wins when code uses most fields of one object at a time, and it's simpler to read and write. It's the right default.
• Designing around how data is accessed, rather than around objects, is called data-oriented design. Measure before converting: the gain comes only in loops that are actually memory-bound.

Your turn: write Particles, a struct-of-arrays store for 2D particles: add(x, y, vx, vy) appends one, step(dt) moves every living particle by its velocity times dt, kill(i) marks particle i dead, and alive_count() counts the living. Keep each field in its own std::vector.

Previous: Caches and contiguous memory Next: Branches and branch prediction