Low-Latency Software · Technology

7C++ for Latency II: Compile Time

Four stages of a hot path, each a class with a virtual function called through a pointer, cost this book’s laptop about seven nanoseconds per event. The same four stages composed as template parameters cost about one: the compiler, seeing every call, inlined all four into thirteen machine instructions with no call left in them. The work was identical; what changed is how much the compiler knew when it compiled. This chapter is about moving decisions from run time to compile time in C++: dispatch by templates instead of virtual functions, values computed by the compiler, inlining and what prevents it, and the layout of rare code away from the common path.

7.1 Virtual dispatch and what it costs

Definition 7.1 (Dynamic dispatch, devirtualisation)

In dynamic dispatch the function called depends on the run-time type of an object: a C++ virtual call loads the object’s table of function pointers and calls through it, an indirect call. Devirtualisation is the compiler’s replacement of such a call by a direct one, when it can prove the object’s type (a final class, a local object, whole-program analysis).

An indirect call costs little when the processor predicts its target: the branch predictor keeps a history of targets, and a hot path that always sees the same message type always calls the same function. It costs a misprediction when the target changes unpredictably, and it always costs the optimisations it blocks: the compiler cannot inline a function it cannot name, so it cannot fold the callee’s work into the caller, keep values in registers across the call, or vectorise the loop around it. The published measurement of the direct cost of virtual calls in C++ (Driesen and Hölzle, 1996) found it modest in cycles; the indirect cost, lost optimisation, is usually larger and does not appear in a microbenchmark of the call alone.

7.2 Static polymorphism: templates, CRTP and concepts

Definition 7.2 (Static polymorphism, curiously recurring template pattern)

Static polymorphism selects the function to call at compile time, by templates or overloading, so that every call is direct. In the curiously recurring template pattern (CRTP) a class template takes its own derived class as a parameter, struct Book : Base<Book>, and the base calls the derived class’s functions through a static_cast of this.

A trading hot path rarely needs run-time polymorphism: the set of message types is fixed by the protocol, and the strategy is chosen when the process starts. Both can be template parameters. C++20 concepts state the requirement a parameter must meet (“has bool on(E&)”), so the error for a stage that does not fit is one line instead of a page. Figure 7.1 compares three dispatchers of one message to one of four handlers (add, cancel, execute, trade), each doing an addition or two: virtual handlers in a table, std::variant with std::visit, and CRTP with a switch. On a stream of one message type, where every branch is predicted, the CRTP dispatcher costs about half a nanosecond per message and the virtual one about four times as much; on a random mix of the four types all three pay mispredictions, and the gap narrows. The last two bars are the four-stage pipeline of the opening, static and dynamic.

Cost per message of three ways to dispatch it to its handler, on a stream of one type and on a random mix, and of a four-stage pipeline composed statically (firm.pipeline) and through virtual calls (the pipeline’s cost does not depend on the message mix). Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores, pinned to one CPU, best of 15 runs of 65 536 messages. Data: bench_dispatch.py. — **Figure 7.1.** Cost per message of three ways to dispatch it to its handler, on a stream of one type and on a random mix, and of a four-stage pipeline composed statically (`firm.pipeline`) and through virtual calls (the pipeline’s cost does not depend on the message mix). Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores, pinned to one CPU, best of 15 runs of 65 536 messages. Data: `bench_dispatch.py`.

7.3 Compile-time evaluation

Definition 7.3 (Compile-time evaluation)

Compile-time evaluation computes a value while compiling instead of while running: a constexpr function may be evaluated by the compiler when its arguments are constants, and a consteval function must be, so that its result is a constant embedded in the program.

Tables are the typical use: powers of ten to rescale prices between protocols with different implied decimals, the mapping from a protocol’s message type byte to a handler index, the lengths of fixed-size messages, checksum tables. Built by the compiler, a table costs nothing at start-up, cannot be forgotten in an initialisation routine, and is checked by static_assert when the program compiles. Layout facts belong there too: the build of chapter 3 asserts at compile time that a padded counter occupies exactly one cache line, and chapter 16 asserts each message’s size against the protocol’s specification.

7.4 Inlining and its limits

Definition 7.4 (Inlining)

Inlining is the compiler’s replacement of a call by the body of the called function, which removes the call’s own cost and, more importantly, lets the compiler optimise the combined code: propagate constants, keep values in registers, remove work whose result is unused.

