# Why Cache Misses Are the Real Performance Killer

> Understand how CPU cache misses destroy performance and learn cache-friendly coding patterns that can deliver up to 100x speed improvements.

- Author: Shawn Ng (https://shawnng.com/about)
- Published: 2025-12-14
- Updated: 2026-09-30
- Canonical URL: https://shawnng.com/posts/cache-misses-performance-killer
- Topics: performance, systems, cpu-cache, optimization

## Key takeaways

- A cache-friendly loop can outperform a cache-unfriendly one by 10x to 100x while doing exactly the same number of operations.
- A single RAM access takes roughly 100 nanoseconds against about 1 nanosecond for an L1 cache hit, a 100x gap.
- CPUs load entire 64-byte cache lines rather than single bytes, which is why sequential access beats random access.
- Loop tiling works on sub-matrices small enough to stay in L1 cache and can make matrix multiplication 3-8x faster.
- Struct of Arrays beats Array of Structs when you touch only a few fields, because every cache line stays full of useful data.

Most developers optimize by choosing better algorithms. Fewer realize that how you organize data in memory can matter just as much, and sometimes more. A cache-friendly loop can outperform a cache-unfriendly one by 10x to 100x, even when both perform the exact same number of operations. The difference comes down to one thing: CPU cache behavior.

Check out the full video on my YouTube channel [Divide and Quantum](https://www.youtube.com/watch?v=211FB-kIAf0).

## The Memory Hierarchy Problem

Your CPU is fast. Absurdly fast. A modern processor can execute billions of operations per second. But main memory (RAM) is comparatively slow. A single RAM access takes roughly 100 nanoseconds, while an L1 cache hit takes about 1 nanosecond. That is a 100x difference.

To bridge this gap, CPUs use a hierarchy of caches:

| Cache Level | Size | Latency |
|---|---|---|
| L1 Cache | ~64 KB | ~1 ns |
| L2 Cache | ~256 KB | ~4 ns |
| L3 Cache | ~8-32 MB | ~12 ns |
| Main Memory (RAM) | ~16-64 GB | ~100 ns |

When the CPU needs data, it checks L1 first, then L2, then L3, and finally RAM. A **cache hit** means the data was found in cache. A **cache miss** means the CPU had to go to a slower level or all the way to RAM. When you get a cache miss, the CPU sits idle, waiting. Those nanoseconds add up fast.

## Cache Lines: The Unit of Transfer

CPUs do not load individual bytes from memory. They load entire **cache lines**, typically 64 bytes at a time. When you access one element of an array, the CPU loads the entire 64-byte block containing that element. If you then access the next element, it is already in cache for free.

This is why sequential access patterns are so much faster than random access patterns.

## Row-Major vs Column-Major: A 100x Difference

The most dramatic demonstration of cache effects is 2D array traversal order. In C and Python (NumPy), arrays are stored in **row-major order**, meaning elements of the same row are contiguous in memory.

```c
#include <stdio.h>
#include <time.h>

#define N 10000

int matrix[N][N];

// Cache-friendly: traverses rows (contiguous memory)
void row_major_traversal() {
    long sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sum += matrix[i][j];  // Sequential access
        }
    }
}

// Cache-unfriendly: traverses columns (jumps across memory)
void column_major_traversal() {
    long sum = 0;
    for (int j = 0; j < N; j++) {
        for (int i = 0; i < N; i++) {
            sum += matrix[i][j];  // Strided access - cache miss every time
        }
    }
}
```

In `row_major_traversal`, accessing `matrix[i][0]` loads `matrix[i][0]` through `matrix[i][15]` into a cache line (assuming 4-byte integers and 64-byte cache lines). The next 15 accesses are all cache hits.

In `column_major_traversal`, each access jumps to a completely different row. With a 10,000-column matrix, consecutive accesses are 40,000 bytes apart. Almost every single access is a cache miss.

The result? Row-major traversal can be **10x to 100x faster** on large matrices, despite doing exactly the same amount of work.

### Demonstrating in Python with NumPy

```python
import numpy as np
import time

n = 10000
matrix = np.random.rand(n, n)

# Cache-friendly: row-major traversal
start = time.perf_counter()
row_sum = 0.0
for i in range(n):
    for j in range(n):
        row_sum += matrix[i, j]
row_time = time.perf_counter() - start

# Cache-unfriendly: column-major traversal
start = time.perf_counter()
col_sum = 0.0
for j in range(n):
    for i in range(n):
        col_sum += matrix[i, j]
col_time = time.perf_counter() - start

print(f"Row-major: {row_time:.3f}s")
print(f"Col-major: {col_time:.3f}s")
print(f"Slowdown:  {col_time / row_time:.1f}x")
```

On a typical machine, the column-major traversal will be noticeably slower. In pure C, the difference is even more dramatic because Python's interpreter overhead partially masks the cache effects.

## Loop Tiling: Working Within the Cache

When you must access data in patterns that are not naturally sequential, **loop tiling** (also called blocking) restructures your loops to work on small blocks that fit entirely in cache.

Consider matrix multiplication. The naive triple loop has terrible cache behavior for one of the three matrices:

```c
// Naive matrix multiplication - poor cache behavior on B
void matmul_naive(int n, float A[n][n], float B[n][n], float C[n][n]) {
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < n; k++)
                C[i][j] += A[i][k] * B[k][j];  // B accessed column-wise
}

// Tiled matrix multiplication - cache-friendly
#define BLOCK 64

void matmul_tiled(int n, float A[n][n], float B[n][n], float C[n][n]) {
    for (int ii = 0; ii < n; ii += BLOCK)
        for (int jj = 0; jj < n; jj += BLOCK)
            for (int kk = 0; kk < n; kk += BLOCK)
                for (int i = ii; i < ii + BLOCK && i < n; i++)
                    for (int j = jj; j < jj + BLOCK && j < n; j++)
                        for (int k = kk; k < kk + BLOCK && k < n; k++)
                            C[i][j] += A[i][k] * B[k][j];
}
```

The tiled version processes small BLOCK x BLOCK sub-matrices that fit in L1 cache. The elements of B that were previously causing cache misses are now reused multiple times before being evicted. For large matrices, the tiled version can be 3-8x faster.

## Struct Layout: AoS vs SoA

How you organize your [data structures](https://shawnng.com/posts/data-structures-every-developer-should-master) also affects cache performance. Consider a particle simulation:

```c
// Array of Structs (AoS) - cache-unfriendly for position-only updates
struct Particle_AoS {
    float x, y, z;       // position
    float vx, vy, vz;    // velocity
    float mass;
    int type;
    char name[32];        // 64 bytes per particle: one full cache line
};
struct Particle_AoS particles[100000];

// Struct of Arrays (SoA) - cache-friendly for position-only updates
struct Particles_SoA {
    float x[100000];
    float y[100000];
    float z[100000];
    float vx[100000];
    float vy[100000];
    float vz[100000];
    float mass[100000];
    int type[100000];
};
struct Particles_SoA particles;
```

If you need to update only positions, the AoS layout loads the entire 64-byte struct into cache for every particle, wasting bandwidth on velocity, mass, type, and name fields you never touch. The SoA layout packs all x-coordinates contiguously, so every cache line is full of useful data.

This pattern is heavily used in game engines and high-performance computing. The Entity Component System (ECS) architecture popular in modern game development is essentially an industrial-strength application of SoA thinking.

## Practical Guidelines for Cache-Friendly Code

### 1. Prefer Sequential Access

Iterate over arrays in the order they are stored in memory. For C, Python (NumPy), and most languages, that means row-major order.

### 2. Keep Hot Data Small

The less memory your frequently-accessed data occupies, the more of it fits in cache. Use smaller types when possible. Separate hot fields from cold fields.

### 3. Avoid Pointer Chasing

Linked lists, trees with heap-allocated nodes, and [hash tables with chaining](https://shawnng.com/posts/hash-tables-how-they-work) all scatter data across memory. When you traverse them, every pointer dereference is potentially a cache miss. Consider array-based alternatives when performance is critical.

### 4. Batch Similar Operations

Instead of processing each item completely before moving to the next, process all items for one operation, then all items for the next operation. This keeps relevant data in cache.

```python
# Cache-unfriendly: process each entity completely
for entity in entities:
    update_position(entity)
    check_collision(entity)
    render(entity)

# Cache-friendly: batch by operation
for entity in entities:
    update_position(entity)
for entity in entities:
    check_collision(entity)
for entity in entities:
    render(entity)
```

## When Does This Matter?

Cache optimization is not something you should think about for every line of code. It matters most when you are processing large datasets, writing hot loops that execute millions of times, building game engines or simulations, or working on low-latency systems like trading platforms. The same memory hierarchy sets the ceiling in machine learning, where bandwidth is the real bottleneck when you [run LLMs on your own hardware](https://shawnng.com/posts/local-models-vs-frontier).

For most application code, choosing the right algorithm still matters more. But when you have already picked the optimal algorithm and still need more speed, cache-friendly data layout is often the biggest win left on the table. Understanding the memory hierarchy gives you a mental model that explains why some code is mysteriously fast and other seemingly equivalent code is mysteriously slow.

## Frequently asked questions

### What is a cache miss?

A cache miss is when the data the CPU needs is not in cache, so it has to fetch it from a slower cache level or from main memory. The CPU sits idle while it waits, and in a hot loop those nanoseconds dominate the runtime.

### Why is row-major traversal faster than column-major?

C and NumPy store 2D arrays row by row, so walking a row reads contiguous memory and most accesses hit a cache line that is already loaded. Column traversal jumps a full row each step, and on a 10,000-column matrix consecutive accesses are 40,000 bytes apart, so almost every one misses.

### How much faster is cache-friendly code?

On large matrices, row-major traversal can be 10x to 100x faster than column-major traversal doing identical work. Tiled matrix multiplication is typically 3-8x faster than the naive triple loop.

### When should I optimize for cache performance?

When you are processing large datasets, writing hot loops that execute millions of times, building game engines or simulations, or working on low-latency systems. For most application code, choosing the right algorithm still matters more.

## Sources

- Ulrich Drepper (2007). [What Every Programmer Should Know About Memory](https://www.akkadia.org/drepper/cpumemory.pdf). Red Hat.
- Monica S. Lam, Edward E. Rothberg, Michael E. Wolf (1991). [The Cache Performance and Optimizations of Blocked Algorithms](https://doi.org/10.1145/106972.106981). ACM (ASPLOS IV).
- ISO/IEC JTC1/SC22/WG14 (2011). [Programming languages: C (ISO/IEC 9899:201x, Committee Draft N1570)](https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1570.pdf).
- Peter Norvig (2001). [Teach Yourself Programming in Ten Years](https://norvig.com/21-days.html).