The Latency Budget: Measuring, Cache Behavior and What to Optimize
Reason about tail latency and coordinated omission, compare book layouts by counted cache misses and allocations, then wire the course's pieces into one deterministic, replayable simulation.
Where the time goes between an event and a reaction
A trading system's critical path starts when a market-data packet arrives and ends when an order leaves. In between, the parts this course built each take their share: the feed handler decodes the message (Parsing Market Data), the book is updated (The Limit Order Book), the strategy decides, the order passes pre-trade risk checks (Order Types, Time-in-Force and Pre-Trade Checks) and the gateway sends it. On the exchange side, the matching engine (A Matching Engine) has its own path from incoming order to outgoing trade and market data.
A latency budget assigns each stage a share of the total time allowed for that path, so that a regression in one stage shows up as a stage over budget rather than as a vague "the system got slower". The actual numbers depend entirely on hardware, network and design, and this lesson quotes none: real figures come only from measuring a real system with the tools described below. What this lesson does instead is make the reasoning concrete by counting: how often a slow path is hit, how many cache lines a data structure touches, how many heap allocations an operation makes. Counts are deterministic, they transfer between machines, and they explain most of what a timer would show.
The lesson ends with the capstone: one program that wires the engine, the binary feed, the risk checks, a strategy and the back-test loop into a single deterministic simulation, and proves its determinism by replaying its input log.
Why the tail matters more than the average
The usual summary of a set of latencies is the mean, and for a trading path it is the least useful one. The events a strategy most needs to react to quickly (a burst of activity after a large trade) are exactly when queues are fullest and slow paths most likely. What matters is the distribution's tail: the 99th percentile (p99, the value that 99% of measurements are at or below), the 99.9th and the maximum.
A small model shows how a rare slow path dominates the tail. Each request passes through 5 stages. A stage normally costs 1 unit of work, but one time in 100 it takes a slow path costing 50 units (think of a cache miss, a page fault, a lock held by someone else). The units are abstract; the model is about shape, not about any real timing.
#include <algorithm>
#include <cstdint>
#include <print>
#include <vector>
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
// A made-up model, in abstract cost units: each of 5 stages costs 1 unit,
// except that 1 time in 100 it takes a slow path costing 50 units.
int request_cost(Lcg& rng, int stages) {
int cost = 0;
for (int s = 0; s < stages; ++s) cost += rng.range(1, 100) == 1 ? 50 : 1;
return cost;
}
// The value at quantile q of sorted samples (nearest rank).
int percentile(const std::vector<int>& sorted, double q) {
std::size_t rank = std::size_t(q * double(sorted.size()));
return sorted[std::min(rank, sorted.size() - 1)];
}
int main() {
Lcg rng{1};
const int n = 100'000;
std::vector<int> cost(n);
long long total = 0;
int hit_slow = 0;
for (int& c : cost) {
c = request_cost(rng, 5);
total += c;
hit_slow += c > 5;
}
std::ranges::sort(cost);
std::println("requests: {}, mean cost {:.2f} units", n, double(total) / n);
std::println("p50 {} p90 {} p99 {} p99.9 {} max {}", percentile(cost, 0.50),
percentile(cost, 0.90), percentile(cost, 0.99), percentile(cost, 0.999),
cost.back());
std::println("requests that hit at least one slow stage: {:.2f}%",
100.0 * hit_slow / n);
// How often does a request that needs k independent parts hit a slow one?
for (int k : {1, 5, 20, 100}) {
int slow = 0;
for (int i = 0; i < n; ++i) slow += request_cost(rng, k) > k;
std::println("needs {:>3} parts: {:>5.1f}% of requests hit a slow path", k,
100.0 * slow / n);
}
}Press Run to compile and run this example.
requests: 100000, mean cost 7.46 units
p50 5 p90 5 p99 54 p99.9 103 max 152
requests that hit at least one slow stage: 4.92%
needs 1 parts: 1.0% of requests hit a slow path
needs 5 parts: 4.9% of requests hit a slow path
needs 20 parts: 18.3% of requests hit a slow path
needs 100 parts: 63.5% of requests hit a slow pathThe median request costs 5 units and so does the 90th percentile. The mean is only 7.46. Yet the p99 is 54 and the p99.9 is 103: one request in a hundred is about ten times slower than the typical one, and the mean hides that almost completely. Rare slow paths compound, too. A request that touches k independent parts hits at least one slow path with probability 1 - 0.99^k: 4.9% for 5 parts, 18% for 20 and 63% for 100, as the last four lines show. A system that fans one decision out to many components (or one strategy that reads many instruments' books) turns a 1% event into the common case.
Two practical consequences follow. Report latency as percentiles from a histogram, never as a mean and standard deviation (the distribution is far from normal). And look for the causes of the slow path, which is usually a specific event (an allocation, a system call, a miss in a large table), rather than shaving the fast path further.
Measuring the wrong thing: coordinated omission
How the measurements are taken matters as much as how they are summarized. A common load test sends a request, waits for the answer, records the time, and sends the next one. If the system stalls for a while, the tester stalls with it: it records one slow answer and then simply does not send the requests it was supposed to send during the stall. Those requests, which real clients would have sent and which would all have waited, never appear in the data. Gil Tene named this coordinated omission: the measuring system coordinates with the measured one and omits exactly the bad samples.
The model: a server that answers every request in 1 time unit, except that it freezes from time 50,000 to 52,000. The load test intends to send one request every 10 units for 100,000 units. The first measurement times each request from when it was actually sent. The second times each request from when it should have been sent, so requests that queued behind the stall count their waiting time.
#include <algorithm>
#include <cstdint>
#include <print>
#include <vector>
// A simulated server in abstract time units: every request takes 1 unit,
// except that the server freezes from time 50'000 to 52'000.
// The load test intends to send one request every 10 units for 100'000 units.
constexpr std::int64_t kStallStart = 50'000, kStallEnd = 52'000;
constexpr std::int64_t kInterval = 10, kDuration = 100'000;
std::int64_t finish_time(std::int64_t start) { // when a request sent at `start` ends
if (start >= kStallStart && start < kStallEnd) start = kStallEnd;
return start + 1;
}
void report(const char* name, std::vector<std::int64_t> v) {
std::ranges::sort(v);
auto at = [&](double q) { return v[std::min(std::size_t(q * double(v.size())),
v.size() - 1)]; };
std::println("{:<28} samples {:>6} p50 {:>4} p99 {:>5} p99.9 {:>5} max {:>5}",
name, v.size(), at(0.5), at(0.99), at(0.999), v.back());
}
int main() {
// Closed loop: send, wait for the answer, then send the next one when due.
// The time it measures runs from the actual send.
std::vector<std::int64_t> naive;
std::int64_t now = 0;
while (now < kDuration) {
std::int64_t done = finish_time(now);
naive.push_back(done - now);
now = std::max(done, now + kInterval); // late requests are simply not sent
}
// Corrected: every request on the intended schedule, timed from when it
// should have been sent. A request queued behind the stall waits too.
std::vector<std::int64_t> corrected;
std::int64_t free_at = 0; // when the server can start the next request
for (std::int64_t intended = 0; intended < kDuration; intended += kInterval) {
std::int64_t done = finish_time(std::max(intended, free_at));
free_at = done;
corrected.push_back(done - intended);
}
report("measured from actual send:", naive);
report("measured from intended send:", corrected);
}Press Run to compile and run this example.
measured from actual send: samples 9801 p50 1 p99 1 p99.9 1 max 2001
measured from intended send: samples 10000 p50 1 p99 1110 p99.9 1920 max 2001Both measurements see the same server. The naive one has 199 fewer samples, the ones that should have arrived during the stall, and its p99 and p99.9 are a perfect 1 unit; only the maximum hints that something happened. The corrected measurement shows that 2% of the requests a client would have sent waited between a few and 2,000 units, which moves the p99 to 1,110. The fix is to measure from the intended send time (or to correct the recorded histogram for missing samples, which some latency libraries do).
Why memory layout dominates: a cache model
On modern CPUs, reading data that is already in a cache is far cheaper than fetching it from main memory, and data moves between them in cache lines (64 bytes on common x86-64 and many ARM processors). A program that walks memory in order uses every byte of each line it fetches; one that jumps around fetches a whole line for each value it uses. That difference is mostly invisible in the source code and often decides the speed of a data structure.
Rather than time it, we can count it. The program below is a deliberately simple cache model: 512 lines of 64 bytes, each memory line allowed in exactly one slot (direct-mapped). It counts misses, accesses to a line not currently in the cache. Real caches have several levels, associativity and hardware prefetchers that detect sequential access; the model ignores all of that and only counts lines. The program walks 100,000 values three ways: an array of int, a linked list whose nodes sit in memory in list order, and the same list with nodes scattered (as happens when nodes are allocated at different times, interleaved with other allocations).
#include <cstdint>
#include <numeric>
#include <print>
#include <vector>
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
// A toy cache: 512 lines of 64 bytes (32 KiB), direct-mapped (each memory
// line can live in exactly one slot). Real caches have several levels,
// associativity and prefetchers; this one only counts which lines are touched.
class CacheModel {
public:
void touch(std::uint64_t address) {
std::uint64_t line = address / 64;
std::uint64_t& slot = slots_[line % slots_.size()];
if (slot != line + 1) { ++misses_; slot = line + 1; } // +1: 0 means empty
++accesses_;
}
long misses() const { return misses_; }
long accesses() const { return accesses_; }
private:
std::vector<std::uint64_t> slots_ = std::vector<std::uint64_t>(512, 0);
long misses_ = 0, accesses_ = 0;
};
int main() {
const int n = 100'000;
// Model addresses: an int array of n * 4 bytes, and list nodes of 16 bytes
// (an 8-byte value and an 8-byte next pointer) in a block of n * 16 bytes.
CacheModel array;
for (int i = 0; i < n; ++i) array.touch(std::uint64_t(i) * 4);
std::vector<int> order(n); // order[k] = the slot of the k-th node in the list
std::iota(order.begin(), order.end(), 0);
CacheModel list_in_order;
for (int k = 0; k < n; ++k) list_in_order.touch(std::uint64_t(order[k]) * 16);
Lcg rng{1}; // nodes allocated at scattered times end up at scattered places
for (int i = n - 1; i > 0; --i) std::swap(order[i], order[rng.range(0, i)]);
CacheModel list_shuffled;
for (int k = 0; k < n; ++k) list_shuffled.touch(std::uint64_t(order[k]) * 16);
for (auto [name, c] : {std::pair{"array of int", &array},
std::pair{"list, nodes in order", &list_in_order},
std::pair{"list, nodes scattered", &list_shuffled}})
std::println("{:<22} {:>6} accesses {:>6} misses ({:.1f}%)", name, c->accesses(),
c->misses(), 100.0 * double(c->misses()) / double(c->accesses()));
}Press Run to compile and run this example.
array of int 100000 accesses 6250 misses (6.2%)
list, nodes in order 100000 accesses 25000 misses (25.0%)
list, nodes scattered 100000 accesses 98472 misses (98.5%)The array misses once per 16 values (64 / 4); the ordered list once per 4 nodes (64 / 16); the scattered list almost once per node. Same number of elements, same algorithm, a factor of 16 between the best and the worst, and on real hardware the scattered list is also the one a prefetcher cannot help, because the next address is known only after the current node has arrived. Ulrich Drepper's "What Every Programmer Should Know About Memory" (2007) explains the hardware behind these numbers in depth.
Storing price levels: `std::map`, sorted vector or tick array
The order book in this course keeps each side in a std::map keyed by price. That gives O(log L) lookups for L levels and easy ordered iteration, and every level is a separate heap-allocated tree node: exactly the scattered layout of the previous section. Two flatter alternatives are common:
- a sorted
std::vectorof levels. Lookups are a binary search over contiguous memory. Inserting or removing a level shifts the elements after it, so keep the best price at the back: most activity happens near the top of the book, and changes there move few elements. - an array indexed by tick offset from a base price. Each price maps directly to a slot, so an update is O(1) with no search at all. The best level is tracked with an index; when it empties, the code scans to the next non-empty slot. The cost is memory proportional to the price range covered and a policy for prices outside it (re-centering or a fallback structure).
The program runs the same seeded workload of 20,000 adds and level removals on one side of the book, concentrated near the top, through all three. It counts comparisons, element moves or scan steps, and heap allocations, and checks that all three report the same best bid after every operation.
#include <algorithm>
#include <cstdint>
#include <functional>
#include <map>
#include <optional>
#include <format>
#include <print>
#include <string>
#include <type_traits>
#include <vector>
using Price = std::int64_t;
using Qty = std::int64_t;
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
long g_compares = 0, g_moves = 0, g_allocs = 0; // costs, counted
// One side (bids) of the book, price -> total quantity, three ways.
struct MapLevels {
std::map<Price, Qty, std::greater<>> m; // bids: highest price first
void add(Price p, Qty q) {
auto [it, is_new] = m.try_emplace(p, 0);
g_allocs += is_new; // a new level is a new heap-allocated tree node
it->second += q;
}
void clear(Price p) { m.erase(p); }
std::optional<Price> best() const {
return m.empty() ? std::nullopt : std::optional(m.begin()->first);
}
};
struct VectorLevels { // sorted with the best price at the BACK: changes near the
struct Level { Price price; Qty qty; }; // top move few elements
std::vector<Level> v;
auto find(Price p) {
return std::lower_bound(v.begin(), v.end(), p, [](const Level& l, Price x) {
++g_compares;
return l.price < x;
});
}
void add(Price p, Qty q) {
auto it = find(p);
if (it != v.end() && it->price == p) { it->qty += q; return; }
g_moves += v.end() - it; // elements shifted right by the insert
auto capacity = v.capacity();
v.insert(it, {p, q});
g_allocs += v.capacity() != capacity; // grew: a new, larger buffer
}
void clear(Price p) {
auto it = find(p);
if (it == v.end() || it->price != p) return;
g_moves += v.end() - it - 1; // elements shifted left by the erase
v.erase(it);
}
std::optional<Price> best() const {
return v.empty() ? std::nullopt : std::optional(v.back().price);
}
};
struct ArrayLevels { // one slot per tick in a fixed window of prices
static constexpr Price kBase = 9'700;
std::vector<Qty> qty = std::vector<Qty>(512, 0);
int top = -1; // index of the best non-empty level, -1 if none
void add(Price p, Qty q) {
int i = int(p - kBase);
qty[i] += q;
top = std::max(top, i);
}
void clear(Price p) {
int i = int(p - kBase);
qty[i] = 0;
while (top >= 0 && qty[top] == 0) { --top; ++g_moves; } // scan down
}
std::optional<Price> best() const {
return top < 0 ? std::nullopt : std::optional(kBase + top);
}
};
template <class Book>
void run(const char* name, std::optional<Price>* bests, std::size_t& levels) {
g_compares = g_moves = g_allocs = 0;
Book book;
Lcg rng{7};
const int ops = 20'000;
for (int i = 0; i < ops; ++i) {
// Most activity is near the top of the book: the smaller of two draws.
Price p = 10'000 - std::min(rng.range(0, 200), rng.range(0, 200));
if (rng.range(1, 10) <= 6) book.add(p, rng.range(1, 10));
else book.clear(p);
bests[i] = book.best();
}
if constexpr (requires { book.m; }) levels = book.m.size();
// std::map's exact comparison count differs between standard libraries
// (only O(log n) is specified), so it is not printed.
std::string compares = std::is_same_v<Book, MapLevels>
? "O(log n)" : std::format("{:.2f}", double(g_compares) / ops);
std::println("{:<14} {:>8} {:>15.2f} {:>12}", name, compares, double(g_moves) / ops,
g_allocs);
}
int main() {
static std::optional<Price> a[20'000], b[20'000], c[20'000];
std::size_t levels = 0;
std::println("{:<14} {:>8} {:>15} {:>12}", "per operation", "compares",
"moves or scans", "allocations");
run<MapLevels>("std::map", a, levels);
run<VectorLevels>("sorted vector", b, levels);
run<ArrayLevels>("tick array", c, levels);
bool agree = std::ranges::equal(a, b) && std::ranges::equal(b, c);
std::println("levels in the book at the end: {}", levels);
std::println("all three report the same best bid after every operation: {}",
agree ? "yes" : "NO");
}Press Run to compile and run this example.
per operation compares moves or scans allocations
std::map O(log n) 0.00 4871
sorted vector 6.90 18.84 9
tick array 0.00 0.01 0
levels in the book at the end: 107
all three report the same best bid after every operation: yesThe map row prints no comparison count, and that is a lesson of its own. The standard specifies that std::map operations are logarithmic, not how many times the comparator is called, and the two major standard libraries differ: on this workload libc++ (Clang) made 9.17 comparisons per operation and libstdc++ (GCC) 10.33. A count that depends on the library is not a portable fact, so it is not printed. Everything else is. The map allocated a new node for each of 4,871 new levels, each a separate heap block. The sorted vector did 6.90 comparisons per operation over contiguous memory, moved about 19 elements per operation (cheap, since they are adjacent) and reallocated its buffer 9 times as it grew by doubling (the growth policy is also the library's choice; both of these use doubling). The tick array did no comparisons, almost no scanning and no allocations.
Which to choose depends on the price range and the activity pattern, and that is the point of counting: these numbers come from a workload that you can change and rerun. If activity were spread uniformly across a wide range, the vector's moves would grow and the array's memory would grow.
Counting allocations: the default heap or an arena
A heap allocation costs more than the instructions around it suggest: the allocator has bookkeeping to do, may take a lock, may ask the operating system for memory (a system call and, on first touch, page faults), and returns blocks scattered across memory. A common rule on a latency-critical path is no allocation after startup: size everything in advance and reuse it.
C++17's polymorphic memory resources (<memory_resource>) make that measurable and controllable without rewriting containers. A std::pmr::map takes a std::pmr::memory_resource* and allocates through it. The program below implements a CountingResource that counts the requests reaching the ordinary heap, and runs the same workload (an order index and a level map: 20,000 adds and cancels) twice: once with every node coming straight from the heap, once from a std::pmr::monotonic_buffer_resource that hands out pieces of one pre-allocated 8 MiB buffer.
#include <array>
#include <cstddef>
#include <cstdint>
#include <map>
#include <memory_resource>
#include <print>
#include <vector>
using Price = std::int64_t;
using Qty = std::int64_t;
using OrderId = std::uint64_t;
enum class Side : std::uint8_t { Buy, Sell };
struct Order { OrderId id; Side side; Price price; Qty qty; };
struct Lcg {
std::uint64_t s;
std::uint32_t next() {
s = s * 6364136223846793005ULL + 1442695040888963407ULL;
return std::uint32_t(s >> 33);
}
int range(int lo, int hi) { return lo + int(next() % std::uint32_t(hi - lo + 1)); }
};
// A memory resource that counts what it is asked for, then forwards to the
// ordinary heap (operator new and delete).
class CountingResource : public std::pmr::memory_resource {
public:
long allocations = 0, frees = 0;
private:
void* do_allocate(std::size_t n, std::size_t align) override {
++allocations;
return std::pmr::new_delete_resource()->allocate(n, align);
}
void do_deallocate(void* p, std::size_t n, std::size_t align) override {
++frees;
std::pmr::new_delete_resource()->deallocate(p, n, align);
}
bool do_is_equal(const memory_resource& o) const noexcept override {
return this == &o;
}
};
// The bookkeeping part of a book: an index of live orders, and the total
// quantity per price level, both allocating from `mem`.
void workload(std::pmr::memory_resource* mem) {
std::pmr::map<OrderId, Order> orders(mem);
std::pmr::map<Price, Qty> levels(mem);
std::vector<OrderId> live; // ids of live orders (its own allocations not counted)
live.reserve(20'000);
Lcg rng{11};
OrderId next_id = 1;
for (int i = 0; i < 20'000; ++i) {
if (live.empty() || rng.range(1, 10) <= 6) {
Order o{next_id++, Side::Buy, 10'000 - rng.range(0, 50), rng.range(1, 10)};
orders.emplace(o.id, o);
levels[o.price] += o.qty;
live.push_back(o.id);
} else { // cancel a random live order (swap-and-pop keeps `live` dense)
std::size_t k = std::size_t(rng.range(0, int(live.size()) - 1));
auto it = orders.find(live[k]);
if ((levels[it->second.price] -= it->second.qty) == 0)
levels.erase(it->second.price);
orders.erase(it);
live[k] = live.back();
live.pop_back();
}
}
}
int main() {
CountingResource heap; // every node straight from the heap
workload(&heap);
std::println("heap: {} allocations, {} frees", heap.allocations, heap.frees);
static std::array<std::byte, 8 << 20> buffer; // 8 MiB, sized for this run
CountingResource upstream; // asked only if the buffer runs out
{
std::pmr::monotonic_buffer_resource arena(buffer.data(), buffer.size(),
&upstream);
workload(&arena);
} // the arena releases everything at once, here
std::println("arena: {} allocations, {} frees from the heap", upstream.allocations,
upstream.frees);
}Press Run to compile and run this example.
heap: 12183 allocations, 12183 frees
arena: 0 allocations, 0 frees from the heapThe heap version made 12,183 separate allocations, one per tree node, and as many frees. With the arena, the heap was never asked for anything: the arena carved every node out of its buffer with a pointer increment, and the whole buffer is released at once when the arena is destroyed.
The trade-off is the reason the arena is called monotonic: freeing a node returns nothing, so memory use only grows until the arena is destroyed. That fits a workload with a natural reset point (a trading session, a batch, a request) and is wrong for a long-running book with heavy churn. For that case std::pmr::unsynchronized_pool_resource keeps pools of fixed-size blocks and reuses freed ones; a hand-written pool or free list of Order slots, sized at startup, is the other common answer. The buffer size here was chosen generously for this workload; if it runs out, the arena silently asks its upstream for more, which is why the upstream should be a counting resource in tests.
Other costs on the hot path
Not everything can be counted in a portable program, but each of these is worth knowing by name and mechanism:
- Branch misprediction. CPUs guess the direction of a branch before it is resolved and execute ahead speculatively; a wrong guess throws that work away. Branches that depend on unpredictable data (the side of the next order, say) mispredict often. Remedies include branch-free formulations and keeping the common case on a predictable path.
- False sharing. Two threads writing to different variables that happen to share a cache line force that line to move back and forth between their cores, although they share no data. Align such variables to separate lines; C++17 provides
std::hardware_destructive_interference_sizeas a portable hint for the distance. - Page faults. The first touch of a newly mapped page traps into the operating system. Touching (and locking) memory at startup moves that cost out of the hot path. Large pages reduce the number of address translations the CPU has to cache.
- NUMA. On machines with several processor sockets, memory attached to another socket is slower to reach. Pin a thread to a core and allocate its memory on the same node.
- System calls. Every crossing into the kernel (sending on a socket, reading a clock on some systems, allocating fresh memory) costs far more than a function call. Kernel-bypass networking exists to remove them from the packet path.
Carl Cook's CppCon 2017 talk "When a Microsecond Is an Eternity: High Performance Trading Systems in C++" walks through several of these from the point of view of a trading system, including keeping the cache warm on a path that runs rarely.