SoA and AoS, with Examples

By: Cam Wohlfeil
Published: 2019-02-08 1500 EST
Category: Programming
Tags: gamedev, cpp, rust, python, lua

Structure of arrays (SoA) and Array of structures (AoS) are ways of structuring data to minimize CPU cache misses, speeding up data access and taking better advantage of processing power, especially in parallel programming. After minimizing the amount of data you are reading, writing, and copying, this is the next logical step in optimization. Processors aren't getting much faster, if you want to crunch a lot of data and/or do it quickly, you have to stop wasting processor time.

It's hard to see the benefit such small examples, and even more so when many of us are working in garbage collected and highly abstracted environments. AoS is best when all values are accessed simultaenously, such as creating or tweening a shape something, you'll need all of the values of that shape. SoA is best when randomly accessing values, which is pretty much all the time (like changing points or inventory).

// Probably best as SoA storage
struct Health {
    float currentHealth;
    float maxHealth;
    float healthRegen;
}

// Probably best as AoS storage
struct Position {
    std::array<int, 1024> x;
    std::array<float, 1024> y;
    std::array<float, 1024> z;
}

Basic examples, in C++:

// Array of structs
struct Position {
    float x;
    float y;
    float z;
}
std::array<Transform, 1024> aos;

// Struct of arrays
struct Health {
    std::array<int, 1024> currentHealth;
    std::array<int, 1024> maxHealth;
    std::array<float, 1024> healthRegen;
}

Rust, basically the same as C++:

// AoS
struct Position {
    x: f32,
    y: f32,
    z: f32,
}
let aos: [Position; 1024];

// SoA
struct Health {
    currentHealth: [i32; 1024],
    maxHealth: [i32; 1024],
    healthRegen: [f32; 1024],
}

C#, again very familiar:

// AoS
public struct Position  
{  
    float x;  
    float y;  
    float z;  
}  
Position[] aos;

// SoA
public struct Health  
{  
    int currentHealth[];  
    int maxHealth[];  
    float healthRegen[];  
}

Lua only has tables, but you can structure the data correctly:

-- AoS
Position = {
    x, 
    y, 
    z
}
aos = {Position}

-- SoA
Health = {
    currentHealth = {}, 
    maxHealth = {}, 
    healthRegen = {}
}

Python also requires some finagling:

from collections import namedtuple # namedtuples make a good stand-in for structs

# Tuple of namedtuples, i.e. AoS
Position = namedtuple("Position", "x, y, z")
P = (Position)

# Namedtuple of tuples, i.e. SoA
Health = namedtuple("Health", "currentHealth, maxHealth, healthRegen")
Health(currentHealth=(), maxHealth=(), healthRegen=())

Check out the references for some more in depth explanations and visualizations.

References