05_low_latency.cpp

// ============================================================================
// LESSON 05 — Low latency: measuring, memory, and mechanical sympathy
// ============================================================================
// Build & run:  make 05 && ./bin/05_low_latency
//
// !!! THE CARDINAL RULE: only benchmark optimised builds (-O2). A debug
// build (-O0) is 10-50x slower and lies about what production will do.
// Try it yourself: `make debug && ./bin/05_low_latency` after this.
//
// Latency in trading systems is rarely about clever algorithms. It's about:
//   1. MEMORY   — cache hits vs misses (100x difference per access)
//   2. ALLOCATION — never malloc on the hot path
//   3. BRANCHES — mispredicted branches stall the pipeline
// This lesson demonstrates #1 and #2 with real measurements on your machine.
// ============================================================================

#include <chrono>     // std::chrono — the timing library
#include <cstdint>
#include <iostream>
#include <list>
#include <numeric>    // std::iota
#include <random>
#include <vector>

// ---------------------------------------------------------------------------
// A minimal, honest benchmark harness.
//   - steady_clock: monotonic, never adjusted (system_clock can jump — NTP!)
//   - warm-up run first: first pass faults pages in and warms the caches
//   - many iterations, report per-op time
// Production systems use rdtsc/histograms and watch p99/p99.9, not the mean —
// in trading the TAIL is what kills you: the slow outlier IS the missed trade.
// ---------------------------------------------------------------------------
template <typename F>
double bench_ns(const char* name, int iters, F&& body) {
    body();                                            // warm-up (untimed)
    const auto t0 = std::chrono::steady_clock::now();
    for (int i = 0; i < iters; ++i) body();
    const auto t1 = std::chrono::steady_clock::now();
    const double ns =
        std::chrono::duration_cast<std::chrono::nanoseconds>(t1 - t0).count()
        / static_cast<double>(iters);
    std::cout << "  " << name << ": " << ns << " ns/iter\n";
    return ns;
}

// A sink the compiler can't see through — prevents it optimising the whole
// benchmark away because "the result is never used".
volatile std::int64_t g_sink;

int main() {
    std::cout << "=== 05 Low latency ===\n";
    constexpr int N = 100'000;

    // =========================================================================
    // EXPERIMENT 1 — cache locality: vector vs list
    // =========================================================================
    // A vector's elements are CONTIGUOUS: walking it streams through memory
    // and the prefetcher keeps the CPU fed. A list's nodes are scattered
    // heap allocations: every ->next is a potential cache miss (~100ns each,
    // vs ~1ns for L1). Same algorithm, same big-O — order-of-magnitude gap.
    // This is why trading code is vectors and flat arrays almost everywhere,
    // and why lesson 03's exercise 3 (array-based book) matters.
    std::vector<std::int64_t> vec(N);
    std::iota(vec.begin(), vec.end(), 0);        // fill 0,1,2,...
    std::list<std::int64_t> lst(vec.begin(), vec.end());

    std::cout << "sum " << N << " ints — contiguous vs pointer-chasing:\n";
    const double v = bench_ns("std::vector", 200, [&] {
        std::int64_t s = 0;
        for (std::int64_t x : vec) s += x;
        g_sink = s;
    });
    const double l = bench_ns("std::list  ", 200, [&] {
        std::int64_t s = 0;
        for (std::int64_t x : lst) s += x;
        g_sink = s;
    });
    std::cout << "  -> list is " << l / v << "x slower. Same O(n)!\n\n";

    // =========================================================================
    // EXPERIMENT 2 — allocation on the hot path: reserve() or pay
    // =========================================================================
    // push_back without reserve: the vector repeatedly outgrows its buffer,
    // and each growth = allocate bigger + copy everything + free old.
    // reserve() moves ALL of that off the hot path. In real systems the rule
    // is stronger: pre-allocate at startup, allocate NOTHING while trading.
    std::cout << "append " << N << " ints:\n";
    const double no_res = bench_ns("no reserve  ", 100, [&] {
        std::vector<std::int64_t> tmp;
        for (int i = 0; i < N; ++i) tmp.push_back(i);
        g_sink = tmp.back();
    });
    const double res = bench_ns("with reserve", 100, [&] {
        std::vector<std::int64_t> tmp;
        tmp.reserve(N);                          // one allocation, up front
        for (int i = 0; i < N; ++i) tmp.push_back(i);
        g_sink = tmp.back();
    });
    std::cout << "  -> reserve() is " << no_res / res << "x faster\n\n";

    // =========================================================================
    // EXPERIMENT 3 — branch prediction: sorted vs random condition
    // =========================================================================
    // The CPU guesses which way each `if` goes and speculates ahead. On
    // sorted data the guess is nearly always right; on random data it's a
    // coin flip and every miss flushes the pipeline (~15 cycles).
    // Hot trading loops are written branch-light for exactly this reason.
    //
    // TWIST: if you write this naively (`if (x < 50) s += x;`), clang at -O2
    // replaces the branch with a conditional-move/vector instruction and both
    // runs measure identical — the optimiser deleted the thing we wanted to
    // measure! That itself is half the lesson: ALWAYS check what the compiler
    // did (godbolt.org) before trusting a microbenchmark. The empty asm below
    // is an "optimisation barrier" that forces a real branch to survive.
    std::vector<std::int64_t> rnd(N);
    std::mt19937 gen(42);                        // seeded: reproducible runs
    std::uniform_int_distribution<std::int64_t> d(0, 99);
    for (auto& x : rnd) x = d(gen);
    std::vector<std::int64_t> sorted = rnd;
    std::sort(sorted.begin(), sorted.end());

    std::cout << "conditional sum (if x < 50), same data sorted vs shuffled:\n";
    auto cond_sum = [](const std::vector<std::int64_t>& xs) {
        std::int64_t s = 0;
        for (std::int64_t x : xs)
            if (x < 50) {
                s += x;
                asm volatile("" : "+r"(s));      // barrier: keep the branch real
            }
        g_sink = s;
    };
    const double bs = bench_ns("sorted   ", 200, [&] { cond_sum(sorted); });
    const double br = bench_ns("shuffled ", 200, [&] { cond_sum(rnd); });
    std::cout << "  -> mispredicted branches cost " << br / bs << "x\n\n";

    std::cout << "Now rebuild with `make debug` and rerun to see why we\n"
              << "never benchmark unoptimised builds.\n";
    return 0;
}

// ----------------------------------------------------------------------------
// EXERCISES
// 1. Change experiment 3's threshold from 50 to 0. The branch becomes
//    always-false — what happens to both times, and why?
// 2. Record every iteration's time of experiment 1 into a vector, sort it,
//    and print p50 / p99 / max. The tail tells a different story to the mean.
// 3. Delete the asm barrier and re-measure: the gap vanishes because the
//    compiler if-converts the branch. Paste the loop into godbolt.org with
//    -O2 and find the cmov/select instruction that replaced your `if`.
// FURTHER READING: "What every programmer should know about memory" (Drepper);
// Carl Cook's CppCon talk "When a Microsecond Is an Eternity" (the classic
// HFT C++ talk — watch it after this lesson, you'll recognise everything).
// ----------------------------------------------------------------------------