Low-Latency Software · Technology

8C++ for Latency III: The Compiler

In July 2009 a Linux kernel driver was found to contain the lines struct sock *sk = tun->sk; and, a little further down, if (!tun) return POLLERR;. The check was meant to protect against a null pointer. The compiler had deleted it: the pointer had already been dereferenced, a null dereference is undefined behaviour, so the pointer could not be null and the test was dead code. On a machine where address zero could be mapped, the deletion became an exploit. The compiler did nothing wrong; it read the program’s contract literally. This chapter is about that contract and about the other levers the compiler offers a latency engineer: optimisation levels and target flags, profile-guided and link-time optimisation, and the habit that ties them together, reading the assembly and measuring every flag against a checksum.

8.1 Undefined behaviour as an optimisation contract

Definition 8.1 (Undefined behaviour)

Undefined behaviour is behaviour for which the C++ standard imposes no requirements: signed integer overflow, a null or dangling dereference, an out-of-bounds access, a data race, reading an object through a pointer of an unrelated type. The compiler may assume it never happens, and optimises every program as if it did not.

The assumption is where much of the optimiser’s power comes from. Because signed overflow cannot happen, x + 1 > x is true, a loop counter cannot wrap, and a loop’s trip count can be computed in advance; because dereferencing null cannot happen, a pointer dereferenced once is non-null afterwards. The assembly in Listings 8.1 and 8.2 shows both on this book’s compiler: the comparison compiles to “return 1” even without optimisation, and the null check of the 2009 pattern is gone at -O2.

	mov	eax, 1
	ret

Listing 8.1. plus_one_greater(int x), return x + 1 > x;, at -O2 (g++ 11.4): a constant. code/low-latency/08-cpp-for-latency-iii-the-compiler/cpp/asm/plus_one_greater_O2.s

	mov	eax, DWORD PTR [rdi]
	ret

Listing 8.2. first_then_check(const int* p): dereference, then test for null; the test is gone. code/low-latency/08-cpp-for-latency-iii-the-compiler/cpp/asm/first_then_check_O2.s

For a trading system the lesson is double. Undefined behaviour is not “the machine does something odd”; it is a license for the compiler to remove checks, reorder work and assume invariants that the code violates, and the result can change with the compiler version or a flag. And the same contract is what makes C++ fast: the idioms that give the optimiser facts (signed loop counters, no aliasing between unrelated types) are the ones that let it keep values in registers and vectorise. The tools that catch violations run in test builds: the undefined-behaviour sanitiser (-fsanitize=undefined) reports each overflow as it happens, the address sanitiser each invalid access.

8.2 Aliasing

Definition 8.2 (Strict aliasing)

Under the strict aliasing rule an object may be accessed only through an lvalue of its own type (or a closely related one: a signed or unsigned variant, a character type), so the compiler may assume that pointers to unrelated types never refer to the same memory. GCC applies the rule from -O2.

	mov	DWORD PTR [rdi], 1
	mov	eax, 1
	mov	DWORD PTR [rsi], 0x00000000
	ret

Listing 8.3. alias(int* i, float* f): store 1 through i, 0 through f, return *i; the compiler returns 1 without reloading. code/low-latency/08-cpp-for-latency-iii-the-compiler/cpp/asm/alias_O2.s

In Listing 8.3 the compiler returns 1 without reading *i again, because a store through a float* cannot change an int. Called with two pointers to the same four bytes, the function returns 1 where the memory holds 0. Decoders are where this bites: reading a price out of a byte buffer by casting the buffer’s address to std::int32_t* is an aliasing violation and, for unaligned fields, also undefined. The correct forms, std::memcpy into a local or C++20’s std::bit_cast, compile to a single load; the compiler knows what they do (chapter 16 builds its codecs this way).

8.3 Flags and target selection

The optimisation level is a bundle of passes: -O2 is the conventional release level, -O3 adds more aggressive inlining, cloning and vectorisation, and -Ofast adds -ffast-math. -march=native lets the compiler use every instruction of the build machine (AVX2 on this laptop), which makes the binary unfit for older machines; production builds name the target explicitly. -ffast-math allows the compiler to reorder floating-point operations as if they were associative and to assume there are no NaNs or infinities.

