The core underneath: latency, throughput, caches

Instruction counts predict performance badly. Two loops with the same number of instructions can differ by 4× because of how the instructions depend on each other, and a loop with fewer instructions can be 50× slower because of where its data lives. This skill builds the mental model of a modern out-of-order core (Zen 3 here, but Intel cores are the same in outline) that lets you predict which.

1. The pipeline

• x86 instructions are decoded into uops (micro-operations). Most simple instructions are one uop; add rax, [rdi] is a load uop plus an add uop (usually "fused" through the front end).
• The scheduler sends each uop to an execution port as soon as its inputs are ready — not in program order. Up to ~6 uops start per cycle.
• Retirement happens in program order, so the program appears sequential.

The consequence: the core is limited by whichever runs out first — the front end's issue width, the number of ports that can execute a given uop type, or the chain of dependencies between uops.

2. Latency versus throughput

Latency is how long until the result can be used. Throughput is how often a new one can start. When every iteration needs the previous iteration's result — a loop-carried dependency — you pay latency; when iterations are independent, you approach throughput.

Summing doubles is the textbook case:

double sum(const double* a, long n) {
    double s = 0;
    for (long i = 0; i < n; ++i) s += a[i];   // each add waits for the previous one
    return s;
}

Every addsd depends on the previous s: 3 cycles per element, while the FP units could start two adds every cycle. The fix is multiple accumulators — independent chains the scheduler can overlap:

#include <algorithm>
#include <chrono>
#include <cstdio>
#include <vector>

[[gnu::noinline]] double sum1(const double* a, long n) {
    double s = 0;
    for (long i = 0; i < n; ++i) s += a[i];
    return s;
}

[[gnu::noinline]] double sum4(const double* a, long n) {
    double s0 = 0, s1 = 0, s2 = 0, s3 = 0;
    long i = 0;
    for (; i + 4 <= n; i += 4) { s0 += a[i]; s1 += a[i + 1]; s2 += a[i + 2]; s3 += a[i + 3]; }
    for (; i < n; ++i) s0 += a[i];
    return (s0 + s1) + (s2 + s3);
}

template <class F> double best_ms(F f) {
    double best = 1e9;
    for (int rep = 0; rep < 15; ++rep) {
        auto t0 = std::chrono::steady_clock::now();
        volatile double r = f();
        (void)r;
        best = std::min(best, std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0).count());
    }
    return best;
}

int main() {
    std::vector<double> v(1 << 14, 1.5);  // 128 KiB: stays in L2
    double one = best_ms([&] { return sum1(v.data(), static_cast<long>(v.size())); });
    double four = best_ms([&] { return sum4(v.data(), static_cast<long>(v.size())); });
    std::printf("one chain: %.3f ms   four chains: %.3f ms   (%.1fx)\n", one, four, one / four);
}

About 4× on this machine. Why doesn't the compiler do it for you? Floating point addition is not associative — (a + b) + c can differ from a + (b + c) in the last bit — so reordering the sum changes the result, and the compiler won't do that without -ffast-math (or -fassociative-math). Integer sums are associative, so for long the compiler splits the chain itself. Notice also that GCC turned the four scalar chains into two addpd chains: independent accumulators are exactly what vectorisation needs.

3. Asking llvm-mca

llvm-mca simulates a CPU model over a block of instructions and reports throughput, the port pressure and a cycle-by-cycle timeline. The explorer's Analyze pane runs it on a function (or on a region you mark):

extern "C" double sum1(const double* a, long n) {
    double s = 0;
    for (long i = 0; i < n; ++i) {
        asm volatile("# LLVM-MCA-BEGIN loop-body");
        s += a[i];
        asm volatile("# LLVM-MCA-END");
    }
    return s;
}

For that region on -mcpu=znver3:

Iterations:        100
Instructions:      100
Total Cycles:      310
IPC:               0.32
Block RThroughput: 0.5

Block RThroughput 0.5 says the resources could run one iteration every half cycle; 310 cycles for 100 iterations says the real limit is ~3 cycles per iteration — the addsd latency, because each iteration waits for the last. Whenever total cycles per iteration ≫ RThroughput, look for a dependency chain. (llvm-mca assumes every load hits L1 and every branch is predicted; it says nothing about cache misses.)

4. Caches and cache lines

Memory moves in 64-byte cache lines. Touching one byte brings in the whole line, so:

