Arrays & Memory Layout

In this lesson:

• why contiguous storage gives arrays O(1) random access
• the cost table: index, search, insert, delete
• 2D arrays in row-major order, and why traversal order affects speed
• cache locality, why "the same O(n)" can run 10× apart
• array-of-structs vs struct-of-arrays for sensor/sample data

This builds on the C arrays lesson; here the focus is layout and its performance consequences.

Contiguous storage is the whole trick

An array stores its elements back-to-back in memory. That single property is why a[i] is O(1): the address is pure arithmetic, no searching.

address of a[i] = base + i * sizeof(element)

 a[0]  a[1]  a[2]  a[3]
┌────┬────┬────┬────┐
│ 10 │ 20 │ 30 │ 40 │   each cell sizeof(int) apart
└────┴────┴────┴────┘
base  +4   +8   +12

The CPU computes the address in one step and reads it. No other structure gives O(1) random access for free, that's the array's superpower.

Array operation costs

That last row is the array's weakness: inserting at the front means shifting every later element up one slot. When you need cheap middle-insertion, a linked list (next lessons) trades away O(1) indexing to get it.

2D arrays are 1D underneath: row-major order

C stores a 2D array row by row, all of row 0, then all of row 1 (this is row-major order). The compiler maps m[r][c] to a flat offset:

offset(r, c) = r * COLS + c

int m[2][3]:   m[0][0] m[0][1] m[0][2] m[1][0] m[1][1] m[1][2]
 in memory →  ┌──────┬──────┬──────┬──────┬──────┬──────┐
              │  a   │  b   │  c   │  d   │  e   │  f   │
              └──────┴──────┴──────┴──────┴──────┴──────┘
                └──── row 0 ────┘ └──── row 1 ────┘

This matters when you manage a flat buffer yourself (common in embedded, a framebuffer, a sample matrix): you index it as buf[r * cols + c].

Traversal order and cache locality

Two loops that are both O(n·m) can run very differently because of the cache, a small fast memory that loads a line (e.g. 32 bytes) around each access. Walking memory sequentially uses every byte of each loaded line; jumping around wastes most of it.

// FAST: row-major traversal matches memory order — sequential, cache-friendly
for (int r = 0; r < ROWS; r++)
    for (int c = 0; c < COLS; c++)
        sum += m[r][c];        // consecutive addresses
 
// SLOW: column-major traversal jumps COLS elements each step — cache-hostile
for (int c = 0; c < COLS; c++)
    for (int r = 0; r < ROWS; r++)
        sum += m[r][c];        // strided, thrashes the cache

On a Cortex-M7 or any cached core, the first can be several times faster despite identical Big-O. Match your traversal to the storage order. (On a small Cortex-M0 with no cache the effect is smaller, but sequential access still helps flash wait-states and prefetch.)

Array-of-structs vs struct-of-arrays

How you group fields changes locality. Say you log samples with a timestamp and three axes:

// Array of Structs (AoS): natural, fields of one sample together
struct Sample { uint32_t t; int16_t x, y, z; };
struct Sample log_aos[256];
 
// Struct of Arrays (SoA): each field in its own array
struct {
    uint32_t t[256];
    int16_t  x[256], y[256], z[256];
} log_soa;

• AoS wins when you process whole samples at once (log[i].x/.y/.z are adjacent).
• SoA wins when you sweep one field across all samples (e.g. average all x values), that field is then contiguous, so the traversal is cache-friendly and SIMD/DSP-friendly. It can also pack better (no per-element padding between unlike fields).

For a DSP filter that processes one axis at a time, SoA can be markedly faster; for "handle one event fully," AoS is simpler. Pick based on your dominant access pattern.

Gotchas

• Front/middle insert is O(n). Every insert or delete that isn't at the end shifts elements. If that's your hot operation, an array is the wrong structure.
• Traversal order is not free. Column-major walks of a row-major array thrash the cache; loop in storage order. Same Big-O, very different cycles.
• Fixed capacity. A plain array can't grow; you size for the worst case (wasting RAM) or risk overflow. This is the fixed-memory tension the whole module returns to.
• 2D indexing by hand is error-prone. buf[r*cols + c] with the wrong cols, or swapping r/c, reads the wrong element or runs out of bounds. Wrap it in an accessor.

TL;DR

• Arrays store elements contiguously, which is exactly why indexing/update are O(1) (address arithmetic), no other structure gives that for free.
• Search is O(n) unsorted / O(log n) sorted; insert/delete is O(1) at the end but O(n) in the front/middle (shifting).
• C lays out 2D arrays row-major: m[r][c] lives at r*COLS + c. Manage flat buffers with that formula.
• Cache locality means traversal order matters: walk in storage order (row-major), two same-Big-O loops can differ several-fold in real time.
• Choose AoS when you process whole records, SoA when you sweep one field across many records (better locality, DSP/SIMD-friendly).