Memory Layout: Why the Same Algorithm Is Ten Times Slower

Two implementations with the same asymptotic complexity, on the same data, can differ by an order of magnitude. Complexity analysis counts operations and assumes memory access costs the same everywhere. It does not.

For a separate people-operations application of the same measurement discipline, see employee PC activity tracking.

The numbers that drive everything

Approximate, architecture-dependent, and the ratios are what matter:

Access	Cost
Register	under 1 cycle
L1 cache	~4 cycles
L2 cache	~12 cycles
L3 cache	~40 cycles
Main memory	~200+ cycles

Main memory is roughly fifty times slower than L1. A program that misses cache constantly spends most of its time waiting, and the CPU shows as fully utilised while doing almost nothing.

Memory moves in cache lines, typically 64 bytes. Reading one byte pulls in 64. If you use all of them, the other 63 were free. If you use one and move somewhere unrelated, you paid for 64 and used one.

That single fact explains most of what follows.

Sequential access wins, decisively

Iterating an array in order touches each cache line once, uses all of it, and the hardware prefetcher recognises the pattern and fetches ahead — so the data is often already there.

Following pointers through a linked structure produces a cache miss per node, in an order the prefetcher cannot predict. Nodes allocated at different times are scattered across memory.

This is why an array outperforms a linked list for traversal even where the complexity is identical, and why it frequently outperforms it for insertion in the middle too, up to surprisingly large sizes — copying contiguous memory is fast, and chasing pointers is not.

The practical rule: prefer contiguous storage unless you have measured a reason not to.

Arrays of structures versus structures of arrays

The layout decision with the largest effect, and it is invisible in most languages until you look for it.

An array of structures stores each record's fields together:

[x0 y0 z0 mass0] [x1 y1 z1 mass1] [x2 y2 z2 mass2] ...

A loop summing only mass reads a cache line, uses 8 bytes of it, and discards the rest. Most of your memory bandwidth is spent on fields you did not want.

A structure of arrays stores each field contiguously:

[x0 x1 x2 ...] [y0 y1 y2 ...] [mass0 mass1 mass2 ...]

Now the same loop uses every byte it fetches, and the compiler can vectorise it because the values are adjacent.

Choose by access pattern. If you usually touch all fields of one record, array-of-structures is right. If you usually touch one field across many records — which is what analytical workloads do — structure-of-arrays can be several times faster.

This is why columnar storage formats exist, and it is the same principle applied to files rather than memory.

False sharing

The concurrency version, and it produces slowdowns that look impossible.

Two threads write to two different variables. No shared state, no lock, no correctness problem. And the two variables sit in the same 64-byte cache line.

Cache coherence operates per line, not per variable. Each write invalidates the line in the other core's cache, so the line ping-pongs between cores and both threads stall.

The symptom is a parallel program that gets slower as you add threads, with no lock contention visible in any profile.

The fix is padding — separate the variables so they occupy different lines. Several languages provide an annotation for this, and where they do not, inserting unused bytes works.

Where it shows up in practice: an array of per-thread counters, adjacent fields in a shared structure updated by different threads, and lock-free queues with head and tail indices in the same line.

Struct field order

Compilers insert padding so each field lands on its natural alignment boundary. Field order therefore determines size.

struct Bad  { char a; long b; char c; };  // 24 bytes with padding
struct Good { long b; char a; char c; };  // 16 bytes

For one instance this is irrelevant. For a million, it is 8 MB of memory bandwidth wasted on nothing, and it changes how many records fit in cache.

Order fields largest to smallest. Some languages reorder automatically; C and C++ do not. It costs nothing to get right.

Branch prediction

The CPU pipelines instructions and guesses which way a branch will go. A correct guess is free; a wrong one costs a pipeline flush, on the order of 15–20 cycles.

Predictable branches are effectively free. A condition that is almost always true, or that alternates in a regular pattern, is predicted correctly.

Unpredictable branches are expensive. This is why sorting an array before filtering it can make the filter faster than the sort cost — sorted data makes the branch predictable.

Branchless alternatives — arithmetic or conditional-move instructions instead of a jump — help where the branch is genuinely random. Only worth doing where measurement shows the misprediction is the cost.

Where this actually matters

Not everywhere. Most application code is bound by I/O, network round trips or database queries, and cache behaviour is irrelevant. Optimising memory layout in a service that spends 90% of its time waiting on a database is wasted effort.

It matters when: you are processing large volumes in a tight loop, the profile shows the CPU busy but the work not progressing, cache miss counters are high, or a parallel program does not scale with threads.

Check before optimising. Hardware performance counters report cache misses and branch mispredictions directly, and the tooling to read them exists on every platform. A high miss rate is evidence; a hunch is not. See measuring performance properly.

What to do, in order

1. Confirm you are memory-bound. High CPU utilisation with low instructions-per-cycle, or a high cache miss rate. If you are not, stop here.

2. Make access sequential. Iterate in memory order. For a two-dimensional array, that means the loop order matching the storage order — row-major or column-major, and getting it backwards is a common and large mistake.

3. Shrink the data. Smaller records mean more fit in cache. Smaller integer types, field ordering, removing fields the hot path does not need.

4. Split hot from cold fields. If a loop touches two fields out of twenty, separating those two into their own array turns many misses into few.

5. Check for false sharing in anything parallel.

6. Only then consider branchless code and manual vectorisation, which are the most effort for the least reliable return.

The summary

Main memory is roughly fifty times slower than L1, and memory moves in 64-byte lines. Everything else follows.

Sequential beats pointer-chasing, usually by a lot, and often even where the complexity says otherwise.

Layout by access pattern — all fields of one record, or one field across many records.

False sharing makes parallel code slower as threads are added, with nothing visible in a lock profile.

And the precondition for all of it: confirm you are memory-bound first, because in most application code you are not.