Indexing, Contiguity, and Cache Locality

Why does iterating through a 1,000,000-element array run 10x to 50x faster than traversing a 1,000,000-node linked list, even though both have identical O(n) theoretical time complexity?

The secret lies in hardware architecture: CPU Cache Lines and Spatial Locality.

The Memory Speed Gap

Modern CPUs can perform billions of calculations per second (gigahertz clocks), but reading data from main system RAM is comparatively sluggish:

Whenever the CPU requests data not present in cache (a cache miss), execution stalls for hundreds of clock cycles while waiting for RAM.

What is a Cache Line?

The CPU never transfers a single byte or single 4-byte integer from RAM. Instead, hardware transfers memory in blocks called Cache Lines (typically 64 bytes).

Copy codeRAM Transfer:
+----------------------------------------------------------------+
| 64-byte Cache Line transferred to L1 Cache in a single bus read |
| [Item 0][Item 1][Item 2][Item 3] ... [Item 15] (for 4B Ints)   |
+----------------------------------------------------------------+

Spatial Locality in Arrays

Spatial Locality states that if a memory location is accessed, nearby memory locations are extremely likely to be accessed soon.

Because arrays are contiguous:

1. When you access array[0], the hardware loads a 64-byte block containing array[0] through array[15] into L1 cache.
2. The subsequent reads array[1] through array[15] result in cache hits (1ns latency).
3. The CPU hardware prefetcher recognizes the sequential access pattern and proactively preloads future cache lines ahead of time.

Copy codeArray sequential traversal:
[0][1][2][3][4][5][6][7][8][9][10][11][12][13][14][15]  <- 1st Cache Line (1 miss, 15 hits!)

Pointer Hopping: The Linked List Cache Penalty

In a node-based data structure (Linked List, Tree, Graph), each node is allocated independently on the heap at non-contiguous memory addresses:

Copy codeHeap Memory Addresses:
Node A (0x1020) -> Node B (0x7F40) -> Node C (0x2100) -> Node D (0x9900)

When traversing a linked list:

1. Accessing Node A loads its 64-byte cache line. None of the other nodes are in that line!
2. Following node.next jumps to 0x7F40, causing a cache miss.
3. Following the next pointer jumps to 0x2100, causing another cache miss.
4. Result: Almost every node access is a cache miss, stalling the CPU repeatedly.

Benchmark Comparison

Consider summing 10,000,000 numbers:

Copy code// Contiguous IntArray: Blazing fast due to cache hits & SIMD vectorization
var sum = 0
for (num in intArray) {
    sum += num
}

// LinkedList of boxed Integers: ~10x-30x slower due to constant cache misses!
var listSum = 0
for (num in linkedList) {
    listSum += num
}

Summary

• Memory contiguity enables spatial locality: accessing one element preloads adjacent elements into CPU L1/L2 cache.
• Arrays benefit from sequential cache-line prefetching, minimizing CPU stalls.
• Node-based structures suffer from pointer hopping, where unpredictable heap addresses trigger frequent cache misses.