Memory Efficient Generic Graphs

In this lesson, you will learn how to build high-performance graph structures by using generics to store node data in contiguous memory buffers.

The Problem with Pointer-Based Graphs

When we think of graphs, we often imagine "nodes" scattered throughout the heap, connected by Box or Rc pointers. While intuitive, this approach is cache-unfriendly. Because each node is allocated independently, the CPU must frequently wait for data to be fetched from distant memory addresses (a "cache miss").

Using Contiguous Storage

To optimize, we can move away from pointers and toward flat storage. By using a generic Vec<T>, we ensure that all nodes are packed tightly together in memory. Instead of storing a pointer to a neighbor, we store an usize index that maps to the position of the neighbor within that vector.

Here is a simplified example of how we define a generic graph structure using this approach:

struct Graph<T> {
    nodes: Vec<T>,
    edges: Vec<Vec<usize>>, // Adjacency list using indices
}

impl<T> Graph<T> {
    fn add_node(&mut self, node: T) -> usize {
        self.nodes.push(node);
        self.edges.push(Vec::new());
        self.nodes.len() - 1
    }

    fn add_edge(&mut self, from: usize, to: usize) {
        self.edges[from].push(to);
    }
}

Why This is Efficient

1. Cache Locality: By storing nodes in a Vec<T>, your hardware prefetcher can easily predict and load adjacent nodes into the CPU cache, drastically speeding up graph traversals.
2. Genericity: Because the Graph is generic over T, you can store simple data like u32 weights or complex structs. Since the storage layout remains a contiguous Vec, the performance benefit persists regardless of what T represents.
3. Reduced Allocations: Instead of allocating memory for every individual node, you allocate memory in large, predictable chunks. This minimizes the pressure on the memory allocator.

This pattern is the foundation for most high-performance game engines and simulation software written in Rust. By using indices instead of references, you also circumvent complex ownership issues that often arise when implementing graph cycles.

Key Takeaway: Replace pointer-heavy node structures with contiguous Vec buffers and index-based references to maximize cache efficiency and simplify memory management.