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 64 bytes, a whole cache line's worth, and this loop needs only x and vx from it. Three quarters of the memory 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 about 265 ms and the SoA loop about 60 ms (typical of several runs, GCC -O2, 4-core Linux machine): over 4 times faster for the same arithmetic, matching the 4 times less memory it reads.

#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 task

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.

Challenge 2

Convert an array of structs into a struct of arrays. Write Enemies to_soa(const std::vector<Enemy>& list), then long long total_hp(const Enemies& e) and std::size_t count_low(const Enemies& e, int limit) (how many have hp below limit). The last two only read the hp array.

Challenge 3

Removing dead particles from a struct of arrays must keep the arrays in step. Write void compact(Particles& p) that removes every particle with alive[i] == 0 from all five arrays, keeping the order, in one pass with a write index (no erase).

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