Cache Thrashing: Load, Evict, Reload, Repeat
Two ways to make a cache useless: overflow it, or arrange for everything you touch to land in one set. Both produce the same signature — a performance cliff at a specific input size or stride, where the curve falls off rather than bending.
Software view, hardware view
The gap between what you wrote and what the machine does is where this whole domain lives.
Two different causes, one signature
Capacity thrashing is the straightforward one: the data you cycle through is larger than the level holds, so by the time you come back to the start it has been evicted. Every pass misses on everything. The fix is to make the hot set smaller — usually by processing in blocks so each block fits (Matrix Tiling: Same Arithmetic, Ten Times Faster).
Conflict thrashing is the surprising one, because the working set may be tiny. If the stride between successive accesses is a multiple of numSets × lineBytes, the index bits never change and every access targets one set. A set holds ways lines; touch ways + 1 addresses in a cycle and each one evicts the line you will need next. The other thousands of sets sit unused (Tag, Index and Offset: How an Address Finds Its Line).
They look identical from outside — high miss rate, low IPC, a hard cliff — which is why the diagnostic step is to change the stride and the size *independently*. If padding the stride by one line restores performance, it was conflict. If only shrinking the working set helps, it was capacity.
| Symptom | Capacity thrashing | Conflict thrashing |
|---|---|---|
| Working-set size | Larger than the level | Can be far smaller than the level |
| Trigger | Crossing a size threshold | A stride that preserves index bits |
| Effect of padding a row by one line | Little or none | Often removes it entirely |
| Effect of blocking the traversal | Removes it — that is the fix | Usually helps too, by shrinking the hot set |
| Cache occupancy during the failure | Full, and churning | Mostly idle, one set churning |
| Typical setting | Any large sequential or repeated pass | Power-of-two dimensions, column-major walks |
The stride that kills, and the padding that saves
The classic reproduction is a column-wise walk over a row-major matrix whose row length is a power of two. Consecutive accesses are one full row apart. If that row length in bytes happens to be a multiple of the set span, every element of the column maps to the same set, and a column longer than the way count thrashes.
The fix is disproportionately small: extend each row by one cache line and the stride is no longer a multiple of the set span, so successive column elements walk across sets instead of piling into one. You waste a sliver of memory and the collision disappears. This is why numerical libraries pad leading dimensions rather than using the natural width.
It is worth being explicit that this is a *layout* fix and not an *algorithmic* one. The number of operations is unchanged; the number of memory transactions is not. That distinction is the entire reason Both Are O(n). One Is Far Slower. and Data-Oriented Design, Without the Dogma exist as topics, and it is invisible to complexity analysis.
1N = 1024 // row = 1024 * 8 bytes = 8 KiB2matrix = alloc(N * N * 8)3 4for col in 0 .. N-1:5 for row in 0 .. N-1:6 sum += matrix[row * N + col]7 8// stride between accesses = 8 KiB9// if that is a multiple of (sets x line),10// every element of the column lands in ONE set11// -> ways+1 hot lines -> evict, reload, repeat1N = 10242STRIDE = N + 8 // +8 doubles = +64 bytes = one line3matrix = alloc(N * STRIDE * 8)4 5for col in 0 .. N-1:6 for row in 0 .. N-1:7 sum += matrix[row * STRIDE + col]8 9// stride is no longer a multiple of the set span,10// so successive elements walk across sets11// -> the column stays residentIdentical arithmetic, identical asymptotic complexity, one extra line per row. The cliff is caused by the numeric relationship between the stride and the cache geometry, and perturbing the stride is enough to remove it.
A cliff, not a slope
The reason thrashing is so often misdiagnosed is the shape of the curve. Most performance problems degrade gradually — twice the data, roughly twice the time. Thrashing does not: performance is flat and good while the pattern fits, then falls sharply over a narrow range, then is flat and bad. Engineers reading a single data point on either side conclude the code is fine or the code is hopeless, and both are wrong.
This shape is also why "it was fast in the test" is such a common preface. A test harness with a small input sits on the good plateau; production sits past the cliff. Nothing about the code changed, and the profile shows time spread across the loop rather than concentrated anywhere actionable.
The practical habit is to sweep rather than sample. Measure across a range of sizes and strides and plot it. A cliff tells you it is a hierarchy effect and roughly where the boundary sits; a smooth slope points elsewhere entirely, toward Algorithmic Cost in a Request Handler or something outside the memory system.
Key points
- Thrashing has two distinct causes — exceeding capacity, and a stride that maps everything into one set.
- Conflict thrashing can occur with a working set far smaller than the cache, while most of the cache sits idle.
- The signature is a cliff rather than a slope: flat and fast, a narrow collapse, then flat and slow.
- Padding a row or allocation by one cache line often removes conflict thrashing entirely.
- Distinguish the two by changing stride and size independently — the one that restores performance names the cause.
Follow the mechanism
The path through the machine, hop by hop — and the conclusions it invites that are wrong.
- 1Loop → address stream: successive accesses are separated by a fixed stride.
- 2Stride → index bits: when the stride is a multiple of the set span, those bits are identical on every access.
- 3Index → one set: every access targets the same set, so only
wayslines of the whole cache are usable. - 4Set → eviction: touching more than
waysaddresses in a cycle evicts the line needed next, every time. - 5Eviction → refill: each iteration pays a miss to the next level, and the loop runs at memory speed rather than cache speed.
- • "The algorithm got slower" — the operation count is unchanged; the memory transaction count is what moved.
- • "We need a bigger cache" — for conflict thrashing a bigger cache may not help at all, since the collision is in the index bits.
- • "The profiler shows no hotspot, so this is not a memory problem" — a diffuse profile is exactly what uniformly slow accesses look like.
- • "It only happens at 1024, so it is a bug at that size" — 1024 is not special to the code; it is special to the geometry it happens to hit.
Consequences, controls and cost
- • Throughput drops by an order of magnitude at a specific input size or matrix dimension, with no code change.
- • Profiles look diffuse — time is spread across the loop rather than pointing at one call — because every access is slow.
- • Small, apparently cosmetic changes (a padded row, a different allocation order) produce large, confusing swings.
- • Tests on small inputs pass comfortably while production sits on the far side of the cliff.
- • Block or tile the traversal so the set that is hot at any moment fits comfortably in the level ([[matrix-tiling]], [[cache-aware-algorithms]]).
- • Pad leading dimensions to non-power-of-two widths so strides stop being multiples of the set span.
- • Traverse in the layout order of the data — row-major data walked row-wise avoids the problem instead of mitigating it.
- • Sweep size and stride when benchmarking so a cliff is visible, rather than sampling one convenient input.
- • Sweep the input size across a wide range and plot time per element; a cliff localises the capacity boundary.
- • Sweep stride independently at fixed working-set size; spikes at power-of-two strides indicate conflict rather than capacity.
- • Read miss counters per level to see which boundary is being crossed ([[performance-counters]], [[cpu-bound-vs-memory-bound]]).
- • Apply the one-line padding experiment: if it recovers performance, the cause was conflict, and you have your answer in minutes.
- • Padding wastes memory and may itself push a marginal working set over a capacity threshold.
- • Blocked traversals complicate loop structure and index arithmetic, which costs readability and invites off-by-one bugs.
- • Tuning block sizes to one machine's geometry produces code that is merely acceptable on others.
Scope
§224 — what these claims are specific to.
- MICROARCH-SPECIFICWhich strides conflict depends on set count, line size and index hashing, all of which vary by level and machine. The padding remedy generalises; the specific bad numbers do not.
- SIMULATEDThe relative costs shown are illustrative ratios from a model, not measurements. Real ratios depend on which level is missed and what the next level costs on that machine.