Memory, CPU Caches and Why Array Order Matters

Big-O (DSA Lesson 12) counts steps. It does not count where the steps read from. Two loops that are both O(n²) can differ by 10 times in real time, because one of them walks memory in the order it is stored and the other one does not. Interviewers like this topic because it separates people who only know the formula from people who have seen a profiler.

You need three things: a rough map of how slow each kind of memory is, the idea of a cache line, and one habit (walk memory in order). Everything is measured below with plain JavaScript and typed arrays, so you can run it yourself. Read Lesson 0 first for stack, heap and typed arrays.

Words used in this lesson

• RAM (main memory) is the big, slower memory where your program's data lives.
• A CPU cache is a small, very fast memory on the CPU chip that holds copies of recently used data from RAM. L1, L2, L3 are the levels: L1 is the smallest and fastest, L3 is the biggest and slowest of the three.
• A cache line is the block the cache loads at one time, usually 64 bytes. You never load one byte alone.
• A cache hit means the data was already in the cache. A cache miss means it was not, so the CPU waits while the line is fetched from a lower level.
• Latency is how long one access takes. Bandwidth is how many bytes per second can flow.
• Locality is the habit of programs to use data that is near (in space) or recent (in time).
• Spatial locality: if you used address X, you will soon use X+1, X+2, and so on.
• Temporal locality: if you used X, you will soon use X again.
• Row-major order means a 2-D table is stored row after row in memory. Column-major is the other way. JavaScript and C use row-major.
• A prefetcher is hardware that guesses the next memory you will need and loads it early.
• A thread is one stream of execution. False sharing is when two threads write to different variables that sit on the same cache line, which makes the CPU cores fight over the line.

The memory hierarchy

Fast memory is small and costly. Large memory is slow and cheap. Computers stack them like a pyramid, and each level holds copies of the one below.

A good picture: if L1 is a book on your desk (1 second to reach), L3 is a shelf in the room (10 to 40 seconds), RAM is a library across town (about 2 minutes), and an SSD is a trip to another city (several hours). The CPU does billions of operations per second, so waiting for RAM often costs more than the arithmetic.

Cache lines: memory comes in 64-byte blocks

When your code reads one Float64 (8 bytes) at address X, the CPU does not load 8 bytes. It loads the whole 64-byte line that contains X: the 8 doubles around it. The next 7 reads in order are then cache hits. This is the entire reason ordered access is fast.

Address:   0         8        16       24       32       40       48       56   | 64 ...           [ d0 ][ d1 ][ d2 ][ d3 ][ d4 ][ d5 ][ d6 ][ d7 ]  <- one cache line  | next lineRead d0: miss, whole line loaded.  Read d1..d7: hits (already there).

Two kinds of locality make the cache work:

• Spatial locality: walking an array in order uses every byte of every line you load.
• Temporal locality: reusing a value soon after you read it (a loop counter, a running sum, a small lookup table) keeps it in L1.

The CPU also has a prefetcher. If you walk memory with a steady stride, it notices and loads the next lines before you ask. Random jumps defeat it.

Experiment 1: row-major against column-major

A matrix is stored as one flat list, row after row. Element (r, c) is at r * N + c. Summing it row by row reads neighbours. Summing it column by column jumps N * 8 bytes between reads. Same number of additions. I ran:

// Row-major vs column-major sum over an N x N matrix stored in one flat Float64Arrayconst N = 4096;const m = new Float64Array(N * N).fill(1);function rowMajor() { let s = 0; for (let r = 0; r < N; r++) for (let c = 0; c < N; c++) s += m[r * N + c]; return s; }function colMajor() { let s = 0; for (let c = 0; c < N; c++) for (let r = 0; r < N; r++) s += m[r * N + c]; return s; }function time(f) { const t = process.hrtime.bigint(); const v = f(); return [Number(process.hrtime.bigint() - t) / 1e6, v]; }function median(f, runs = 7) { const a = []; for (let i = 0; i < runs; i++) a.push(time(f)[0]); a.sort((x, y) => x - y); return a[runs >> 1]; }rowMajor(); colMajor(); // warm upconst r = median(rowMajor), c = median(colMajor);console.log(`N=${N} (${(N*N*8/1048576)} MB)  row-major ${r.toFixed(1)} ms   column-major ${c.toFixed(1)} ms   ratio ${(c/r).toFixed(1)}x`);

N=4096 (128 MB)  row-major 36.7 ms   column-major 313.7 ms   ratio 8.5x

(A second full run gave 36.4 ms and 317.2 ms, ratio 8.7.) Same work, about 8.5 times slower. The fill(1) and the warm-up call matter: the first call also lets V8 compile the function, which is a different cost (Lesson 0).