The static pipeline of Listing 7.4 is the whole effect in thirteen instructions: the four stages’ additions, the exclusive-or, the comparison and the conditional update, with the stage objects folded into loads and stores. Its dynamic twin (Listing 7.5) is a loop over a vector of pointers with an indirect call per stage. The compiler inlines by a cost model: small functions, functions called once, functions whose definition it can see. It will not inline across translation units without link-time optimisation (chapter 8), through a function pointer it cannot resolve, or a function marked noinline; and it may decline to inline a large function into a hot loop. [[gnu::always_inline]] overrides the cost model for the few functions that must be inlined; it is a statement about this compiler’s heuristics, and should be verified in the assembly rather than trusted.

7.5 Branch layout and cold paths

Definition 7.5 (Cold path)

A cold path is code that runs rarely (error handling, logging of an anomaly, recovery). Keeping it out of the hot function, by marking the rare branch [[unlikely]] and the rare function cold and noinline, keeps the hot code small and contiguous in the instruction cache, with the common case falling through.

GCC places functions marked cold in a separate section with the other cold functions and treats branches to them as unlikely. The rescaling function of the tutorial checks its arguments, and the check costs one comparison and a predicted branch; the report of a bad argument, with its formatted output, lives out of line. The discipline matters more than any single attribute: the hot function should contain the common case and calls to everything else.

7.6 Tutorial: three dispatchers and a pipeline

Goal. Dispatch messages three ways, compose a pipeline at compile time, and read in the assembly what the compiler made of each. End state: Figure 7.1 and the two listings of assembly.

CRTP. The base’s on switches on the type and calls the derived class’s handler directly.

// 3. Static polymorphism with the curiously recurring template pattern: the base knows the derived type at compile
// time, so every handler call is direct and can be inlined.
template <class Derived>
struct StaticDispatch {
    void on(const Msg& m, State& s) {
        auto& d = static_cast<Derived&>(*this);
        switch (m.type) {
            case kAdd: d.on_add(m, s); break;
            case kCancel: d.on_cancel(m, s); break;
            case kExec: d.on_exec(m, s); break;
            default: d.on_trade(m, s); break;
        }
    }
};
struct Book : StaticDispatch<Book> {
    void on_add(const Msg& m, State& s) { s.added += m.qty; }
    void on_cancel(const Msg& m, State& s) { s.cancelled += m.qty; }
    void on_exec(const Msg& m, State& s) { s.executed += m.qty; }
    void on_trade(const Msg& m, State& s) { s.notional += m.price * m.qty; }
};

Listing 7.1. Static dispatch with the curiously recurring template pattern. code/low-latency/07-cpp-for-latency-ii-compile-time/cpp/ll_dispatch.hpp

A table the compiler builds, and a rare path it keeps out of line.