Definition 8.3 (Function multiversioning)

Function multiversioning compiles one function several times for different instruction sets and chooses a version at run time by the processor’s features: GCC’s target_clones("avx2", "default") attribute builds both and dispatches when the program loads.

Figure 8.1 measures the feed decoder of One Quant Book 1 with a per-message handler in a second translation unit, under seven flag sets, and a floating-point sum under three. On the decoder, -O3 was more than three times faster than -O2, profile-guided optimisation alone two and a half times, and the combination of everything nearly five times; -march=native and link-time optimisation alone changed almost nothing. On the float sum, -ffast-math was seven times faster and gave a different answer, because it summed in another order: the benchmark’s checksum caught it, and firm.flagbench does not rank a flag set whose output differs.

Figure 8.1. Left: the decode benchmark (Book 1’s 2 020-message sample decoded 300 times, a per-message handler in another translation unit) under seven flag sets; every set gave the same checksum. Right: summing

2^{20}

floats; with -ffast-math the sum changed. Best of five runs, g++ 11.4. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores, pinned to one CPU. Data: bench_flags.py.

8.4 Profile-guided and link-time optimisation

Definition 8.4 (Profile-guided optimisation)

In profile-guided optimisation (PGO) the program is built with instrumentation, run on a representative workload that records how often each branch goes each way and which values and calls are common, and rebuilt with the profile, so that the compiler inlines, unrolls and lays out code according to measured behaviour rather than guesses.

Definition 8.5 (Link-time optimisation)

In link-time optimisation (LTO) the compiler stores its intermediate representation in the object files and optimises the whole program again when linking, as if all translation units were one: functions can be inlined across files.

Figure 8.2. Profile-guided optimisation builds twice around a training run, whose workload decides what the compiler optimises for; link-time optimisation defers the optimisation of the whole program to the link.

The training run is the critical input of PGO. A profile taken on a quiet morning optimises the quiet-morning paths; a trading system must be trained on a replay of a busy, representative day (chapter 23), and retrained when the workload changes, or it will be optimised for the wrong branches. LTO’s benefit depends on the code’s structure: here the per-message handler was small and its cost was dominated by the decoder’s own calls, so LTO alone gained nothing. Both lengthen the build and make the binary depend on more than the source; both belong in the release pipeline, measured by the flag matrix on every release, not applied once and forgotten.

8.5 Reading assembly

The compiler’s output answers questions no benchmark can: whether a function was inlined, a loop vectorised, a check removed, a value kept in a register. g++ -O2 -S -masm=intel writes it for one file; objdump -d -M intel disassembles a binary; online compiler explorers show it line by line. The book’s listings of assembly are generated by scripts from tested sources, and their tests check properties (no call, a constant return) with whatever compiler is installed, never the exact bytes, which change with the compiler.

Method 8.6 (Choosing release flags)

Give the benchmark a checksum of its output and a realistic workload (a replayed day, not one message in a loop).
Build it under a matrix of flag sets, including profile-guided sets trained on a different day than the one measured.
Reject every set whose checksum differs from the reference build’s, whatever its speed.
Rank the rest by measured percentiles over repeated runs (chapter 25), and read the assembly of the hot functions to understand the winner.
Pin the chosen flags, compiler version and target in the build system; rerun the matrix on every compiler upgrade.

8.6 Tutorial: a flag matrix and three contracts

Goal. See the optimiser act on undefined behaviour, catch it with a sanitiser, and choose flags by measurement. End state: the three assembly listings, a sanitiser report, and Figure 8.1.

Three contracts. python ll_ub.py compiles ll_ub.cpp to assembly at -O0 and -O2 and writes the listings above.
Catch an overflow. ll_ub.ubsan(2147483647) builds a call of increment(x), return x + 1, with -fsanitize=undefined and runs it: “runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type int”.

Build with a profile. firm.flagbench builds a profile-guided set in three steps: instrumented build, training run, rebuild with the profile.

