Performance-Critical Data Layouts

In this lesson, you will learn how to select the right data structure by prioritizing CPU cache efficiency and memory layout.

When writing high-performance Rust, your biggest enemy isn't just the number of instructions executed, but how often the CPU has to wait for data to be fetched from main RAM. Because RAM is significantly slower than your CPU cache, we organize data to ensure it is "cache-friendly."

Arrays vs. Vectors vs. Linked Lists

To choose the right structure, consider the access pattern:

• Arrays ([T; N]): These are the gold standard for performance. Because the size is fixed at compile time, the data is allocated contiguously on the stack. The CPU can easily predict and pre-fetch this memory, leading to zero-latency access. Use these when the size is known and won't change.
• Vectors (Vec<T>): A Vec is essentially a heap-allocated array that can grow. It maintains cache locality because, like an array, its elements are stored in a contiguous block of memory. Iterating over a Vec is nearly as fast as an array because the CPU can "stride" through the memory linearly.
• Linked Lists (LinkedList<T>): In a linked list, each node is an independent allocation on the heap. These nodes are scattered throughout your memory address space. When you traverse a linked list, the CPU must jump to random locations in memory, causing "cache misses." Your processor sits idle while it waits for each new node to be fetched from RAM.

When to choose what?

If you need to iterate over data frequently, always favor an array or a Vec. They allow the hardware prefetcher to load your data into the cache before you even ask for it.

// Good: Contiguous memory, cache-friendly
let data = vec![1, 2, 3, 4]; 

// Avoid: "Pointer chasing" leads to cache misses
// Each node is a separate allocation in a different memory location
let list = std::collections::LinkedList::from([1, 2, 3, 4]);

Only use a LinkedList if you have a very specific performance requirement where you must insert or remove elements from the middle of the collection frequently without moving other elements, and even then, consider if a different layout (like a VecDeque or a custom pool) could achieve better locality.

Key Takeaway: Prioritize contiguous memory layouts like Arrays and Vectors to maximize CPU cache hit rates and avoid the performance tax of pointer chasing.