Cache Lines and Spatial Locality

The Carton of Eggs Principle

How does the hardware decide what to put in the fast caches? It uses a principle called locality—the observation that programs tend to access data in predictable patterns.

When your code asks the CPU to read a single byte from memory (e.g., array[0]), the CPU doesn't just grab that one byte. It grabs a whole chunk of neighboring data surrounding it. This chunk is called a Cache Line. On virtually all modern x86 and ARM server processors, a cache line is 64 bytes long.

Imagine you are baking and need one egg. You don't go to the store and buy exactly one single egg; you buy a carton of 12. Why? Because it's highly likely that if you need one egg now, you'll need another one soon. The CPU applies the same logic.

There are two types of locality that caches exploit:

• Spatial Locality: If code accesses memory location N, it is highly likely to access locations N+1, N+2, N+3, etc. soon. This is why the CPU fetches an entire 64-byte cache line—it's pre-loading the neighbors.
• Temporal Locality: If code accesses memory location N now, it is likely to access location N again soon. This is why recently accessed data stays in cache rather than being immediately evicted.

The Performance Implication

This is why iterating over a contiguous array (arr[0], arr[1], arr[2]...) is incredibly fast. When the CPU fetches arr[0], it loads 64 bytes into the cache line. For a 4-byte integer array, that means arr[0] through arr[15] are all loaded in a single fetch. The next 15 accesses are cache hits—essentially free. The CPU also has a hardware prefetcher that detects sequential access patterns and proactively fetches the next cache line before you even ask for it, effectively hiding the latency entirely.

Contrast this with a linked list, where each node is a separately allocated object scattered randomly across the heap. Following a pointer from one node to the next almost always lands on a different cache line, causing a cache miss every single time. This is called pointer chasing, and it's one of the most cache-hostile patterns in computing.

Struct Layout and Padding

Cache line awareness also affects how you design data structures. Consider a struct that is accessed in a tight loop:

// Cache-hostile: fields used together are far apart
struct Event {
    char     name[128];        // 128 bytes — rarely needed in hot path
    uint64_t timestamp;        // 8 bytes   — needed every iteration
    uint32_t event_type;       // 4 bytes   — needed every iteration
    char     description[256]; // 256 bytes — rarely needed
};
// Total: 396 bytes. Hot fields (timestamp + event_type) span bytes 128–140.
// Loading them requires fetching cache lines 2 and 3 of the struct.

// Cache-friendly: hot fields grouped at the front
struct Event {
    uint64_t timestamp;        // 8 bytes  — hot: fits in first cache line
    uint32_t event_type;       // 4 bytes  — hot: fits in first cache line
    char     name[128];        // cold
    char     description[256]; // cold
};
// Hot fields now fit in the first cache line (bytes 0–11).
// Cold fields are only loaded when explicitly needed.

For even more aggressive optimization, the Struct of Arrays (SoA) pattern separates fields into parallel arrays, so a loop that only needs timestamp values loads only timestamp data—no wasted cache space on unused fields.

// Array of Structs (AoS) — cache-hostile for partial field access
struct Event events[1000];  // timestamp, event_type, name, description interleaved

// Struct of Arrays (SoA) — cache-friendly for partial field access
struct EventStore {
    uint64_t timestamps[1000];    // all timestamps contiguous
    uint32_t event_types[1000];   // all event_types contiguous
    char     names[1000][128];    // all names contiguous
};
// A loop summing timestamps only touches the timestamps[] array — perfect locality.

Key Point: The performance difference between cache-friendly and cache-hostile data structures is not a small constant factor—it can be 10x–50x for large datasets. This is why performance-critical systems (databases, game engines, network stacks) overwhelmingly prefer arrays and structs-of-arrays over linked lists and trees of heap-allocated nodes. When choosing data structures, "cache-friendliness" should be a first-class design criterion alongside correctness and algorithmic complexity.