The gap depends on the size

I repeated it for smaller matrices (same code with n instead of N):

This is the cache hierarchy showing itself. At 512 KB the whole matrix fits in this machine's L2 (1 MB per core), so even a bad order is cheap. As the matrix grows past L2 (8 MB) and past L3 (33 MB), more reads must go to RAM and the bad order pays a full miss for almost every read. The ratio stops growing once the data is much bigger than the caches. On a small input you will not see the effect, which is why "it is fast on my test data" proves little.

Does it hold for arrays of arrays?

Most JavaScript code uses grid[r][c] with ordinary arrays. I ran the same test with Array.from({length: N}, () => new Array(N).fill(1)):

array of arrays 4096x4096: row-first 38.0 ms, column-first 547.1 ms, ratio 14.4x

Row-first was about as fast as the flat typed array. Column-first was slower still (about 14 times), probably because each step also has to jump to a different row array. I did not dig into the reason, so treat "probably" as a guess. The advice is the same: make the inner loop run over the last index.

Experiment 2: strides and cache lines

If cache lines matter, reading every 8th double should not be 8 times cheaper, because every line must still be loaded. I read a 128 MB Float64Array with a step of k and timed the whole loop:

const N = 1 << 24; // 16M doubles = 128 MBconst a = new Float64Array(N).fill(1);for (const k of [1, 2, 4, 8, 16, 32]) {  const f = () => { let s = 0; for (let i = 0; i < N; i += k) s += a[i]; return s; };  f();  const ms = median(f);  console.log(String(k).padStart(6), String(N / k).padStart(9), ms.toFixed(1).padStart(8), ((ms * 1e6) / (N / k)).toFixed(2).padStart(8));}

stride  reads       ms    ns/read     1  16777216     32.1     1.92     2   8388608     21.4     2.55     4   4194304     16.9     4.02     8   2097152     15.0     7.16    16   1048576     13.8    13.14    32    524288      8.1    15.48

(median and time are the helpers from the first experiment.) With stride 1 each read is about 2 ns. With stride 8 we do 8 times fewer reads but the loop takes about half the time, so each read costs 3.7 times more (7.16 ns). At stride 8 each read touches a new 64-byte line, and the work is now limited by moving lines, not by the additions. The drop at stride 32 is probably the hardware prefetcher and memory system doing better with a very regular pattern; I did not test that, so I only report the numbers.

Experiment 3: sequential against random order

Same 4 million reads from a 32 MB array. In one run I read the elements in order using an index array 0, 1, 2, .... In the other I read them with the index array shuffled:

sequential indices 8.0 ms;  random indices 88.7 ms  ( 4194304 reads of a 32 MB array)

Eleven times slower, and the only change was the order. This is the case for a linked list or a big hash table with scattered entries: each step is a new address that the prefetcher cannot guess. It is a reason that a plain array often beats a linked list in practice, even when the textbook Big-O says they are equal for the operation you do.

Array of structs against struct of arrays

Say you have 2 million records, each with five fields (x, y, z, w, id), and you want the sum of x. There are three common layouts:

• Array of structs (AoS): an array of objects {x, y, z, w, id}. All fields of one record sit together.
• Array of structs in one flat typed array: five doubles per record in one Float64Array, so x of record i is at i * 5.
• Struct of arrays (SoA): one typed array per field, x[i], y[i], and so on.

const N = 2_000_000;const aos = Array.from({ length: N }, (_, i) => ({ x: i, y: 1, z: 2, w: 3, id: i }));const soa = { x: new Float64Array(N), y: new Float64Array(N), z: new Float64Array(N), w: new Float64Array(N), id: new Float64Array(N) };for (let i = 0; i < N; i++) { soa.x[i] = i; soa.y[i] = 1; soa.z[i] = 2; soa.w[i] = 3; soa.id[i] = i; }const flat = new Float64Array(N * 5);for (let i = 0; i < N; i++) { flat[i*5] = i; flat[i*5+1] = 1; flat[i*5+2] = 2; flat[i*5+3] = 3; flat[i*5+4] = i; }const sumAos = () => { let s = 0; for (let i = 0; i < N; i++) s += aos[i].x; return s; };const sumSoa = () => { let s = 0; const x = soa.x; for (let i = 0; i < N; i++) s += x[i]; return s; };const sumFlat = () => { let s = 0; for (let i = 0; i < N; i++) s += flat[i * 5]; return s; };

sum of x over 2000000 recordsarray of objects       21.21 msflat typed, stride 5   10.17 msstruct of arrays       4.54 mssums equal: true