// A table computed by the compiler: powers of ten for scaling prices with up to 18 implied decimals.
consteval std::array<std::int64_t, 19> make_pow10() {
    std::array<std::int64_t, 19> t{};
    t[0] = 1;
    for (std::size_t i = 1; i < t.size(); ++i) t[i] = t[i - 1] * 10;
    return t;
}
inline constexpr auto kPow10 = make_pow10();
static_assert(kPow10[4] == 10'000 && kPow10[18] == 1'000'000'000'000'000'000);

// The rare path, out of line: the hot function keeps only a predicted-not-taken branch and a call.
[[gnu::cold, gnu::noinline]] inline void report_bad_scale(int scale) { std::fprintf(stderr, "bad price scale %d\n", scale); }

inline std::int64_t rescale(std::int64_t price, int from, int to) {
    if (from < 0 || from > 18 || to < 0 || to > 18) [[unlikely]] {
        report_bad_scale(from < 0 || from > 18 ? from : to);
        return 0;
    }
    return to >= from ? price * kPow10[static_cast<std::size_t>(to - from)] : price / kPow10[static_cast<std::size_t>(from - to)];
}

Listing 7.2. A compile-time table and a cold error path. code/low-latency/07-cpp-for-latency-ii-compile-time/cpp/ll_dispatch.hpp

Compose stages. A fold expression over a tuple of stages, constrained by a concept; && stops at the first stage that rejects the event.

template <class E, Stage<E>... S>
class Pipeline {
public:
    Pipeline() = default;
    explicit Pipeline(S... s) : stages_(std::move(s)...) {}
    // Stops at the first stage that returns false; && is short-circuit inside the fold.
    bool on(E& e) {
        return std::apply([&](auto&... s) { return (s.on(e) && ...); }, stages_);
    }
    template <std::size_t I>
    auto& stage() { return std::get<I>(stages_); }

private:
    std::tuple<S...> stages_;
};

Listing 7.3. The static pipeline of firm.pipeline. code/firm/pipeline/cpp/firm_pipeline.hpp

Read the assembly. python ll_asm.py compiles two one-line functions with -O2 -masm=intel and extracts their bodies.

	endbr64
	mov	rdx, QWORD PTR [rsi]
	mov	eax, DWORD PTR 8[rsi]
	xor	r8d, r8d
	add	rax, QWORD PTR 16[rsi]
	xor	rax, rdx
	mov	QWORD PTR 16[rsi], rax
	cmp	rdx, QWORD PTR 8[rdi]
	jge	.L1
	add	QWORD PTR [rdi], rax
	mov	r8d, 1
.L1:
	mov	eax, r8d
	ret

Listing 7.4. The four-stage static pipeline after inlining (g++ 11.4, -O2). code/low-latency/07-cpp-for-latency-ii-compile-time/cpp/asm/run_static.s

	endbr64
	push	r12
	push	rbp
	push	rbx
	mov	rbx, QWORD PTR [rdi]
	mov	r12, QWORD PTR 8[rdi]
	cmp	rbx, r12
	je	.L6
	mov	rbp, rsi
	jmp	.L8
.L14:
	add	rbx, 8
	cmp	r12, rbx
	je	.L6
.L8:
	mov	rdi, QWORD PTR [rbx]
	mov	rsi, rbp
	mov	rax, QWORD PTR [rdi]
	call	[QWORD PTR 16[rax]]
	test	al, al
	jne	.L14
	pop	rbx
	pop	rbp
	pop	r12
	ret
.L6:
	pop	rbx
	mov	eax, 1
	pop	rbp
	pop	r12
	ret

Listing 7.5. The same pipeline through virtual calls: a loop with an indirect call per stage. code/low-latency/07-cpp-for-latency-ii-compile-time/cpp/asm/run_dynamic.s

Measure with python bench_dispatch.py.

What to change next. Mark the dispatch table’s handlers final and access them through their concrete types, and see whether the compiler devirtualises; add [[gnu::noinline]] to one stage of the static pipeline and read the assembly again.

7.7 Build: the compile-time pipeline

Purpose. The composition of the hot path of Part IV (decode, book, strategy, risk, gateway) as one statically dispatched call chain, with a runtime-polymorphic twin for tests and for configurations chosen at start-up.

Interface. C++20 firm::pipeline: concept Stage<S, E>; Pipeline<E, S…> with on(E&) and stage<I>(); AnyStage<E>, DynPipeline<E> with add and on. Rust firm_pipeline: trait Stage<E>, Chain<A, B> and the chain! macro, DynPipeline<E>.

Rules. Stages run in order; the first false stops the event; the static and dynamic pipelines give the same results and the same order of effects; a stage that does not meet the concept does not compile.

Acceptance tests. code/firm/pipeline/: order and short-circuit on a traced event, static against dynamic, in C++20 and Rust; the chapter’s test checks that the static pipeline’s assembly contains no call and the dynamic one an indirect call.

Stretch. Stages that return a new event type (a decoded message into a book update), with the chain’s types checked by the compiler.

Sources and further reading

K. Driesen and U. Hölzle, “The direct cost of virtual function calls in C++”, OOPSLA 1996.
GCC manual, “Common function attributes” (cold, noinline, always_inline).
cppreference, consteval; attributes likely and unlikely.
C. Cook, “When a microsecond is an eternity”, CppCon 2017 (templates for configuration).

7.8 Exercises

Exercise 7.1 ★

From Figure 7.1, how many times more does virtual dispatch cost than CRTP on one message type, and on the mix?

Solution

Solution of Exercise 7.1.

On the committed measurement, $1.94/0.52 \approx 3.7$ times on one message type and $8.69/5.22 \approx 1.7$ times on the mix.

Exercise 7.2 ★

At 5 million messages a second, how much processing time a second does the dynamic pipeline cost over the static one?

Solution

Solution of Exercise 7.2.

$(7.26 - 1.14)\ \text{ns} \times 5 \times 10^6 \approx 31$ milliseconds of processing a second: 3% of a core, and six nanoseconds on every event’s latency.

Exercise 7.3 ★

Write the value of rescale(250, 2, 4) and rescale(2500, 4, 2), and say what rescale(1, 2, 20) does.

Solution

Solution of Exercise 7.3.

$250 \times 10^2 = 25\,000$ ; $2\,500 / 10^2 = 25$ . rescale(1, 2, 20): the target scale is out of range, so the unlikely branch calls the cold reporting function and returns 0.

Exercise 7.4 ★★

Why does the random mix slow down the CRTP dispatcher too, although it makes no indirect call?

Solution

Solution of Exercise 7.4.

The switch is compiled to a jump table (an indirect jump) or a chain of conditional branches; either depends on the message type, and on a random mix the predictor is wrong about three times in four.

Exercise 7.5 ★★

Count the instructions of Listing 7.4 that belong to each stage. Which stage’s object has disappeared entirely, and why?

Solution

Solution of Exercise 7.5.

Stage 1 (add the quantity) is the load of qty and the add; stage 2 the xor with the price and the store of acc; stage 3 the cmp with the limit and the jge; stage 4 the add to the sum in memory. The objects of stages 1 and 2 have disappeared: they have no data members, only code, which was inlined; stage 3’s limit and stage 4’s sum remain as loads and stores at offsets of the pipeline object.

Exercise 7.6 ★★

A strategy is chosen by a configuration file at start-up among three. How do you keep dispatch static?

Solution

Solution of Exercise 7.6.

Make the engine a template over the strategy type and instantiate it for each of the three; at start-up, read the configuration and call the run of the matching instantiation once. The single dispatch happens outside the hot loop.

Exercise 7.7 ★★★

Coding. Make one stage of the static pipeline [[gnu::noinline]], regenerate the assembly and measure. What changes in the listing and in the time per event?

Solution

Solution of Exercise 7.7.

The listing gains a call to the stage, with the event’s fields stored to memory before it and reloaded after, since the compiler can no longer see what the callee changes; the time per event rises toward the dynamic pipeline’s, without the indirect load of a table.

Exercise 7.8 ★★★

Find the flaw. “A virtual call costs 1.9 nanoseconds in our benchmark and our path makes five, so removing them saves ten nanoseconds at most.”

Solution

Solution of Exercise 7.8.

The benchmark measures a perfectly predicted call in a tight loop. It misses the mispredictions when targets vary, and above all the lost optimisation: a virtual call cannot be inlined, so values are spilled around it and nothing is folded across it. The four-stage pipeline lost six nanoseconds, not four calls’ worth of 1.9.

7.9 Problem: The Indirect Branch

Problem 7.1

Weekend problem — a plug-in architecture on the hot path

A trading engine was designed with plug-ins: the decoder, book, strategy and risk check are loaded at start-up and called through a base class. It handles four message types in a mix close to random. The team measures the alternatives of this chapter (Figure 7.1).

Part I — The measurement.

What do the three dispatchers cost per message on one type and on the mix?
Which effect makes the mix expensive for all three?
What does the four-stage pipeline cost static and dynamic?
Why does the pipeline’s cost not depend on the mix?

Part II — The mechanisms.

What does the dynamic pipeline do per stage that the static one does not (Listing 7.5)?
How many instructions does the static pipeline execute when the event passes every stage?
What optimisations became possible once the stages were inlined?
What would final on the plug-in classes change, and what not?

Part III — The redesign.

How can plug-ins chosen at start-up still be dispatched statically?
What is lost: what can no longer change without a rebuild?
How many program variants does the choice of three strategies and two risk checks produce?
How should the variants be tested?

Part IV — The verdict.

State the named result: the cost per message of virtual against static dispatch, predictable and not, and the four-stage pipeline’s cost both ways.
Why is the microbenchmark of a virtual call alone the wrong measure?
When is dynamic dispatch the right choice in a trading system?
What does a concept add to a template interface?
What is compile-time evaluation good for on the hot path?
Why keep error reporting out of line?
Why check the assembly rather than trust always_inline?
In one sentence: what should the compiler know when it compiles the hot path?

Solution

Solution of Problem 7.1.

One type: virtual 1.9, variant 1.8, CRTP $0.5\,\mathrm{n}\mathrm{s}$ ; mix: 8.7, 6.4 and $5.2\,\mathrm{n}\mathrm{s}$ (committed measurement).
Branch misprediction on the message type, which chooses the target.
About 1.1 and $7.3\,\mathrm{n}\mathrm{s}$ per event.
Its stages run in the same order for every event; the only data-dependent branch is the gate, the same in both.
It loads the next stage pointer, loads the object’s table, calls through it, tests the result and loops; registers are saved around each call.
Thirteen instructions.
Folding the stages’ arithmetic together, keeping the event in registers, removing the empty stage objects, and a single conditional branch for the gate.
It lets the compiler devirtualise calls through references of the concrete type; it does nothing for calls through the base class pointer that a plug-in architecture uses.
Make each plug-in a template parameter and instantiate the engine for each supported combination; choose the instantiation once at start-up.
New plug-ins cannot be loaded into a running binary; adding one needs a rebuild and a release.
$3 \times 2 = 6$ .
Each variant is built and runs the full test and replay suite; a matrix in continuous integration.
Named result. Virtual dispatch costs about 3.7 times CRTP when the message type is predictable and about 1.7 times on a random mix; the four-stage pipeline costs about $1.1\,\mathrm{n}\mathrm{s}$ per event composed statically and $7.3\,\mathrm{n}\mathrm{s}$ through virtual calls.
It measures the call alone, predicted, and not what the call prevents: inlining and the optimisations it enables.
Off the hot path (configuration, reporting, tools), and where the set of types is open (plug-ins loaded without a rebuild in a research engine).
A named requirement checked at the point of use: the error for a stage without bool on(E&) is one line.
Tables and constants (scales, lengths, lookup tables) built without start-up code and checked by static_assert.
To keep the hot function small and contiguous in the instruction cache, with the common case falling through.
Because always_inline is a request to a heuristic that can change between compiler versions; the assembly shows what happened.
Everything that is fixed for the life of the process: types, strategies, tables.

7.10 Interview questions

Interview question 7.1 ★ developer

How does a virtual function call work, and what does it cost?

Solution

Solution of Interview question 7.1.

The object holds a pointer to its class’s table of function pointers; the call loads the pointer, loads the entry and calls through it. Cost: two dependent loads and an indirect branch (cheap when predicted), and the loss of inlining.

What the interviewer is looking for: the vtable mechanism and the indirect cost.

Interview question 7.2 ★★ developer

Explain the curiously recurring template pattern and when you would use it.

Solution

Solution of Interview question 7.2.

A base class template parameterised by its derived class calls the derived class’s functions through static_cast<Derived&>(*this); dispatch is resolved at compile time and inlinable. Use it for a fixed family of behaviours on a hot path (handlers, policies).

What the interviewer is looking for: compile-time dispatch and its trade-off: no runtime substitution.

Interview question 7.3 ★★ developer

What is the difference between constexpr and consteval?

Solution

Solution of Interview question 7.3.

A constexpr function may be evaluated at compile time when its arguments are constants, and otherwise runs at run time; a consteval function must be evaluated at compile time, so a call that cannot be is an error.

What the interviewer is looking for: may versus must.

Interview question 7.4 ★★ developer

Why can inlining make code faster by more than the cost of the call it removes? When can it make code slower?

Solution

Solution of Interview question 7.4.

It exposes the callee’s body to the caller’s optimisations: constants propagate, values stay in registers, dead work disappears. It can make code slower by growing it beyond the instruction cache or the loop buffer, or by inlining rare code into a hot loop.

What the interviewer is looking for: optimisation across the boundary, and code size.

Interview question 7.5 ★★ developer

std::variant or a class hierarchy for message types: which would you choose on a hot path, and why?

Solution

Solution of Interview question 7.5.

A variant: the set of message types is closed, the object needs no heap allocation, dispatch is a jump on the index, and the handlers can be inlined. A hierarchy only if the set must be open.

What the interviewer is looking for: closed versus open sets of types, and allocation.

Interview question 7.6 ★★★ developer

Design a trading engine whose strategy is chosen at start-up but whose hot path has no indirect calls.

Solution

Solution of Interview question 7.6.

The engine is a template over its strategy (and other policies); each supported strategy is an instantiation compiled into the binary; the configuration selects one instantiation at start-up with a single dispatch outside the loop; the hot loop is fully static. Tested as a matrix.

What the interviewer is looking for: one dispatch at start-up, static thereafter.

Terms defined in this chapter

See all 2333 terms in the glossary