Cache Lines, False Sharing, and Cache-Oblivious Algorithms in Practice

Modern CPU cores operate orders of magnitude faster than main memory (DRAM). While an instruction retirement cycle in an ALU takes a fraction of a nanosecond, fetching a cache line from DRAM routinely costs 60 to 80 nanoseconds—equivalent to hundreds of wasted execution cycles.

To mask this divergence, modern microarchitectures implement hierarchical caching subsystems: L1 data cache (typically 32–48 KB, ~4 cycles), L2 cache (512 KB–1 MB, ~14 cycles), and unified L3 cache (up to 32+ MB, ~40–60 cycles).

Engineering software that scales under heavy multicore workloads requires understanding that memory is not a uniform byte-addressable flatland; it is transferred exclusively in quantized blocks known as cache lines (standardized at 64 bytes on modern x86-64 and AArch64 architectures).

The Mechanics of Cache Lines

When a thread dereferences an 8-byte pointer, the memory controller does not fetch 8 bytes. It fetches the enclosing 64-byte aligned boundary:

[ Address: 0x1000 ... 0x103F ] -> 64-byte Cache Line
  +-------+-------+-------+-------+-------+-------+-------+-------+
  | Byte0 | Byte1 |  ...  |       |       |       |       | Byte63|
  +-------+-------+-------+-------+-------+-------+-------+-------+

Spatial locality is the natural beneficiary: sequential array iterations (for (size_t i = 0; i < N; ++i)) amortize the initial DRAM miss across subsequent elements residing in the pre-fetched line. Conversely, pointer-chasing structures such as naive linked lists or uncoalesced binary trees evict neighboring lines with nearly zero reuse factor, degrading throughput by an order of magnitude.

In multi-threaded concurrent pipelines, cache lines introduce a notorious synchronization hazard: false sharing.

False sharing occurs when two independent threads running on separate physical cores write to completely unrelated variables that happen to share the same 64-byte cache line.

// ANTI-PATTERN: Structural False Sharing
struct ThreadWorkerStats {
    uint64_t worker_1_ops; // 8 bytes (Offset 0x00)
    uint64_t worker_2_ops; // 8 bytes (Offset 0x08)
    // Both variables reside on the same 64-byte cache line!
};

Even though Core A only mutates worker_1_ops and Core B only mutates worker_2_ops, the cache coherency protocol (such as MESI or MOESI) mandates that any store instruction transitions the entire 64-byte line into the Modified state.

Core B’s L1 cache line is promptly invalidated via bus snooping, forcing Core B to flush its pipeline and reload the line from L3 or main memory. The cores spend more cycles bouncing the cache line across the interconnect fabric than doing arithmetic.

In modern C++ (C++17 onwards), we enforce explicit isolation using std::hardware_destructive_interference_size:

#include <new>
#include <cstdint>

struct alignas(std::hardware_destructive_interference_size) IsolatedCounter {
    uint64_t operations{0};
};

struct MultiThreadedEngine {
    IsolatedCounter worker_counters[MAX_THREADS];
};

By guaranteeing that each worker counter occupies its own independent 64-byte cache line, inter-core coherency traffic drops to zero, restoring linear scalability with core count.

Cache-Oblivious Matrix Transposition

Traditional performance tuning often requires hardcoding tile sizes tuned to specific L1/L2 cache sizes. Cache-oblivious algorithms, pioneered by Frigo, Leiserson, Prokop, and Ramachandran at MIT, solve this problem by leveraging recursive divide-and-conquer strategies that are optimal across all cache hierarchies simultaneously without tuning parameters.

Consider matrix transposition $B = A^T$:

void transpose_cache_oblivious(
    const double* A, double* B,
    size_t row_start, size_t row_end,
    size_t col_start, size_t col_end,
    size_t lda, size_t ldb
) {
    size_t n_rows = row_end - row_start;
    size_t n_cols = col_end - col_start;

    // Base case: small enough to reside in L1
    if (n_rows <= 16 && n_cols <= 16) {
        for (size_t i = row_start; i < row_end; ++i) {
            for (size_t j = col_start; j < col_end; ++j) {
                B[j * ldb + i] = A[i * lda + j];
            }
        }
        return;
    }

    // Split along the larger dimension
    if (n_rows >= n_cols) {
        size_t mid = row_start + n_rows / 2;
        transpose_cache_oblivious(A, B, row_start, mid, col_start, col_end, lda, ldb);
        transpose_cache_oblivious(A, B, mid, row_end, col_start, col_end, lda, ldb);
    } else {
        size_t mid = col_start + n_cols / 2;
        transpose_cache_oblivious(A, B, row_start, row_end, col_start, mid, lda, ldb);
        transpose_cache_oblivious(A, B, row_start, row_end, mid, col_end, lda, ldb);
    }
}

Because the recursion naturally divides matrices until sub-problems fit cleanly within each tier of the memory hierarchy, the algorithm exhibits asymptotically optimal cache transfers across L1, L2, L3, and even TLB pages.

Conclusion

High-throughput systems programming is fundamentally an exercise in mechanical sympathy. The programmer who visualizes the physical silicon—the latency penalties of interconnect buses, the 64-byte cache line quantum, and the cost of branch mispredictions—writes software that executes with effortless speed.

The Mechanics of Cache Lines

The Silent Bottleneck: False Sharing

Eliminating False Sharing via Explicit Alignment

Cache-Oblivious Matrix Transposition

Conclusion