Your microseconds are not hiding in your arithmetic. They are hiding in memory — in which cache level holds the number you asked for, in how many bytes you copied to get it, and in whether you called the allocator on the way. This week installs a cost model in your head, and a measuring habit you will use for the next thirteen topics.
new on the hot path is a bug rather than merely slow.alignas(64)
Baseline your bot's on_book p99.9 this week
A benchmark without warm-up and a sink is not a result
A modern core issues several instructions per nanosecond and then waits. Everything interesting about performance is what it waits for. The ladder below is the whole model: each rung is roughly an order of magnitude, and your job all term is to keep the hot path on the top few rungs. Click a rung.
Representative figures for a ~3 GHz x86-64 server core. Your machine will differ by a factor of two; it will not differ by a factor of ten, and the ordering never changes.
C++ has value semantics: = means copy unless you say
otherwise, and a copy of a container is an allocation plus a memcpy. Step through the same six lines
twice — once with the function taking its argument by value, once by const& — and
watch the counters.
// AoS — array of structs. Hot and cold fields interleaved.
struct QuoteAoS {
double px; // 8 B <- the only field we scan
int qty; // 4 B
char venue[36]; // 36 B cold, dragged in anyway
}; // 48 B per element
// Scanning px touches 48 B per useful 8 B:
// one 64-byte line feeds 1.3 prices.
A scan of 4,096 prices reads 192 KB — six times L1 — so it misses on very nearly every line.
// SoA — struct of arrays. Hot fields packed together.
struct BookSoA {
std::array<double, 4096> px{}; // contiguous
std::array<int, 4096> qty{}; // contiguous
std::array<Venue, 4096> venue{}; // never touched in the scan
};
// One 64-byte line feeds 8 prices, and the
// hardware prefetcher sees the pattern coming.
The same scan reads 32 KB — it fits in L1, and the prefetcher hides most of what does not.
Below is a micro-benchmark of one operation whose true cost is 42 ns. You do not get to see that number — you get to see what your harness reports. Switch the four pitfalls on and off and watch the reported figure wander between zero and several hundred nanoseconds, all of it from the same code.
// bench.hpp — the shape of the harness the grader uses (C++20)
#include <algorithm>
#include <chrono>
#include <vector>
template <class T>
inline void doNotOptimize(const T& v) { // the sink
asm volatile("" : : "r,m"(v) : "memory");
}
template <class F>
std::vector<double> sample_ns(F&& f, int n) {
using clk = std::chrono::steady_clock; // monotonic
for (int i = 0; i < n / 10; ++i) doNotOptimize(f()); // warm up
std::vector<double> ns;
ns.reserve(static_cast<std::size_t>(n));
for (int i = 0; i < n; ++i) {
const auto t0 = clk::now();
auto r = f();
const auto t1 = clk::now();
doNotOptimize(r); // or it never ran
ns.push_back(
std::chrono::duration<double, std::nano>(t1 - t0).count());
}
std::sort(ns.begin(), ns.end()); // percentiles, not a mean
return ns;
}
new per tick is a tail, not a slowdownHere is the point of the whole week in one picture. An allocation costs about 60 ns most of the time — which is nothing. The problem is the word most. One call in sixty walks a free list; one in a thousand takes a lock or faults a fresh page. Those calls do not move your median at all, and they are the only ones the LATENCY board can see.
new,
no make_shared, no push_back that can grow, no std::string
concatenation.Abstraction in C++ is free only when the compiler can see through it. Walk the same price-to-tick conversion through three versions of one idea and watch the work disappear — first into an inlined call, then into the binary itself.
Illustrative. The instruction counts above are hand-drawn to show the shape of
the effect, not measured on your machine. The method is the transferable part:
compile at -O2, read the assembly with objdump -d, and count for yourself.
Week 6 makes this the main event.
Every one of these has shipped in a submission. Open them.
At -O2 the optimiser may delete any computation whose result is never observed. Your
timing loop computes something, throws it away, and the compiler removes the body — so you have
carefully measured an empty loop and a pair of steady_clock reads.
The tell is a number that is suspiciously round, suspiciously small, or does not change when you double the work.
Fix: sink every result through a doNotOptimize helper, and sanity-check
by doubling the iteration count — if the time does not roughly double, you are not measuring what
you think you are.
A -O0 build keeps every function call, every temporary and every abstraction layer.
Ratios between two implementations can invert entirely: the version with more inlineable structure
looks worse, because none of it got inlined.
Fix: -O2 or -O3 plus -g so you still get
symbols in the profiler. Benchmark the thing you will ship — including the same -march,
since Week 13's SIMD depends on it.
Two errors that hide each other. The first samples of any loop pay for cold caches, an untrained branch predictor and first-touch page faults, so an unwarmed mean is inflated. And a mean over a right-skewed distribution describes no actual tick: a 38 µs mean is equally consistent with a 20 µs median and a 5 ms tail.
Fix: warm up for roughly a tenth of your sample count, then collect, sort and report p50 / p99 / p99.9. Keep the minimum too — it is the closest thing you have to the cost with no noise in it, which is exactly what you want when comparing two implementations.
system_clock, or timing a region that contains I/Ostd::chrono::system_clock is wall-clock time and may step backwards when NTP
corrects it, which produces negative durations and nonsense percentiles. And a std::cout
inside the timed region measures your terminal: a flush is easily tens of microseconds, hundreds of
times the thing you meant to time.
Fix: std::chrono::steady_clock, and time the smallest region that
contains the work and nothing else. Push log lines into a pre-allocated ring buffer and drain them
from another thread — Week 10 builds exactly that ring.
Two std::atomic<long> members declared next to each other land on one 64-byte
cache line. Two cores incrementing them independently now invalidate each other's copy on every
write — false sharing — and you get a threaded program slower than the
single-threaded one, with nothing visibly wrong in the source.
Fix: alignas(64) on each hot counter, or a padding array between them.
Padding is not waste when it buys a clean line. Week 9 explains the coherency protocol underneath,
and Week 10 depends on the fix for its SPSC ring.
#include <atomic>
#include <new>
struct Counters { // 2–4× faster than the unpadded version
alignas(64) std::atomic<long> produced{0};
alignas(64) std::atomic<long> consumed{0};
};
static_assert(sizeof(Counters) == 128);
static_assert(alignof(Counters) == 64);
Three questions, instant feedback, nothing recorded.
Q1Roughly how many L1 cache hits fit in the time of one main-memory access?
Q2Why is a single new inside on_book a problem, given that the median allocation takes about 60 ns?
Q3Your release-build benchmark of a function that clearly does real work reports 0.3 ns per operation. What happened?
new[]/delete[] of the same size. Expect
10–50×, and report percentiles.alignas(64) and measure again.on_book p50 / p99 / p99.9 baseline. Every later topic is graded
against this number.