Portfolio | The 3 Cs of memory bound

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:

cpp

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;
}

sum_cols is 6.15x slower (985 ms vs 160 ms), 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 before measuring: a measurement you couldn't predict 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. Overlap it (prefetching, post 4) or touch fewer bytes.

Capacity. The working set between two touches of a line exceeds the cache, so it 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. Vanishes 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.

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 threecs

Two build warnings before you trust anything:

Use -O2 and read the disassembly. At -O3, GCC's -floop-interchange may quietly rewrite sum_cols into sum_rows, destroying the experiment. Check with objdump -d.
GCC >= 12 auto-vectorizes at -O2; sum_rows may vectorize while sum_cols won't, inflating the gap for compute reasons. For the purist version add -fno-tree-vectorize -fno-unroll-loops and confirm equal instruction counts.

Measurement hygiene: fix the clock and pin the core, or every number is garbage.

bash

sudo cpupower frequency-set -g performance
echo 1 | sudo tee /sys/devices/system/cpu/intel_pstate/no_turbo
taskset -c 2 ./threecs sweep

Run each experiment 5+ times, report the median, state CPU model, cache geometry, kernel. Two confounders: transparent huge pages change the sweep's tail (post 3); hardware prefetchers rescue the sequential experiments (disable via Intel MSR 0x1a4 on a machine you own and will reboot).

04Reading the counters

bash

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 rows

Predict before you measure, from your lscpu -C numbers:

rows vs cols. For rows, one line serves 8 sequential doubles, so 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 page, miss ratio approaches 1, 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): 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 and land in one set:

bash

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 again

The 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 cache size would help; 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.)

cols was really this: kN = 4096 doubles is a 32 KiB row pitch, a power-of-two stride. The hook is a conflict-and-capacity cocktail, typical of real slow loops. Re-run with kN = 4104 to see how much damage was the power-of-two.

When aggregate counters aren't enough: cachegrind attributes misses to source lines (attribution, never magnitudes; simulates no prefetching); perf mem samples real loads with latencies and data sources; 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's finished: the ceiling is the memory bus, not the ALUs. The honest ending for a memory-bound kernel: you don't make it fast, you make it hit the wall squarely and stop.

06What's next

Of the three C's, the conflict miss deserves special contempt: nobody chooses it. It arrives silently through a power-of-two dimension, an allocator's alignment, or (next post) a struct putting two threads' data on one cache line. That's the fourth C, coherence, and the fix is spelled alignas.