def build(sources, fs, out_dir, train_args=(), includes=()):
    out_dir = pathlib.Path(out_dir)
    out_dir.mkdir(parents=True, exist_ok=True)
    exe = out_dir / fs.name.replace(" ", "_").replace("+", "p").replace("/", "_")
    if not fs.pgo:
        _compile(sources, fs.flags, exe, includes)
        return exe
    prof = out_dir / (exe.name + ".prof")
    shutil.rmtree(prof, ignore_errors=True)
    _compile(sources, (*fs.flags, f"-fprofile-generate={prof}"), exe, includes)
    subprocess.run([str(exe), *map(str, train_args)], check=True, capture_output=True, cwd=u.ROOT)
    use = (f"-fprofile-use={prof}", "-fprofile-correction", "-Wno-missing-profile")
    _compile(sources, (*fs.flags, *use), exe, includes)
    return exe

Listing 8.4. Building a flag set, profile-guided or not. code/firm/flagbench/firm_flagbench.py

Run the matrix with python bench_flags.py: seven sets on the decoder, three on the float sum, each checked against the -O2 checksum.

What to change next. Find which of the passes that -O3 adds to -O2 makes the decoder faster by adding them one at a time to -O2; train the profile-guided build on only the first hundred messages of the sample and measure again.

8.7 Build: the flag matrix

Purpose. The firm’s release flags are chosen, and re-chosen at every compiler upgrade, by measurement with a correctness check, never by habit.

Interface. Python firm_flagbench: FlagSet(name, flags, pgo), build(sources, fs, out_dir, train_args, includes), run_matrix(sources, flag_sets, args, reference, repeats, cpus) returning rows with name, flags, checksum, time, ok and speed-up. The benchmark prints its checksum on its first line and its time per unit on its second.

Rules. A set whose checksum differs from the reference’s is marked not ok and never recommended; profile-guided sets are trained with the benchmark’s own arguments (or a separate training workload); every run is pinned and repeated.

Acceptance tests. code/firm/flagbench/tests/: a small program under -O2, -O0 and a profile-guided build (all ok) and under -ffast-math (not ok, its float sum differs).

Stretch. Separate training and measurement workloads; report percentiles instead of the best time; bisect the passes of -O3 automatically.

Sources and further reading

J. Corbet, “Fun with NULL pointers, part 1”, LWN.net, 20 July 2009.
C. Lattner, “What every C programmer should know about undefined behavior”, LLVM blog, 2011.
GCC 11.4 manual, “Options that control optimization” and “Common function attributes”.

8.8 Exercises

Exercise 8.1 ★

From Figure 8.1, what does the decoder cost per message at -O0, -O2 and with every optimisation, and what would each cost for 5 million messages a second?

Solution

Solution of Exercise 8.1.

On the committed measurement about 92, 11.6 and $3.1\,\mathrm{n}\mathrm{s}$ per message; at 5 million messages a second, 460, 58 and 16 milliseconds of processing a second: the unoptimised build would use half a core on decoding alone.

Exercise 8.2 ★

Which of these are undefined: INT_MAX + 1; UINT_MAX + 1u; reading a uint32_t from a byte buffer with std::memcpy; reading it by casting the buffer’s address to uint32_t*?

Solution

Solution of Exercise 8.2.

INT_MAX + 1 is undefined (signed overflow). UINT_MAX + 1u is defined: unsigned arithmetic wraps to 0. std::memcpy into a local is defined. The cast is undefined: it reads an object of a type the buffer never held (aliasing), and the address may be misaligned.

Exercise 8.3 ★

Why does plus_one_greater compile to a constant even at -O0, and why can the sanitiser not catch it?

Solution

Solution of Exercise 8.3.

The comparison is folded while the compiler simplifies expressions, before any optimisation level applies: with signed overflow impossible, x + 1 > x is always true. No addition is left in the program, so the sanitiser has nothing to instrument; it can only catch an overflow that is actually computed, as in increment.

Exercise 8.4 ★★

The exact sum of $1/k$ for $k = 1$ to $2^{20}$ is about 14.44. Which of the float sums of Figure 8.1 is closer to it, and does that make -ffast-math safe?

Solution

Solution of Exercise 8.4.

