Cache Coherency and Performance

Modern CPUs are incredibly fast, but main memory (RAM) is much slower. This speed difference creates a bottleneck.

CPU caches are small, super-fast memory areas located directly on the CPU chip. They act as temporary storage for frequently accessed data and instructions, bridging the speed gap between the CPU and RAM.

Caches are organized into a hierarchy, usually with three main levels:

• L1 Cache: Smallest (tens of KBs), fastest, located directly on each CPU core. Stores data and instructions the core needs right now.
• L2 Cache: Larger (hundreds of KBs), slower than L1, often per-core. Acts as a secondary buffer.
• L3 Cache: Largest (several MBs), slowest, but faster than RAM. Shared across all CPU cores on the chip.

Data isn't moved to and from the cache one byte at a time. Instead, it's moved in fixed-size blocks called cache lines. A typical cache line size is 64 bytes.

When the CPU requests data, an entire cache line containing that data is fetched from the next memory level. This is crucial for performance because it anticipates future data needs.

When the CPU needs data:

• Cache Hit: If the data is found in a cache, it's a "hit." This is extremely fast, as the CPU can access it immediately.
• Cache Miss: If the data is not in the cache, it's a "miss." The CPU must fetch the data from the next slower memory level (L2, L3, or main RAM), which causes a significant delay.

Our goal in optimizing assembly code is to maximize cache hits.

Spatial locality means that if a program accesses a memory location, it's likely to access nearby memory locations soon after. Think of it as "data you need is often next to data you just used."

Cache lines are designed to exploit this. When you load one byte, the entire 64-byte line is brought in, making subsequent accesses to adjacent bytes very fast (cache hits).

Temporal locality means that if a program accesses a memory location, it's likely to access that same location again in the near future. Think of it as "data you used recently, you'll probably use again soon."

Caches keep recently used data closer to the CPU, making repeated accesses to the same variables or instructions much faster.

As an assembly programmer, you can structure your code and data to improve cache locality:

• Data Layout: Arrange related data contiguously in memory (e.g., struct members, array elements).
• Access Patterns: Access data sequentially rather than jumping around memory.
• Loop Optimization: Process smaller chunks of data that fit entirely within the cache.

This minimizes cache misses and keeps the CPU busy with useful work.

In a multi-core CPU, each core has its own L1 and L2 caches. What happens if Core 0 modifies a variable, but Core 1 has an older copy of that variable in its own cache?

Cache coherency ensures that all cores have a consistent view of memory. When one core modifies a shared memory location, other cores' caches must be updated or invalidated to prevent stale data.

Cache coherency is typically maintained through hardware protocols, like the MESI protocol (Modified, Exclusive, Shared, Invalid).

When a core writes to a shared cache line, the protocol ensures that other cores' copies of that line are marked "Invalid." If another core then tries to read that data, it will incur a cache miss and fetch the updated version from the modifying core or main memory.

This overhead can impact performance in multi-threaded programs.

How you access multi-dimensional data can drastically affect cache performance. In systems like x86, memory for 2D arrays is typically laid out in a row-major fashion (all elements of the first row, then the second, etc.).

Consider this conceptual C-like example illustrating the principle:

// Good: Row-major traversal (spatial locality)
// Accesses elements contiguously in memory
for (int row = 0; row < ROWS; row++) {
  for (int col = 0; col < COLS; col++) {
    data[row][col]++;
  }
}

// Bad: Column-major traversal (poor spatial locality)
// Jumps across memory for each 'row' increment
for (int col = 0; col < COLS; col++) {
  for (int row = 0; row < ROWS; row++) {
    data[row][col]++;
  }
}

The row-major approach maximizes cache hits by efficiently using loaded cache lines.

Consider a loop that repeatedly accesses the same few variables within a tight code block.

We've explored how CPU caches (L1, L2, L3) bridge the speed gap with main memory. Data moves in cache lines, and maximizing cache hits through spatial and temporal locality is key to performance.

We also touched upon cache coherency, which ensures data consistency across multiple cores, though it can introduce synchronization overhead. Understanding these concepts helps you write more efficient low-level code.