• Sequential access is cheap: one miss per 64 bytes, and the hardware prefetcher recognises the stream and fetches ahead.

• Strided or random access is expensive: every access can miss. A linked list or a pointer chase can't be prefetched, because the next address isn't known until the current load finishes — that's a latency chain through memory.

• Row-major vs column-major traversal of a 2D array is the classic example: same instructions, same count, often 10× different time.

• Power-of-two strides fight associativity. A line's address picks its set; only that set's few ways can hold it. Zen 3's L1d has 64 sets × 8 ways of 64-byte lines, so addresses 4 KiB apart all land in the same set: walk nine rows of a 1024-int matrix down one column and you thrash 8 ways while the other 63 sets sit empty.

The same effect in miniature — a toy cache with 4 sets × 2 ways of 16-byte lines, where "4 KiB apart" becomes "64 bytes apart":

__builtin_prefetch(p) can help for irregular but computable access patterns (you know the address several iterations ahead). For sequential access the hardware already does it.

5. False sharing

Cache coherence works on whole lines. If two cores write to different variables that live in the same line, the line bounces between their caches on every write, even though there is no logical sharing:

#include <atomic>
#include <chrono>
#include <cstdio>
#include <thread>

struct Packed { std::atomic<long> a{0}, b{0}; };                           // one line
struct Padded { alignas(64) std::atomic<long> a{0}; alignas(64) std::atomic<long> b{0}; };  // two

template <class Counters> double run_ms() {
    Counters c;
    auto t0 = std::chrono::steady_clock::now();
    std::thread t1([&] { for (int i = 0; i < 5'000'000; ++i) c.a.fetch_add(1, std::memory_order_relaxed); });
    std::thread t2([&] { for (int i = 0; i < 5'000'000; ++i) c.b.fetch_add(1, std::memory_order_relaxed); });
    t1.join();
    t2.join();
    return std::chrono::duration<double, std::milli>(std::chrono::steady_clock::now() - t0).count();
}

int main() {
    std::printf("sizeof Packed %zu, Padded %zu\n", sizeof(Packed), sizeof(Padded));
    double packed = run_ms<Packed>(), padded = run_ms<Padded>();
    std::printf("same cache line: %.0f ms   separate lines: %.0f ms\n", packed, padded);
}

Typically 5–10× apart. The fix is layout: give each thread's hot data its own line — alignas(64) (or alignas(std::hardware_destructive_interference_size)), or accumulate in a local variable and write the shared slot once at the end. Each fetch_add here is a lock add instruction: atomic read-modify-writes need exclusive ownership of the line, which is what makes the bouncing so expensive.

6. Store forwarding

A store sits in the store buffer before it reaches L1. A later load from the same address can be served straight from the store buffer — store forwarding, about as fast as an L1 hit. It works when the load reads the same bytes the store wrote (or a subset, suitably aligned). It fails — the load waits for the store to commit, ~10+ cycles — when the load is wider than the store or straddles two stores:

void stall(char* p, long* out) {
    *reinterpret_cast<int*>(p) = 1;        // 4-byte store
    *out = *reinterpret_cast<long*>(p);    // 8-byte load of the same address: forwarding fails
}

(That snippet also breaks strict aliasing — the kind of code where this happens is type-punning through memory. Use std::bit_cast on values.)

7. Branch misprediction, once more

A mispredicted branch costs roughly the length of the pipeline: ~15–20 cycles on Zen 3. In throughput terms that's 60–100 simple instructions not executed. The branchless skill has the details; here it's another entry in the "what costs how much" table:

8. Measuring cycles, and why microbenchmarks lie

rdtsc reads the time-stamp counter. On every recent x86 CPU it ticks at a constant rate (the nominal frequency), not the current core clock — so it measures time, not core cycles. It isn't serializing either: the CPU may execute it before earlier instructions finish (lfence; rdtsc or rdtscp fix the ordering). For most purposes std::chrono::steady_clock is just as good and portable; use perf stat for real cycle and cache-miss counts.

A microbenchmark that loops over the same small input measures a best case that production rarely sees:

• the data is hot in L1, the prefetcher is warmed up;
• the branch predictor has learned the input;
• the compiler may have hoisted or deleted work (use the result, vary the input);
• frequency scaling and other processes move the numbers between runs.

Measure at realistic sizes, with realistic data, both versions in the same session, and look at the distribution, not one number.