The exact sum is 14.440160. The -ffast-math result, 14.439274, is off by about 0.0009; the in-order sum, 14.403684, by 0.036, forty times more, because adding tiny terms to a large running sum loses them. Closer is not safe: the result now depends on the compiler, its version and the vector width, so two builds disagree, and the program can no longer be checked against a reference. Where accuracy matters, write the better algorithm (pairwise or compensated summation, One Quant Book 4, chapter 25) explicitly.

Exercise 8.5 ★★

A decoder reads a 32-bit price with *reinterpret_cast<const std::uint32_t*>(buf + 16). Name two rules it breaks and write the correct line.

Solution

Solution of Exercise 8.5.

It breaks the aliasing rule (reading bytes as a uint32_t object that does not exist) and the alignment rule (buf + 16 need not be 4-byte aligned), and it ignores the wire’s byte order. Correct: std::uint32_t v; std::memcpy(&v, buf + 16, 4); v = __builtin_bswap32(v); for a big-endian field on x86; it compiles to a load and a byte swap.

Exercise 8.6 ★★

A profile-guided build was trained on a replay of a quiet day and deployed on the day of an index rebalance. What can go wrong?

Solution

Solution of Exercise 8.6.

The profile tells the compiler that rebalance-day paths (bursts of executions, auction messages, one-sided flow) are cold, so it lays them out of line, does not inline them and may even optimise them for size: the day the firm most needs speed, the hot paths are the ones built as cold. Train on representative busy days, including the rare heavy ones.

Exercise 8.7 ★★★

Coding. Add a flag set -O2 -fno-strict-aliasing to the matrix and compile alias with it. What changes in the assembly, and in the decoder’s speed?

Solution

Solution of Exercise 8.7.

In alias the store through f is followed by a reload of *i (mov eax, DWORD PTR [rdi]) instead of the constant 1. The decoder assembles fields byte by byte and does not rely on type-based aliasing, so its code and speed should not change; the matrix measures it.

Exercise 8.8 ★★★

Find the flaw. “We compile with -Ofast -march=native on the build server; it was 30% faster in our benchmark.”

Solution

Solution of Exercise 8.8.

Three flaws: -Ofast includes -ffast-math, which changes floating-point results (the float sum changed); a single benchmark number with no checksum proves speed, not correctness; and -march=native on the build server targets the build server’s processor, which may have instructions the trading hosts lack. Name the target, keep IEEE semantics where results matter, and run the flag matrix with checksums on a production-shaped workload.

8.9 Problem: The Fast Build That Was Wrong

Problem 8.1

Weekend problem — a release flag review

A team’s release uses -O2. An engineer proposes -O3 -march=native -flto with profile-guided optimisation, another -Ofast. The team runs firm.flagbench (Figure 8.1).

Part I — The decoder.

What speed-up over -O2 does each flag set give?
Which single change gives most of the gain?
Why did link-time optimisation alone give nothing here?
Did any set change the decoder’s checksum?

Part II — The float sum.

What do the three sets give, in time and in value?
Why did -ffast-math change the value?
Which value is closer to the exact sum?
Why must the team still refuse -ffast-math for its pricing and risk code?

Part III — Undefined behaviour.

The decoder reads fields by casting. Why might it work at -O2 and break at -O3?
What does the undefined-behaviour sanitiser report for an overflowing increment?
In which builds should the sanitisers run?
What does the 2009 kernel bug teach a team that checks pointers after using them?

Part IV — The decision.

State the named result: the speed-up of the combined optimisations over -O2 on the decoder, and what -ffast-math did to the float sum.
Which flags should the release use, and what must accompany them?
How should the profile’s training day be chosen?
What does -march=native commit the firm to?
How would function multiversioning change that?
How often should the matrix be rerun?
Why check assembly properties rather than bytes in the tests?
In one sentence: what is a compiler flag worth without a checksum?

Solution

Solution of Problem 8.1.

