Two loops, identical work, wildly different runtimes: a field guide to the three kinds of cache miss (compulsory, capacity, conflict) with a benchmark rig to provoke each one and the perf incantations to tell them apart.
Two functions read the same 128 MiB, execute comparable instruction counts, and compute the same sum:
constexpr std::size_t kN = 4096; // 4096 x 4096 doubles = 128 MiB
double sum_rows(const double *m) { // walk along rows
double s = 0.0;
for (std::size_t i = 0; i < kN; ++i)
for (std::size_t j = 0; j < kN; ++j)
s += m[i * kN + j];
return s;
}
double sum_cols(const double *m) { // walk along columns
double s = 0.0;
for (std::size_t i = 0; i < kN; ++i)
for (std::size_t j = 0; j < kN; ++j)
s += m[j * kN + i];
return s;
}On my machine sum_cols is 6.15x slower (985 ms vs 160 ms) while burning 8.4x more cycles for 1.56x the instructions. IPC drops from 0.56 to 0.11: the CPU spends most of sum_cols waiting.
The taxonomy is due to Mark Hill (1989): every miss is compulsory, capacity, or conflict. (A fourth C, coherence, was added later for multiprocessors (next post).
01The machine under the loop
Four facts are enough:
- Memory moves in 64-byte cache lines. One line holds 8 doubles; touch one byte, pay for 64.
- The hierarchy is L1d -> L2 -> L3 -> DRAM, roughly 4-5, 12-16, 40-60, and hundreds of cycles load-to-use. The rig below measures yours.
- Caches are set-associative: middle address bits select a set, each set holds W lines (typically 8-16). Addresses that agree on those bits compete for the same W slots regardless of total cache size. That's the entire conflict-miss story.
- Replacement within a set is approximately LRU.
Get your geometry first: lscpu -C (size, ways, sets, line size) and lstopo-no-graphics (which cores share L2/L3). Predict counter values from these numbers before measuring: a measurement you couldn't have predicted is one you don't understand.
02The taxonomy
Compulsory (cold). First touch of a line, ever. No cache avoids it. Lower bound: bytes touched / 64. You can only overlap it (prefetching, post 4) or touch fewer bytes.
Capacity. The working set between two touches of a line exceeds the cache, so the line was evicted. A fully associative cache of the same size would still miss. Cure: shrink the reuse distance (tiling, fusion, cache-sized chunks).
Conflict. The cache is big enough but the set isn't: more than W hot lines map to the same index bits and evict each other while the rest of the cache sits idle. Would vanish under full associativity. Almost always self-inflicted: power-of-two strides and dimensions, allocator alignment. Cure: break the stride (pad, skew, offset).
Hill's definitions are operational: each C is defined by the hypothetical cache that would have avoided it:
| C | Bigger cache helps? | More ways help? | Cure |
|---|---|---|---|
| Compulsory | no | no | prefetch, touch fewer bytes |
| Capacity | yes | no | tiling, fusion |
| Conflict | no | yes | padding, de-power-of-two-ing |
03The rig
One file, four experiments: threecs.cpp.
#include <immintrin.h>
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <random>
#include <string>
#include <vector>
template <class T>
static inline void do_not_optimize(T const &v) {
asm volatile("" : : "r,m"(v) : "memory");
}
static double now_s() {
return std::chrono::duration<double>(
std::chrono::steady_clock::now().time_since_epoch()).count();
}
// ---------------------------------------------------------------- hook ----
constexpr std::size_t kN = 4096; // 4096^2 doubles = 128 MiB
static double sum_rows(const double *m) {
double s = 0.0;
for (std::size_t i = 0; i < kN; ++i)
for (std::size_t j = 0; j < kN; ++j) s += m[i * kN + j];
return s;
}
static double sum_cols(const double *m) {
double s = 0.0;
for (std::size_t i = 0; i < kN; ++i)
for (std::size_t j = 0; j < kN; ++j) s += m[j * kN + i];
return s;
}
static void run_matrix(bool rows) {
double *m = static_cast<double *>(std::aligned_alloc(4096, kN * kN * 8));
std::memset(m, 0, kN * kN * 8); // pre-fault, keep page faults out of the timing
double t0 = now_s();
double s = rows ? sum_rows(m) : sum_cols(m);
double t1 = now_s();
do_not_optimize(s);
std::printf("%s: %.3f s (%.2f ns/element)\n", rows ? "rows" : "cols",
t1 - t0, (t1 - t0) / double(kN * kN) * 1e9);
std::free(m);
}
// ------------------------------------------------- capacity: the sweep ----
// Pointer chase through a random cycle of line-sized nodes. Each load
// depends on the last, so misses can't overlap: ns/step = load-to-use
// latency. Random order defeats the stride prefetcher.
struct alignas(64) Node {
std::uint64_t next;
std::uint64_t pad[7];
};
static double chase_ns(std::size_t bytes, std::size_t steps) {
const std::size_t n = bytes / sizeof(Node);
std::vector<Node> nodes(n);
std::vector<std::uint64_t> order(n);
for (std::size_t i = 0; i < n; ++i) order[i] = i;
std::mt19937_64 rng(42);
std::shuffle(order.begin(), order.end(), rng);
for (std::size_t i = 0; i < n; ++i)
nodes[order[i]].next = order[(i + 1) % n];
std::uint64_t idx = order[0];
for (std::size_t s = 0; s < n; ++s) idx = nodes[idx].next; // warm up
double t0 = now_s();
for (std::size_t s = 0; s < steps; ++s) idx = nodes[idx].next;
double t1 = now_s();
do_not_optimize(idx);
return (t1 - t0) / double(steps) * 1e9;
}
static void run_sweep() {
std::printf("%12s %10s\n", "working set", "ns/load");
for (std::size_t kib = 16; kib <= 512 * 1024; kib *= 2)
std::printf("%9zu KiB %10.2f\n", kib, chase_ns(kib * 1024, 20'000'000));
}
// -------------------------------------------- compulsory: cold vs warm ----
// clflush everything, then sweep: one true cold miss per line, no page
// faults. Warm passes are the control.
static void run_cold(std::size_t mib) {
const std::size_t bytes = mib << 20;
char *p = static_cast<char *>(std::aligned_alloc(4096, bytes));
std::memset(p, 1, bytes);
for (int pass = 0; pass < 4; ++pass) {
if (pass == 0 || pass == 2) {
for (std::size_t i = 0; i < bytes; i += 64) _mm_clflush(p + i);
_mm_mfence();
}
std::uint64_t a = 0;
double t0 = now_s();
for (std::size_t i = 0; i < bytes; i += 64) a += std::uint8_t(p[i]);
double t1 = now_s();
do_not_optimize(a);
std::printf("pass %d (%s): %6.2f ns/line\n", pass,
(pass == 0 || pass == 2) ? "cold" : "warm",
(t1 - t0) / double(bytes / 64) * 1e9);
}
std::free(p);
}
// ------------------------------------------------ conflict: set thrash ----
// Hammer <lines> lines <stride> bytes apart. Stride = cache size / ways
// puts them all in ONE set: past the associativity, every access misses
// on a few-KiB footprint.
static void run_conflict(std::size_t lines, std::size_t stride,
std::size_t reps) {
char *base =
static_cast<char *>(std::aligned_alloc(4096, lines * stride + 64));
std::memset(base, 1, lines * stride + 64);
std::uint64_t a = 0;
double t0 = now_s();
for (std::size_t r = 0; r < reps; ++r)
for (std::size_t k = 0; k < lines; ++k)
a += *reinterpret_cast<const std::uint64_t *>(base + k * stride);
double t1 = now_s();
do_not_optimize(a);
std::printf("%zu lines @ stride %zu: %.2f ns/access (footprint %.1f KiB)\n",
lines, stride, (t1 - t0) / double(reps * lines) * 1e9,
double(lines * 64) / 1024.0);
std::free(base);
}
int main(int argc, char **argv) {
std::string mode = argc > 1 ? argv[1] : "";
if (mode == "rows") run_matrix(true);
else if (mode == "cols") run_matrix(false);
else if (mode == "sweep") run_sweep();
else if (mode == "cold") run_cold(argc > 2 ? std::atoi(argv[2]) : 8);
else if (mode == "conflict")
run_conflict(argc > 2 ? std::atoi(argv[2]) : 16,
argc > 3 ? std::atoi(argv[3]) : 4096, 5'000'000);
else
std::fprintf(stderr,
"usage: %s rows|cols|sweep|cold [MiB]|conflict [lines] [stride]\n",
argv[0]);
return 0;
}Build: g++ -O2 -std=c++20 -march=native threecs.cpp -o threecsTwo build warnings before you trust anything:
- Use
-O2and read the disassembly. At-O3, GCC's-floop-interchangemay quietly rewritesum_colsintosum_rows, destroying the experiment. Check withobjdump -d. - GCC >= 12 auto-vectorizes at
-O2;sum_rowsmay vectorize whilesum_colswon't, inflating the gap for compute reasons. For the purist version add-fno-tree-vectorize -fno-unroll-loopsand confirm equal instruction counts.
Measurement hygiene: fix the clock and pin the core, or every number is garbage.
sudo cpupower frequency-set -g performance
echo 1 | sudo tee /sys/devices/system/cpu/intel_pstate/no_turbo
taskset -c 2 ./threecs sweepRun each experiment at least 5 times, report the median, and state CPU model, cache geometry, and kernel. Two confounders: transparent huge pages change the sweep's tail (post 3), and hardware prefetchers rescue the sequential experiments (they can be disabled via Intel MSR 0x1a4 on a machine you own and will reboot).
04Reading the counters
perf stat -e task-clock,cycles,instructions,L1-dcache-loads,L1-dcache-load-misses,\
LLC-loads,LLC-load-misses,page-faults taskset -c 2 ./threecs rowsPredict before you measure, from your lscpu -C numbers:
rows vs cols. For rows, one line serves 8 sequential doubles, so the L1 miss ratio is at most 1/8 before prefetching kicks in. For cols, the stride is 32 KiB: every load lands on a fresh line and a fresh page, the miss ratio approaches 1, and IPC craters.
My counters:
| counter | rows | cols | ratio |
|---|---|---|---|
| cycles | 74.0M | 495.5M | 6.69x |
| IPC | 0.40 | 0.098 | 0.24x |
| L1 loads | 22.25M | 22.28M | 1.00x |
| L1 miss ratio | 18.95% | 85.35% | 4.50x |
sweep. Plot ns/load against working-set size (log2 x-axis). You should see a staircase: steps at your L1d, L2, and L3 sizes, plateaus at each level's latency, a final climb to DRAM.
cold. Flushed passes cost a DRAM fill per line; warm passes are ~10x cheaper. page-faults stays ~0: the memset pre-faulted, so this is the compulsory miss alone.
conflict. The star exhibit. On a 32 KiB / 8-way L1d, addresses 4096 bytes apart (32768 / 8) share the same index bits, so they all land in one set:
taskset -c 2 ./threecs conflict 8 4096 # 8 lines fit the 8 ways: hits
taskset -c 2 ./threecs conflict 16 4096 # 2x the ways: thrashes
taskset -c 2 ./threecs conflict 16 4160 # stride +64: hits againThe middle command shows a 1 KiB working set missing L1 on effectively every access, defeating a 32 KiB cache; the third fixes it by adding 64 bytes to the stride. No amount of cache size would help, and one line of padding cures it. (Caveat: L1 is virtually indexed, so virtual strides hit the sets you expect; repeating this at L2/L3 needs huge pages or luck.)
Note what cols really was: kN = 4096 doubles is a 32 KiB row pitch, a power-of-two stride. The hook is a conflict-and-capacity cocktail, which is typical of real slow loops. Re-run with kN = 4104 and see how much damage was the power-of-two.
When aggregate counters aren't enough: cachegrind attributes misses to source lines (use for attribution, never magnitudes; it simulates no prefetching); perf mem samples real loads with latencies and data sources; and top-down analysis (perf stat -M TopdownL1) settles whether you're memory-bound at all before you spelunk.
05The ceiling: know when you've won
The roofline model tells you when to stop. This kernel does one add per 8 bytes loaded (0.125 flop/byte), deep in the bandwidth-bound region. Once rows streams at your DRAM bandwidth (measure with STREAM), it is finished: the ceiling is the memory bus, not the ALUs. That's the honest ending for a memory-bound kernel: you don't make it fast, you make it hit the wall squarely and then stop.
06What's next
Of the three C's, the conflict miss deserves special contempt, because nobody chooses it. It arrives silently through a power-of-two dimension, an allocator's alignment, or (next post) a struct that puts two threads' data on one cache line. That's the fourth C, coherence, and the fix is spelled alignas.