Memory Layout & Cache Locality: Why Array Iteration is 10x Faster Than Linked Lists

In introductory computer science courses, big-O asymptotic analysis often presents a misleading picture of computational efficiency. On paper, inserting an element at the beginning of a linked list is O(1), while inserting into an array requires shifting elements in O(N) time. Iterating through $N$ elements in both data structures is categorized under identical O(N) linear time.

Yet, when you benchmark iterating through a continuous array versus traversing a linked list of identical size on modern hardware, the contiguous array frequently runs 10x to 50x faster.

Why does theoretical complexity fail to predict real-world wall-clock performance? The answer lies in the memory hierarchy, CPU cache architectures, and cache locality.

This deep dive explores how modern CPUs fetch memory, why pointer-chasing destroys performance, and how you can structure data layouts in C++, Rust, Go, and high-level languages for maximum throughput.

1. The Memory Latency Hierarchy#

To understand performance, you must understand the vast speed differences across the hardware hierarchy.

Hardware Latency Comparison#

When your CPU encounters a Cache Miss (data is not in L1/L2/L3), it sits idle for up to 200 clock cycles, waiting for RAM to deliver the payload.

2. Contiguous Memory vs. Pointer Chasing#

The Array Memory Layout: Sequential & Predictable#

An array allocates elements in a single contiguous block of physical RAM. When the CPU requests array[0], the memory controller retrieves the entire 64-byte cache line, pulling array[0] through array[15] (for 32-bit integers) into L1 cache simultaneously.

Contiguous Array in RAM (Cache-Friendly):
[ Int 0 | Int 1 | Int 2 | Int 3 | Int 4 | Int 5 | Int 6 | Int 7 ]
└─────────────────────── 64-Byte Cache Line ────────────────────┘

Furthermore, the CPU's Hardware Prefetcher detects sequential linear memory access patterns and begins proactively fetching the next cache lines from RAM into L2 cache before your loop even reaches them.

The Linked List Memory Layout: Fragmented Heap Traversals#

Each node in a linked list is allocated individually on the heap at arbitrary memory addresses.

Linked List in RAM (Cache-Hostile):
Address 0x1040: [ Value: 42 | Next: 0x8820 ] ──> (L1 Cache Miss!)
Address 0x8820: [ Value: 99 | Next: 0x3100 ] ──> (L1 Cache Miss!)
Address 0x3100: [ Value: 17 | Next: 0x9940 ] ──> (L1 Cache Miss!)

Every single step in a linked list requires dereferencing a pointer to an unpredictable address. The hardware prefetcher cannot predict where the next node lives, causing the CPU pipeline to stall on nearly every iteration.

3. Real-World Benchmarks: Array vs. Linked List#

Let us observe the wall-clock execution time for summing 10,000,000 integers in C++ / Rust:

// Benchmarking Array vs Linked List Traversal
#include <iostream>
#include <vector>
#include <list>
#include <chrono>

int main() {
    const int N = 10'000'000;
    
    // Contiguous Vector
    std::vector<int> vec(N, 1);
    
    // Node-Allocated Linked List
    std::list<int> lst(N, 1);

    // Benchmark Vector
    auto start = std::chrono::high_resolution_clock::now();
    long long sum_vec = 0;
    for (int n : vec) sum_vec += n;
    auto end = std::chrono::high_resolution_clock::now();
    std::cout << "Vector Time: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
              << " ms\n";

    // Benchmark List
    start = std::chrono::high_resolution_clock::now();
    long long sum_list = 0;
    for (int n : lst) sum_list += n;
    end = std::chrono::high_resolution_clock::now();
    std::cout << "Linked List Time: " 
              << std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count() 
              << " ms\n";

    return 0;
}

Benchmark Results (10M Integers, Modern x86_64 CPU)#

The contiguous vector is over 23 times faster purely due to hardware cache locality, despite both algorithms being O(N).

4. Struct of Arrays (SoA) vs. Array of Structs (AoS)#

Cache locality optimization does not stop at data structure selection—it extends to how you design your object schemas.

The Problem with Array of Structs (AoS)#

Consider a particle simulation where each entity has coordinates, velocities, mass, and color:

// Array of Structs (AoS) - Traditional OOP Design
struct Particle {
    x: f32,       // 4 bytes
    y: f32,       // 4 bytes
    z: f32,       // 4 bytes
    vx: f32,      // 4 bytes
    vy: f32,      // 4 bytes
    vz: f32,      // 4 bytes
    mass: f32,    // 4 bytes
    color: [u8; 4], // 4 bytes
    padding: [u8; 32], // Extra metadata (total 64 bytes)
}

// Memory Layout: [P0_all_fields][P1_all_fields][P2_all_fields]

If your physics system only updates positions (x += vx * dt), loading one Particle fills a 64-byte cache line with color and padding you do not need, wasting 60% of your memory bandwidth!

The Solution: Struct of Arrays (SoA)#

// Struct of Arrays (SoA) - Data-Oriented Design
struct ParticleSystem {
    x: Vec<f32>,
    y: Vec<f32>,
    z: Vec<f32>,
    vx: Vec<f32>,
    vy: Vec<f32>,
    vz: Vec<f32>,
    mass: Vec<f32>,
    color: Vec<[u8; 4]>,
}

Now, iterating through x and vx loads 16 contiguous floating-point values per cache line with zero wasted bytes, maximizing SIMD vectorization and CPU throughput.

5. Practical Rules for Writing Cache-Friendly Software#

1. Default to Contiguous Storage: Prefer std::vector (C++), Vec (Rust), ArrayList (Java), and standard packed arrays over linked structures.
2. Matrix Traversal Order (Row-Major vs. Column-Major): In C, C++, Rust, and Python (NumPy), 2D arrays are stored in Row-Major order. Always iterate rows first, then columns:
   cCopy

   // FAST: Sequential memory access
   for (int r = 0; r < ROWS; r++) {
       for (int c = 0; c < COLS; c++) {
           sum += matrix[r][c];
       }
   }
   
   // SLOW (10x slower): Strided jumps across memory rows
   for (int c = 0; c < COLS; c++) {
       for (int r = 0; r < ROWS; r++) {
           sum += matrix[r][c];
       }
   }
   

3. Avoid Excessive Object Wrapping in High-Level Languages: In JavaScript, Python, and Ruby, objects contain hidden metadata headers. When dealing with large numeric datasets, leverage TypedArrays (Float32Array, Int32Array) or NumPy buffers.
4. Group Related Hot Fields: Place fields that are frequently read together adjacent to each other within structs to ensure they land in the same 64-byte cache line.

Frequently Asked Questions#

Are linked lists ever useful on modern hardware?#

Linked lists have specific niche applications: when elements are extremely large (where node copying is prohibitive), when stable node pointers are required across concurrent mutations, or inside real-time OS kernels where memory allocation is static and embedded. For 99% of general applications, dynamic arrays (Vec / std::vector) are faster.

What is False Sharing in multi-threaded programming?#

False sharing occurs when threads running on different CPU cores modify distinct independent variables that happen to share the same 64-byte cache line. The cache coherence protocol invalidates the entire cache line across cores, drastically degrading multi-threaded scaling. Fix this by adding memory padding (e.g., alignas(64)).

How does garbage collection affect cache locality?#

Compacting garbage collectors (like in Java or .NET) help cache locality by defragmenting memory and moving living objects into contiguous heap blocks during GC cycles. However, non-compacting allocators leave fragmented memory that increases L1 cache misses over time.