Reducing Indirection

In this lesson, you will learn how to improve CPU performance by "flattening" nested data structures to minimize pointer chasing.

The Cost of Indirection

In Rust, we often model data using nested structures like Box<T>, Vec<Box<T>>, or complex linked structures. While these are flexible, they are performance bottlenecks. Every time you access a Box<T>, the CPU must perform a memory dereference. If the data is located far away in the heap, the CPU may trigger a "cache miss," forcing it to stall while it waits for data to arrive from slower main memory.

Reducing indirection means transforming your data layout so that related pieces of information reside closer together in memory, ideally in a single, contiguous block.

Flattening Your Structures

Consider a list of users, where each user owns a profile that is heap-allocated:

struct Profile { /* ... */ }

struct User {
    id: u32,
    profile: Box<Profile>, // Indirection: Must jump to another memory location
}

If you iterate through a Vec<User>, you are constantly jumping between the Vec's memory and the individual heap allocations for each Profile. To reduce this indirection, we can flatten the structure:

struct User {
    id: u32,
    profile: Profile, // Direct: Data is stored inline within User
}

By removing the Box, the Profile data is now stored directly inside the User struct. When you load a User into the CPU cache, you automatically load the Profile as well. This creates "spatial locality," meaning the data you need for the next operation is already sitting in your high-speed cache lines.

When to Flatten

You should aim to flatten structures when:

1. The nested type has a fixed size: If the inner data size is known at compile-time, Box is often unnecessary.
2. You process items in bulk: If you frequently iterate over a collection, flattening keeps the cache pipeline full.
3. Latency is critical: Every pointer dereference is a potential branch or wait state. By packing data into a single contiguous block, you ensure the CPU spends more time computing and less time waiting for memory.

Key Takeaway: By removing layers of indirection and embedding data directly, you convert expensive pointer-chasing into efficient, cache-friendly sequential memory access.