Cache-Unfriendly C++: Identifying Access Patterns

The Principle of Data Locality

Before we dive into specific code patterns, let's establish the fundamental principle that governs cache efficiency: data locality. The core reason for poor cache performance is failing to use the data that the CPU has already fetched.

As you know, when the CPU needs a piece of data from RAM, it doesn't just fetch that one byte. It pulls in an entire cache line—a contiguous block of memory, typically 64 or 128 bytes. A cache hit occurs when the next piece of data the CPU needs is already in a cache line it holds. A miss occurs when it isn't.

The key insight is that performance is not just an attribute of your code's logic (the algorithm), but also of your data's layout in memory. The goal is to arrange data to maximize the use of each cache line brought in from RAM.

To visualize how this works with a familiar data structure, consider a simple 2D array in C++.

With this foundation, let's examine specific C++ patterns that violate the principle of data locality.

Pattern 1: Strided Memory Access

The most classic example of a cache-unfriendly pattern is accessing memory with a large, regular "stride" instead of sequentially. The canonical example is traversing a 2D matrix.

In C++, 2D arrays are stored in row-major order. This means that elements of the same row are contiguous in memory.

• Traversing row by row (for (row) { for (col) }) results in stride-1 access. This is highly cache-friendly because you are walking through memory sequentially. The CPU's prefetcher can predict this pattern and load the next cache line before you even need it.
• Traversing column by column (for (col) { for (row) }) results in stride-N access, where N is the number of elements in a row. You access one element, then jump N elements forward in memory to get the next one. This is extremely cache-unfriendly.

Identifying the Pattern: Look for nested loops iterating over multi-dimensional arrays. If the innermost loop iterates over an index that does not correspond to the contiguous dimension in memory, you have found a strided access pattern.

Pattern 2: Pointer Chasing

Your experience with data structures like linked lists, trees, and graphs is valuable here. These structures are often implemented using pointers, where each node is a separate heap allocation. While flexible, this is often disastrous for cache performance.

When you traverse a linked list, you follow a pointer from one node to the next. Since new Node() can return memory from anywhere in the heap, the nodes are likely scattered all over memory.

• Accessing node->value is a cache hit (assuming you just got the node).
• Accessing node->next->value is almost guaranteed to be a cache miss, because node->next points to a completely different memory location.

This is called pointer chasing.

A common scenario in C++ is having a std::vector<std::unique_ptr<MyObject>>. While the vector of pointers itself is contiguous, the MyObject instances they point to are scattered across the heap. Iterating through this vector and dereferencing each pointer to do work will cause a cache miss for almost every object.

Identifying the Pattern: Be suspicious of code that iterates through a collection of pointers and dereferences them to access data. This applies to std::list, std::map, and collections of smart pointers like std::unique_ptr or std::shared_ptr. The more cache-friendly alternative is often a flat std::vector of objects.

Pattern 3: Inefficient Data Layout (Hot/Cold Splitting & AoS vs. SoA)

Even if your data is in a contiguous array, you can still have cache-unfriendly patterns. Consider an array of structs or classes. If each object contains a mix of data—some fields accessed frequently ("hot") and others rarely ("cold")—you are wasting precious cache space.

Every time you access a hot field, the entire object (or at least the part that fits in a cache line) is loaded. The cold data comes along for the ride, occupying cache space but never being used.

This idea can be taken further into a design paradigm known as Data-Oriented Design, which often contrasts two layouts:

• Array of Structures (AoS): The typical object-oriented approach. std::vector<Person>, where struct Person { std::string name; int age; };. This is cache-unfriendly if your loop only needs the age.
• Structure of Arrays (SoA): A data-oriented approach. struct People { std::vector<std::string> names; std::vector<int> ages; };. If your loop only needs ages, it can now iterate through a tightly packed, contiguous array of integers, which is extremely cache-friendly.

Identifying the Pattern: Look for loops that process an array of large objects but only touch one or two small fields within each object. This is a sign that your data layout is inefficient. The hot and cold data are mixed, polluting the cache.

Pattern 4: False Sharing

This last pattern is specific to multithreaded programming, but it is so important and counter-intuitive that we must cover it now. It will be critical for the parallel programming modules to come.

False sharing occurs when:

1. Multiple threads are running on different CPU cores.
2. They access and modify logically independent variables.
3. These variables happen to reside on the same cache line.

When Thread 1 on Core 1 modifies its variable, the cache coherency protocol invalidates the entire cache line for all other cores. When Thread 2 on Core 2 then tries to access its own independent variable, it triggers a cache miss because its copy of the cache line was invalidated. The line has to be fetched again. This back-and-forth invalidation can destroy performance, even though the threads are not sharing any data in the program's logic.

Identifying the Pattern: In a multi-threaded C++ program, look for an array where different threads write to different indices (e.g., results[thread_id] = ...). If the elements of the array are small (like int or double), multiple elements will fit on a single 64-byte cache line. If thread_id 0 and 1 are working on adjacent elements, they are very likely to be causing false sharing.

Conclusion

Today we demystified the connection between your C++ code and the hardware's cache performance. You are now equipped to look at code not just for its logical correctness, but also for its mechanical sympathy with the underlying hardware.

Key Takeaways:

• Data Locality is King: The primary goal is to arrange data contiguously in the order it will be processed to maximize the use of every cache line.
• Common Unfriendly Patterns:
  1. Strided Access: Accessing multi-dimensional arrays in a non-contiguous order (e.g., column-wise in C++).
  2. Pointer Chasing: Traversing data structures like linked lists or trees of heap-allocated objects.
  3. Inefficient Layouts: Mixing frequently accessed ("hot") and rarely accessed ("cold") data in the same object, leading to wasted cache space.
  4. False Sharing: When independent variables used by different threads happen to fall on the same cache line, causing constant invalidations.

Understanding these patterns is the first and most crucial step toward writing high-performance code.

Preview of the Next Lesson

This lesson concludes our module on the fundamentals of computer organization and memory. You now understand how the CPU executes instructions and how the memory hierarchy impacts performance.

In our next module, "Single-Core Performance Optimization," we will put this knowledge into action. The first lesson will introduce you to profiling C++ code to identify performance bottlenecks. You will learn how to use tools that can pinpoint exactly where your program is spending its time—and which functions are causing the most cache misses—so you can apply the optimization techniques you will learn next.