(Median of 9 runs, using the same median helper.) SoA was about 4.7 times faster than the array of objects, and about twice as fast as the flat strided layout. The reason is how many cache lines you must load:

SoA wastes nothing when you read one field of every record. It is also easy for V8 to turn into tight machine code (Lesson 0). The trade-off: if you usually need all fields of one record (for example, show one user), AoS keeps them together in a single line, and is the more natural code. Choose by access pattern. This is the idea behind "data-oriented design" in game engines, which store particles or entities in SoA form for this reason.

A caution: I made the objects one after another, so in memory they are probably close together. A real program whose objects were created at different times, with other allocations in between, can be slower than my number, not faster.

False sharing in one paragraph

Caches keep each line coherent across cores: when one core writes to a line, other cores' copies of that line are thrown away. If two threads write to two different variables that happen to live on the same 64-byte line, each write forces the other core to reload the line, although the threads share no data. This is false sharing. It can slow down parallel code badly, and the fix is padding: put each thread's variable on its own line. In JavaScript it only matters when you use SharedArrayBuffer with worker threads. I tested it with two workers each doing 20 million Atomics.add calls on an Int32Array:

// each worker: for (let i = 0; i < 20_000_000; i++) Atomics.add(a, slot, 1);// slots 0 and 1 are 4 bytes apart (same cache line); slots 0 and 32 are 128 bytes apart

adjacent slots (4 bytes apart)     1157 mspadded slots (128 bytes apart)      609 msadjacent slots (4 bytes apart)     1397 mspadded slots (128 bytes apart)      539 msadjacent slots (4 bytes apart)     1339 mspadded slots (128 bytes apart)      444 ms

Padding made the workers about 2 to 3 times faster in these runs. The time includes starting the two workers, so the real gap in the loops is larger than shown. An honest note: my first attempt used a plain a[slot] += 1 on a Float64Array and showed no difference (about 600 to 700 ms either way). I do not know why (it may be how V8 compiles the plain store), so I switched to Atomics.add for the test above. The lesson: false sharing is real, but it is easy to fail to reproduce, so measure before you pad.

What this means for JavaScript

• Typed arrays are contiguous. A Float64Array(n) is one block of 8n bytes. Walking it in order is the ideal case for caches. A normal array of objects is a block of references, and each object may be elsewhere.
• Numbers in a regular array (an array holding only numbers) are stored compactly by V8 too, but an array holding mixed types or objects holds references. I only measured the cases above, not V8's internal array kinds.
• Use flat arrays for grids. grid[r * width + c] in one typed array, with loops that go row by row, is often both simpler to copy and faster than an array of arrays (DSA Lesson 25 covers matrix problems).
• Keep the hot loop's data small. If a loop only needs x, do not drag the whole object through the cache.
• Do not guess, measure. The optimiser, GC and cache all affect results. Warm up, repeat, take the median, and make the data big enough to leave the cache.
• Do not rewrite everything for this. Most web code is bound by the network and the database, not the cache. Use this when a profile shows a hot loop over large data.

A quick checklist for reading code

When you review a loop over big data, ask these five questions. They take a minute and catch most cache problems.

1. Which index changes fastest in the inner loop? It should be the last index of the array, the one whose neighbours are next to each other in memory.
2. How much of each record does the loop use? If it reads 8 bytes out of a 40-byte record, you are loading five times the data you need.
3. Is the next address predictable? Steady steps are good. Following pointers (linked lists, trees, objects that hold objects) is not.
4. Does the working set fit in a cache? A table of 100 KB stays in L1 and L2. A table of 1 GB cannot, so order matters a lot.
5. Did I measure? Warm up first, repeat, take the median, and run on data of realistic size.

Interview questions

Key takeaways

• Memory is a pyramid: each level is bigger and slower. Typical ratios are about 100 times from L1 to RAM and more from RAM to SSD. These numbers are typical, not exact.
• Memory moves in 64-byte lines. Use the neighbours of what you just read.
• Walk arrays in the order they are stored. For a 2-D table, the inner loop goes over the last index.
• On this machine, a 128 MB matrix took 37 ms row by row and 314 ms column by column. The gap grew with size and was small when the data fit in cache.
• Random access cost about 11 times more than sequential access for the same number of reads.
• If you read one field of many records, store that field in its own typed array (struct of arrays).
• False sharing needs shared memory and threads. It is real but easy to get wrong in a test, so measure.
• Always measure with warm-up, a median and data bigger than the cache. All numbers here are local.

What's next

Lesson 2: Floating Point, Why 0.1 + 0.2 Is Not 0.3. You now know that data is bytes in memory. Next we look at how a number is written into 8 of those bytes, and why that sometimes gives surprising answers.