AoS vs SoA in C: Cache Locality and Performance

Choosing between an Array of Structures (AoS) and a Structure of Arrays (SoA) in the C programming language fundamentally dictates how modern CPU caches interact with your application's data. This article explores how hardware cache lines, spatial locality, and memory access patterns determine the optimal data layout, contrasting the traditional object-centric AoS layout with the performance-oriented SoA layout commonly utilized in high-throughput computing.

Understanding CPU Cache Lines and Spatial Locality

Modern CPUs do not fetch individual bytes from system memory. Instead, memory is transferred into CPU caches in fixed-size blocks called cache lines, which are typically 64 bytes wide.

Spatial locality refers to the principle that accessing a particular memory address makes it highly probable that adjacent memory addresses will be accessed soon after. When your code accesses a variable, the hardware loads the entire 64-byte cache line containing that variable. If your algorithms process memory contiguously, almost every load hits the high-speed L1/L2 cache. If your data layout leaves gaps between relevant fields, the processor wastes memory bandwidth loading unused bytes, leading to cache pollution and stalling execution.

The Array of Structures (AoS) Layout

The Array of Structures layout represents the conventional, object-oriented approach in C where a single struct holds all attributes of an entity, and an array contains instances of that struct.

struct Particle {
    float x, y, z;
    float vx, vy, vz;
    int id;
    int active;
};

struct Particle particles[1024];

In memory, each Particle is stored contiguously: [x, y, z, vx, vy, vz, id, active][x, y, z, ...]

Cache Locality Characteristics of AoS

• Optimal for entity-centric operations: If a function processes all attributes of a single particle at once—such as reading positions, computing velocities, and modifying state—AoS provides exceptional spatial locality. Loading the structure brings all its related fields directly into the cache.
• Inefficient for attribute-isolated operations: If a loop only needs to update positions (x += vx), the cache line still fetches id, active, and other non-essential fields. This wastes a substantial percentage of the 64-byte cache line, forcing the CPU to request new cache lines from higher-latency memory far more frequently.

The Structure of Arrays (SoA) Layout

The Structure of Arrays layout decomposes the entity, grouping identical attributes together into separate, parallel arrays within a single encompassing struct.

struct ParticleSystem {
    float x[1024];
    float y[1024];
    float z[1024];
    float vx[1024];
    float vy[1024];
    float vz[1024];
    int id[1024];
    int active[1024];
};

struct ParticleSystem system;

In memory, attributes of the same type are contiguous: [x0, x1, x2, ...][y0, y1, y2, ...][z0, z1, z2, ...]

Cache Locality Characteristics of SoA

• Optimal for data streaming and transformations: When iterating over a single attribute across all elements, every single byte fetched into a 64-byte cache line is utilized. For example, a 64-byte cache line can hold 16 contiguous 32-bit float values. Updating positions achieves 100% cache line efficiency without loading unrelated fields.
• Vectorization (SIMD) friendly: Contiguous memory layout allows compilers to easily vectorize operations using SIMD instructions (such as AVX or SSE), operating on 4, 8, or 16 elements per instruction cycle.
• Inefficient for single-entity lookups: Accessing all properties of a specific particle (e.g., retrieving x, y, z, and id for index i) requires accessing multiple distinct memory regions, potentially triggering several simultaneous cache line fetches.

Architectural Trade-Offs

Selecting the Right Layout

1. Choose AoS when:
   • Entities are frequently sorted, added, or removed individually.
   • Functions regularly consume the majority of a structure's fields together.
   • Working with high-level systems where readability and object encapsulation take precedence over raw streaming throughput.
2. Choose SoA when:
   • Processing pipelines iteratively transform subsets of attributes (e.g., physics engines, rendering, digital signal processing).
   • Code execution is bound by memory bandwidth rather than compute limits.
   • Auto-vectorization or explicit SIMD hardware instructions are required to maximize performance.