关于locality对cache性能的重要性及程序优化方法的技术问询

Great question—cache locality is one of those underrated concepts that makes a huge difference in program performance once you get how it works. Let’s break this down clearly.

Why is locality critical for cache performance? #

Short answer: Yes, it all boils down to reducing cache misses—and those misses are a massive performance killer. Here’s the full picture:

CPUs rely on caches because they’re way faster than main memory (like 10-100x faster access time). But caches are tiny compared to RAM. When the CPU needs data, it first checks the cache:

• If it finds the data (a "hit"), it keeps chugging along at full speed.
• If it doesn’t (a "miss"), it has to wait for the data to be fetched from main memory, which stalls the CPU for dozens of clock cycles.

Locality solves this by aligning your program’s data access patterns with how caches work:

• Temporal locality: Data you’ve recently used is likely to be used again soon. Caches keep recently accessed data around, so reusing it avoids misses.
• Spatial locality: Data near the data you just accessed is likely to be used next. Caches load data in chunks called "cache lines" (usually 64 bytes). If you access data sequentially, the entire cache line gets used before you need to fetch the next one—no wasted cycles from partial line loads.

Without good locality, your CPU will spend most of its time waiting for memory instead of doing actual work.

How to write programs with good locality #

Here are practical, actionable tips to optimize your code’s cache behavior:

• Iterate arrays in order (row-major for most languages)
  Most languages (C, C++, Python, Java) store multi-dimensional arrays in row-major order—meaning all elements of a row are stored contiguously in memory. If you loop over columns first, you’ll jump around memory and trigger tons of cache misses.

  Bad example (C):

  // Jumps across columns—terrible spatial locality
  for (int j = 0; j < COLS; j++) {
      for (int i = 0; i < ROWS; i++) {
          sum += matrix[i][j];
      }
  }
  

  Good example:

  // Iterates row by row—uses cache lines efficiently
  for (int i = 0; i < ROWS; i++) {
      for (int j = 0; j < COLS; j++) {
          sum += matrix[i][j];
      }
  }
  

• Use contiguous data structures instead of linked lists
  Arrays, vectors, and arrays of structs store data in contiguous memory. Linked lists (and similar structures) scatter nodes all over RAM—each node access is a potential cache miss. If you need dynamic size, prefer a vector (which stays contiguous as it grows) over a linked list unless you have a specific reason not to.

• Group frequently used data together
  If your program often accesses certain variables or struct fields together, keep them close in memory. For example, put all the fields a function uses regularly into a single struct—this way, when you load one field into cache, the others come along for free in the same cache line.

• Use blocking (tiling) for large datasets
  When working with big matrices or arrays, split the data into smaller "blocks" that fit entirely into the CPU’s cache. For example, in matrix multiplication, instead of multiplying entire rows/columns at once, multiply 32x32 blocks (adjust based on your cache size). This keeps all the data you’re working on in cache, avoiding repeated misses.

• Reuse data before moving on
  If you need to perform multiple operations on the same set of data, do all those operations back-to-back instead of jumping between different data sets. This leverages temporal locality—your data stays in cache while you work on it.

内容的提问来源于stack exchange，提问作者Bab