CPU Caches and Locality
CPU cache behavior depends on what memory a workload touches, in what order, how it reuses that memory, and which cores read or modify it. Locality can reduce repeated data movement, while contention over shared cache lines can add work even when threads use different logical fields.
Start with the slow application operation and a representative baseline. Use profiles and supported hardware counters to investigate, then compare a specific layout or access change. A cache-miss count, source-level loop shape, or small simulator cannot by itself establish an application speedup or explain every memory stall.
TL;DR
- Cache behavior depends on what memory a workload touches, in what order, how it reuses it, and which cores share it.
- Good locality reduces repeated data movement; contention on shared cache lines (false sharing) adds work even when threads use different fields.
- Start from a slow application operation and a representative baseline, then profile with supported hardware counters.
- Change one layout or access pattern at a time and measure the application result.
- Miss counts, loop shapes, and small simulators explain behavior; they don't prove a speedup.
Quick Example
This Python program models an ideal fully associative LRU cache with invented dimensions: sixteen-byte lines, four-byte elements, and a configurable line capacity. It compares two orders over the same thirty-two indices. These are simulation counts, not characteristics measured from this computer.
At capacity four, sequential order produced 24 modeled hits and 8 misses; the strided order produced 0 hits and 32 misses. At capacity eight, the same strided order produced 24 hits and 8 misses.
The changed-capacity result is the useful counterexample: an access-order conclusion depends on the assumed working set and cache. This model excludes real associativity, replacement policies, prefetching, coherence, TLBs, NUMA, overlapping memory requests, and compiler transformations. No CPU timing, hardware counter, false-sharing event, or memory-stall measurement was collected.
Core Concepts
Spatial and temporal locality describe reuse opportunities
Spatial locality concerns nearby memory; temporal locality concerns reusing recently accessed memory. The model makes those ideas explicit by mapping neighboring fictional elements into the same line and retaining only a bounded set of lines. It helps explain an opportunity for reuse, not a guarantee about an actual processor.
Inspect the real representation before reasoning from a loop. A list of references and a contiguous array of numeric values do not imply the same memory layout. Likewise, source-level adjacency does not establish the final layout after compilation, allocation, and runtime behavior. Choose a representation suited to the operation, then verify its measured effect.
Working-set size changes the comparison
Identify the data actively needed by the operation, not only the total size of the application. A small reusable subset can behave differently from a stream that touches much more data once. Include metadata, indices, pointers, and frequently accessed neighboring fields in the investigation.
The simulator changes only capacity and obtains a different result for the same access sequence. A real experiment can also change with input size, concurrency, or the surrounding workload. Report the tested range and look for where a proposed improvement stops helping. Avoid converting one favorable data size into a universal layout rule.
False sharing concerns coherence, not just capacity
Linux's kernel documentation describes false sharing when multiple CPUs access data in the same cache line and at least one access writes, causing coherence-related interference even between logically distinct fields. It gives read/write as well as write/write examples. Mere shared read access is not the same condition. Linux false-sharing guide.
Locate the actual line and participating access sites before adding padding. Separating fields can help a demonstrated contention problem while increasing footprint or reducing useful locality elsewhere. A lock and its associated state may have different tradeoffs under different concurrency. Keep ownership and workload in the explanation.
The LRU example does not model coherence or multiple cores. Its misses cannot demonstrate false sharing. Treat false-sharing analysis as a separate experiment involving the real layout, threads, access modes, and target's available evidence.
A counter is evidence with a definition
The kernel guide describes using profiles, perf-c2c, and layout information such as pahole to locate cache-line contention. Those tools answer specific questions in supported environments; the existence of a generic event name does not guarantee identical semantics or availability on every processor. Linux detection guidance.
Record the CPU, operating system, profiler version, event definitions, sampling arrangement, and workload. Relate event counts to the operation's elapsed time and completed work. More misses can be harmless if other work overlaps them, while a dependency chain can make fewer expensive accesses consequential. The measured application outcome should decide whether a change is useful.
Best Practices
Establish a correct, representative baseline
Choose the operation that matters to users and verify its output. Capture input size, data distribution, concurrency, compiler/runtime, and relevant machine conditions. Warm and cold behavior can answer different questions; state which one the experiment represents.
Repeat measurements enough to understand their variability. Keep other changes controlled and retain the raw evidence needed to reproduce the comparison. A single short timing can reflect startup, background activity, or measurement noise rather than the proposed cache mechanism.
Change one mechanism deliberately
Evaluate traversal order, active working set, representation, or field ownership with a stated hypothesis. Keep the logical work equivalent. If a blocked traversal adds preprocessing or copying, include that cost in the end-to-end comparison.
Check representative small and large inputs, plus the intended thread count. An improvement that depends on fitting one working set into one cache can reverse outside that range. A favorable counter change without a useful application result is a lead for further investigation, not a completed optimization claim.
Separate true sharing from false sharing
If threads intentionally update the same logical state, padding cannot remove the coordination requirement. Revisit ownership, batching, synchronization, or the algorithm when appropriate. If they operate on independent state that happens to share a line, layout can be a relevant candidate. Verify the distinction from actual access evidence.
Common Mistakes
Assuming one cache-line size
Treating simulated misses as hardware measurements
Adding padding everywhere
Optimizing a loop that isn't the bottleneck
FAQ
Is sequential access always faster?
No universal result is established here. The outcome depends on representation, working set, dependencies, compiler behavior, hardware, and surrounding work. The model illustrates one mechanism and shows a capacity-dependent reversal.
Do more cache misses prove memory is the bottleneck?
No. Interpret the event definition and correlate it with completed work and elapsed time. Use a controlled change to test the proposed explanation rather than treating one counter as a verdict.
Does the example measure false sharing?
No. It is a single ideal-cache simulation with no cores or coherence. False sharing requires separate evidence about actual lines, concurrent accesses, and writes.