-O0 0.13; -O3 3.7; -O2 -march=native 1.02; -O2 -flto 1.02; -O2 with PGO 2.6; everything together 4.8 (committed measurement).
-O3 alone, with profile-guided optimisation close behind.
The handler in the second file is cheap; the time is in the decoder and the per-message callback it makes, which are in the main file already.
No: every set produced the -O2 checksum.
-O2: $0.44\,\mathrm{n}\mathrm{s}$ per element and 14.4036837; -O3 -march=native: the same time and value; with -ffast-math: $0.064\,\mathrm{n}\mathrm{s}$ , seven times faster, and 14.4392738.
It allowed the compiler to reassociate the additions, summing several partial sums in vector registers, a different order with different rounding.
The -ffast-math value (exact 14.440160).
Its results must be reproducible and checkable against a reference, and -ffast-math also assumes no NaNs or infinities, which market data and failed calibrations produce.
Undefined behaviour gives no guarantee at any level: -O3 inlines and vectorises more, so an assumption that was harmless in one context becomes exploited in another.
“runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type int”.
In test and continuous-integration builds, on replayed production days; not in production binaries.
That a check after a use is dead code to the compiler: check before use, and treat compiler warnings and sanitiser reports as defects.
Named result. With -O3, -march=native, link-time and profile-guided optimisation the decoder ran 4.8 times faster than at -O2 with an identical checksum; -ffast-math made the float sum seven times faster and changed its value.
-O3 with profile-guided optimisation, an explicit target instead of native, no -ffast-math; accompanied by a pinned compiler version, a training workload under version control, and the matrix rerun on every release.
A replay of recent busy days, including the heaviest seen, distinct from the day used to measure.
To run only on processors with the build machine’s instruction set; a new server generation may be fine, an older one crashes with an illegal instruction.
It would compile the few hot vector functions for several targets and choose at load time, so the binary runs everywhere and still uses AVX2 where available.
On every compiler upgrade, flag change or significant code change, and periodically on the current workload.
Because the bytes change with the compiler version while the properties (a call inlined, a check present) are what the design relies on.
Nothing: faster and wrong is wrong.

8.10 Interview questions

Interview question 8.1 ★ developer

What is undefined behaviour, and why does it exist in C++?

Solution

Solution of Interview question 8.1.

Behaviour on which the standard imposes no requirement (signed overflow, invalid pointers, data races, aliasing violations). It exists so that compilers can assume it away and generate fast code for many machines without checks.

What the interviewer is looking for: that the compiler optimises on the assumption it never happens.

Interview question 8.2 ★★ developer

What is the strict aliasing rule? How do you read an integer from a network buffer correctly?

Solution

Solution of Interview question 8.2.

The compiler may assume that pointers to unrelated types never refer to the same memory. Read with std::memcpy into a local (or std::bit_cast on an array), then convert the byte order; it compiles to a load.

What the interviewer is looking for: memcpy or bit_cast, and byte order.

Interview question 8.3 ★★ developer

What does profile-guided optimisation do, and what are its risks?

Solution

Solution of Interview question 8.3.

It builds an instrumented binary, runs it on a training workload to record branch and value frequencies, and rebuilds using them for inlining, layout and unrolling. Risks: a non-representative training run optimises the wrong paths; the build depends on data that must be versioned.

What the interviewer is looking for: the training workload as the critical input.

Interview question 8.4 ★★ developer

Would you use -ffast-math in a trading system? Where, and where not?

Solution

Solution of Interview question 8.4.

Not for pricing, risk or anything checked against a reference; possibly for a self-contained numerical kernel whose tolerance is tested, where the speed matters and NaNs cannot occur. Better: write the vectorised or reassociated algorithm explicitly and keep IEEE semantics.

What the interviewer is looking for: reproducibility and the NaN assumption.

Interview question 8.5 ★★ developer

A check if (ptr == nullptr) disappears from the optimised binary. Why might that be?

Solution

Solution of Interview question 8.5.

The pointer was dereferenced earlier; since dereferencing null is undefined, the compiler concludes it is not null and removes the test. Move the check before the first use.

What the interviewer is looking for: the use-then-check pattern.

Interview question 8.6 ★★★ developer

How would you decide, and keep deciding, the compiler flags of a latency-critical binary?

Solution

Solution of Interview question 8.6.

A flag matrix on a realistic workload with a checksum, pinned and repeated, including profile-guided builds trained on separate data; reject any set that changes the output; read the hot assembly; pin the compiler and flags; rerun on every upgrade and release.

What the interviewer is looking for: measurement plus correctness, repeated over time.

Terms defined in this chapter

See all 2333 terms in the glossary