---
title: "Vector Instructions and Data-Parallel Code"
book: "Low-Latency Software"
subject: quant
language: en
chapter: 14
exercises: 8
source: https://one-course.com/books/quant/13/en/chapter/14-vector-instructions-and-data-parallel-code
---

# Chapter 14 — Vector Instructions and Data-Parallel Code

A parser that reads one byte at a time looks at a message the way a person reads a page letter by letter. In 2019 Geoff Langdale and Daniel Lemire published a JSON parser that looks at 32 or 64 bytes per instruction instead, and described it as the first standard-compliant JSON parser “to process gigabytes of data per second on a single core”, using a quarter or fewer of the instructions of a widely used reference parser. On the laptop of this book, the loop that looks for the end of a field one byte at a time scans about four bytes a nanosecond; the same search written with 256-bit [vector instructions](#def-ll-vector-instructions-and-data-parallel-code-simd) scans about eighty, some eighteen times faster, and splits a 159-byte FIX order into its sixteen fields in about $11\,\mathrm{n}\mathrm{s}$ instead of a hundred. Market data and order messages are text or packed binary, read field by field on every tick: this chapter shows what [vector instructions](#def-ll-vector-instructions-and-data-parallel-code-simd) are, when the compiler uses them by itself and what stops it, how to write them by hand with a scalar fallback that the tests hold them to, and how to lay out data so that they apply.

## 14.1 SIMD registers and instruction sets

**Definition 14.1 (SIMD, vector instruction).**

*SIMD* (single instruction, multiple data) is the execution of one operation on several data elements at once. A *vector instruction* is such an operation on a vector register holding several elements side by side: on x86-64, 16-byte `xmm` registers (SSE2, part of every x86-64 processor), 32-byte `ymm` registers (AVX2) and, on processors that have it, 64-byte `zmm` registers (AVX-512).

A 32-byte register holds 32 bytes, 16 two-byte integers, 8 four-byte integers or floats, or 4 doubles, and one instruction adds, compares or multiplies all of them. The instruction that matters most for parsing is the byte comparison: `VPCMPEQB` compares the 32 bytes of two `ymm` registers and sets each byte of the result to all ones where they are equal, and `VPMOVMSKB` gathers the top bit of each of those bytes into a 32-bit integer in an ordinary register. A message chunk compared with a register full of the delimiter byte therefore becomes a 32-bit mask with one bit per position, and “where is the first delimiter” becomes “how many trailing zeros does the mask have”, one more instruction ([Figure 14.1](#fig-ll-vector-instructions-and-data-parallel-code-mask)). The loop does in three instructions what the scalar loop does in 32 comparisons and 32 branches.

![Finding the field delimiters of a FIX message with one comparison of 32 bytes. The byte | stands for the SOH delimiter (byte 1). The comparison sets a byte to all ones where the message equals the delimiter; the mask instruction collects one bit per byte; counting trailing zeros gives each position in turn.](https://one-course.com/images/onecourse/chapters/quant-13/ll-vector-instructions-and-data-parallel-code/fig-ca6f27a78701.svg)

***Figure 14.1.** Finding the field delimiters of a FIX message with one comparison of 32 bytes. The byte `|` stands for the SOH delimiter (byte 1). The comparison sets a byte to all ones where the message equals the delimiter; the mask instruction collects one bit per byte; counting trailing zeros gives each position in turn.*

The laptop’s processor has SSE2 through AVX2 and fused multiply-add (One Quant Book 4, chapter 25), but not AVX-512, as its feature flags in `/proc/cpuinfo` show. That is the ordinary situation for a trading firm’s code: it is compiled once and runs on machines of several generations, so the widest instruction set cannot be assumed, and a binary that executes an AVX2 instruction on a processor without it dies with an illegal-instruction signal. Section 3 deals with that.

## 14.2 Auto-vectorisation and what blocks it

**Definition 14.2 (Auto-vectorisation).**

*Auto-vectorisation* is the compiler’s transformation of a scalar loop into [vector instructions](#def-ll-vector-instructions-and-data-parallel-code-simd) that process several iterations at once, done when it can prove the result unchanged and estimates it profitable.

The compiler vectorises by itself more often than people expect, and less often than they hope. GCC does it at `-O3`; from GCC 12 it also does it at `-O2`, with a cost model that accepts only very cheap transformations (the release notes), so a loop that GCC 11 at `-O2` leaves scalar may be vectorised by GCC 13 at the same flag: the compiler version is part of the performance. `-fopt-info-vec-all` makes it report each decision. [Listing 14.1](#lst-ll-vector-instructions-and-data-parallel-code-report) is its report on five small loops under the laptop’s GCC 11.

```text
# g++ 11.4.0: vectorisation report for ll_vecdemo.cpp (optimized and missed lines, notes dropped)
-O2                   (no loop vectorised, nothing reported)
-O3                   line 13: optimized: loop vectorized using 16 byte vectors
-O3                   line 13: optimized: loop versioned for vectorization because of possible aliasing
-O3                   line 20: missed: couldn't vectorize loop
-O3                   line 21: missed: not vectorized: no vectype for stmt: _4 = _3->qty;
-O3                   line 27: missed: couldn't vectorize loop
-O3                   line 27: missed: not vectorized: control flow in loop.
-O3                   line 34: optimized: loop vectorized using 16 byte vectors
-O3                   line 40: optimized: loop vectorized using 16 byte vectors
-O3 -mavx2 -mfma      line 13: optimized: loop vectorized using 32 byte vectors
-O3 -mavx2 -mfma      line 13: optimized: loop versioned for vectorization because of possible aliasing
-O3 -mavx2 -mfma      line 13: optimized: loop vectorized using 16 byte vectors
-O3 -mavx2 -mfma      line 20: missed: couldn't vectorize loop
-O3 -mavx2 -mfma      line 21: missed: not vectorized: no vectype for stmt: _4 = _3->qty;
-O3 -mavx2 -mfma      line 27: missed: couldn't vectorize loop
-O3 -mavx2 -mfma      line 27: missed: not vectorized: control flow in loop.
-O3 -mavx2 -mfma      line 34: optimized: loop vectorized using 32 byte vectors
-O3 -mavx2 -mfma      line 34: optimized: loop vectorized using 16 byte vectors
-O3 -mavx2 -mfma      line 40: optimized: loop vectorized using 32 byte vectors
```

***Listing 14.1.** The vectorisation report of GCC 11 for `ll_vecdemo.cpp`: the revaluation over columns (line 13), over records (20–21), a search that leaves early (27), and integer and double sums (34, 40). code/low-latency/14-vector-instructions-and-data-parallel-code/cpp/vecreport/gxx11.txt*

Each line is a lesson. At `-O2` nothing is vectorised. The revaluation over separate arrays is vectorised at `-O3`, two doubles per instruction, four with `-mavx2`, but only after the compiler “versioned” the loop: the output pointer might overlap an input, so it checks at run time and keeps a scalar copy of the loop for that case (`__restrict`, which promises no overlap, removes the check). The same computation over 80-byte records is not vectorised at all: the five fields of consecutive options are 80 bytes apart, and GCC 11 finds no vector type for such strided loads. The search is refused because it may leave the loop early (“control flow in loop”): GCC 11 does not vectorise a loop with an early exit. The integer sum is vectorised. The double sum is reported vectorised too, and its assembly shows why that means nothing: the additions stay in their original order, one element at a time, because floating-point addition is not associative and reordering it would change the result (chapter 8, where `-ffast-math` allowed it and changed the answer). Blockers, in short: possible aliasing, strided or scattered data, early exits, calls that cannot be inlined, and reductions whose order matters.

## 14.3 Intrinsics and CPU feature dispatch

**Definition 14.3 (Compiler intrinsic, CPU feature dispatch).**

A *compiler intrinsic* is a function the compiler knows and translates into one specific instruction (`_mm256_cmpeq_epi8` into `VPCMPEQB`), letting a program use an instruction without writing assembly while the compiler still allocates registers and schedules around it. *CPU feature dispatch* selects at run time, from the features the processor reports, which of several compiled versions of a function to call.

When the compiler will not vectorise a loop, intrinsics do it by hand. The build’s search for a byte loads 32 bytes, compares them with the broadcast delimiter, takes the mask and counts its trailing zeros; a message whose length is not a multiple of 32 ends with one more load that finishes exactly at its last byte and overlaps the previous block, with the bytes already seen shifted out of the mask, so that no byte beyond the message is ever read. That last point is not pedantry: a read past the end of a buffer that ends at a page boundary faults, and the sanitiser of chapter 8 reports any such read.

```cpp
__attribute__((target("avx2"))) inline std::size_t find_byte_avx2(const char* p, std::size_t n, char c) {
    if (n < 32) return find_byte_sse2(p, n, c);
    const __m256i needle = _mm256_set1_epi8(c);
    std::size_t i = 0;
    for (; i + 32 <= n; i += 32) {
        const __m256i v = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(p + i));
        const unsigned m = static_cast<unsigned>(_mm256_movemask_epi8(_mm256_cmpeq_epi8(v, needle)));
        if (m != 0) return i + static_cast<std::size_t>(__builtin_ctz(m));
    }
    if (i < n) {   // the last, overlapping block
        const __m256i v = _mm256_loadu_si256(reinterpret_cast<const __m256i*>(p + n - 32));
        const unsigned m = static_cast<unsigned>(_mm256_movemask_epi8(_mm256_cmpeq_epi8(v, needle))) >> (i - (n - 32));
        if (m != 0) return i + static_cast<std::size_t>(__builtin_ctz(m));
    }
    return n;
}
```

***Listing 14.2.** The AVX2 search for a byte, with an overlapping last block. code/firm/simdscan/cpp/firm_simdscan.hpp*

The function is compiled for AVX2 by a `target` attribute, without compiling the whole program for it, and is called only after a check. GCC’s `__builtin_cpu_supports("avx2")` returns non-zero when the running processor has the feature; the build checks once, at the first call, and keeps the answer. Chapter 8’s [function multiversioning](https://one-course.com/books/quant/13/en/chapter/8-c-for-latency-iii-the-compiler#def-ll-cpp-for-latency-iii-the-compiler-fmv) does the same automatically for a whole function; the explicit version keeps the choice visible and testable, and the tests call every version directly on the same inputs.

```cpp
enum class Level { scalar, sse2, avx2 };

inline Level detect() {
    __builtin_cpu_init();
    return __builtin_cpu_supports("avx2") && __builtin_cpu_supports("bmi") ? Level::avx2 : Level::sse2;
}

inline Level level() {
    static const Level l = detect();
    return l;
}

inline std::size_t find_byte(const char* p, std::size_t n, char c) {
    return level() == Level::avx2 ? find_byte_avx2(p, n, c) : find_byte_sse2(p, n, c);
}
```

***Listing 14.3.** Dispatch: detect the features once, then call the widest version. code/firm/simdscan/cpp/firm_simdscan.hpp*

Rust expresses the same contract in its types. An intrinsic-using function is declared `unsafe` with the attribute `target_feature` enabling `avx2`, and calling it is [sound](https://one-course.com/books/quant/13/en/chapter/9-rust-for-low-latency#def-ll-rust-for-low-latency-sound) only once the macro `is_x86_feature_detected!` has returned true for `avx2`, as the standard library’s own example puts it: the `unsafe` block “is safe because we’re testing that the `avx2` feature is indeed available on our CPU”.

```rust
/// The widest implementation this CPU supports, chosen at every call (the check is a cached load).
pub fn find_byte(s: &[u8], c: u8) -> usize {
    #[cfg(target_arch = "x86_64")]
    {
        if is_x86_feature_detected!("avx2") {
            // SAFETY: the running CPU supports AVX2, checked just above.
            return unsafe { x86::find_byte_avx2(s, c) };
        }
        x86::find_byte_sse2(s, c)
    }
    #[cfg(not(target_arch = "x86_64"))]
    find_byte_scalar(s, c)
}
```

***Listing 14.4.** The same dispatch in Rust: the unsafe call is guarded by the run-time check. code/firm/simdscan/rust/src/lib.rs*

Numbers need a second trick. Eight ASCII digits loaded as one 64-bit integer can be turned into their value without a loop: subtract the character `0` from every byte at once, then combine neighbouring digits into two-digit numbers in 16-bit lanes, those into four-digit numbers in 32-bit lanes, and those into the result, three multiplications in all. This is [SIMD](#def-ll-vector-instructions-and-data-parallel-code-simd) within an ordinary register, and it needs no special instruction; a version with SSE4.1 multiply-adds does the same in vector registers.

```cpp
// SIMD within a register: the first digit is the lowest byte (little-endian load). Combine neighbouring digits into
// 2-digit numbers in 16-bit lanes, those into 4-digit numbers in 32-bit lanes, and those into the 8-digit result.
inline std::uint32_t parse8_swar(const char* p) {
    std::uint64_t v;
    std::memcpy(&v, p, 8);
    v -= 0x3030303030303030ULL;                               // '0' from every byte
    v = (v * 10 + (v >> 8)) & 0x00FF00FF00FF00FFULL;         // d0*10 + d1, ...
    v = (v * 100 + (v >> 16)) & 0x0000FFFF0000FFFFULL;       // (d0d1)*100 + d2d3, ...
    v = (v * 10000 + (v >> 32)) & 0xFFFFFFFFULL;             // (d0..d3)*10000 + d4..d7
    return static_cast<std::uint32_t>(v);
}
```

***Listing 14.5.** Eight digits in three multiply-add steps inside one 64-bit register. code/firm/simdscan/cpp/firm_simdscan.hpp*

**Proposition 14.4 (The eight-digit combination).**

Let bytes $b_0,\dots,b_7$ hold digits $d_0,\dots,d_7$ (after subtracting the character zero), $b_0$ the lowest. After the step $v \leftarrow (10v + (v \gg 8)) \wedge \mathtt{0x00FF00FF00FF00FF}$, the 16-bit lane $k$ holds $10 d_{2k} + d_{2k+1}$; after the two analogous steps with 100 and 10 000, the low 32 bits hold $\sum_{j=0}^{7} d_j\, 10^{7-j}$.

**Proof.** Before the mask, byte $2k$ of $10v + (v \gg 8)$ is $10 d_{2k} + d_{2k+1} \le 99 < 256$, since the shift brings byte $2k+1$ down to position $2k$; no carry leaves the byte, and the mask discards the odd bytes, which hold unwanted sums. The same argument on 16-bit lanes (values up to $99 \times 100 + 99 < 2^{16}$) and on 32-bit lanes (up to $9\,999 \times 10\,000 +
9\,999 < 2^{32}$) gives the four-digit and eight-digit values, the earlier digit always in the higher place. ∎

On the laptop an eight-digit field costs about $2.0\,\mathrm{n}\mathrm{s}$ with the scalar loop, $1.0\,\mathrm{n}\mathrm{s}$ with the register trick and $0.7\,\mathrm{n}\mathrm{s}$ with SSE4.1, against about $5\,\mathrm{n}\mathrm{s}$ for the standard library’s `std::from_chars`, which also validates and handles any length. A price parsed into an integer number of ten-thousandths costs about $7\,\mathrm{n}\mathrm{s}$, and the same price read as a double by `strtod` about $43\,\mathrm{n}\mathrm{s}$. Lemire’s number-parsing paper makes the point for floating-point parsing: a 64-bit float needs at most 17 significant digits, which fit in one 64-bit word, and parsing done that way is several times faster than the C library’s.

## 14.4 Where vectorisation pays in a trading system

[Figure 14.2](#fig-ll-vector-instructions-and-data-parallel-code-scan) measures the search for a delimiter placed at the end of a message of each length. The scalar loop costs about a quarter of a nanosecond per byte; SSE2 about a fortieth, AVX2 about an eightieth, on top of a fraction of a nanosecond per call. Below 16 bytes both vector versions hand the message to the scalar loop and cost the same. Splitting a whole FIX order message into its fields (16 fields, 159 bytes) takes about $95\,\mathrm{n}\mathrm{s}$ one byte at a time and about $11\,\mathrm{n}\mathrm{s}$ with the mask loop, about nine times less.

![Time to find a delimiter at the end of a message, by message length: median of batches of a thousand searches of a message in the first-level cache. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: bench_simd.py.](https://one-course.com/images/onecourse/chapters/quant-13/ll-vector-instructions-and-data-parallel-code/fig-8eef8453ff93.svg)

***Figure 14.2.** Time to find a delimiter at the end of a message, by message length: median of batches of a thousand searches of a message in the first-level cache. Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: `bench_simd.py`.*

Where does this matter? Wherever bytes are examined one by one on the hot path: splitting FIX messages on their delimiter (chapter 15), finding the structural characters of JSON messages from venues that publish in it (chapter 17), validating and parsing numeric fields, checksums, and copying. It matters less for binary protocols whose fields sit at fixed offsets (chapter 16), where there is nothing to search for; there, [vector instructions](#def-ll-vector-instructions-and-data-parallel-code-simd) pay in bulk work on arrays instead: the risk checks of many orders, the revaluation of a book of positions, the statistics a strategy updates. Three conditions decide: enough elements to fill a register, the same operation on each, and data laid out contiguously. The first two are properties of the problem; the third is a design decision.

## 14.5 Structure of arrays

**Definition 14.5 (Structure of arrays).**

A *structure of arrays* stores a collection of records as one array per field, so that the same field of consecutive records is contiguous in memory; the usual layout, one record after another, is called an array of structures.

An options book revalued from its Greeks shows the difference ([Figure 14.3](#fig-ll-vector-instructions-and-data-parallel-code-layout)). Each option’s record carries an identifier, a symbol, its quantity and four Greeks, an expiry and some flags: 80 bytes, of which the revaluation $q(\Delta\,\delta S + \tfrac12
\Gamma\,\delta S^2 + \mathcal{V}\,\delta\sigma + \Theta\,\delta t)$ reads 40. Stored as records, four consecutive deltas lie 80 bytes apart and no instruction loads them together; stored as columns, they are 32 consecutive bytes, one load. Half of every [cache line](https://one-course.com/books/quant/13/en/chapter/3-memory-hierarchy-and-caches#def-ll-memory-hierarchy-and-caches-line) fetched for the records is wasted as well.

![The same options book as records and as columns. Revaluation reads five of the record’s fields; as columns, each field of four consecutive options fills one 256-bit register.](https://one-course.com/images/onecourse/chapters/quant-13/ll-vector-instructions-and-data-parallel-code/fig-c59d6e179c64.svg)

***Figure 14.3.** The same options book as records and as columns. Revaluation reads five of the record’s fields; as columns, each field of four consecutive options fills one 256-bit register.*

[Figure 14.4](#fig-ll-vector-instructions-and-data-parallel-code-reval) measures both layouts at three flag sets. With 1 024 options, which fit in the caches, the records cost about $0.8\,\mathrm{n}\mathrm{s}$ per option whatever the flags, since no compiler vectorises them; the columns cost the same at `-O2` (GCC 11 does not vectorise there), half at `-O3` (two doubles per instruction) and a quarter with `-mavx2 -mfma`, four doubles per instruction and one fused multiply-add for each multiplication and addition pair. With a million options the data no longer fit in the caches and the bytes moved decide: 88 bytes per option for records (the record and the result), 48 for columns, and the measured cost is about three times lower for columns whatever the flags, the vector width now mattering little.

![Revaluing an options book from its Greeks, stored as 80-byte records or as columns, compiled at three flag sets by GCC 11: in cache (1 024 options) and from memory (220 options, 80 MB of records). Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: bench_simd.py.](https://one-course.com/images/onecourse/chapters/quant-13/ll-vector-instructions-and-data-parallel-code/fig-ad0d216fb2a1.svg)

***Figure 14.4.** Revaluing an options book from its Greeks, stored as 80-byte records or as columns, compiled at three flag sets by GCC 11: in cache (1 024 options) and from memory ($2^{20}$ options, 80 MB of records). Measured on a laptop (Intel Core Ultra 7 155H) under WSL2, no isolated cores. Data: `bench_simd.py`.*

Columns have costs. Adding or removing one option touches every array; code that handles one option at a time (an order arriving, a fill) reads one element from each of several arrays, which is more [cache lines](https://one-course.com/books/quant/13/en/chapter/3-memory-hierarchy-and-caches#def-ll-memory-hierarchy-and-caches-line) than one record; and the layout is less natural to write. The usual compromise is to keep records where single items are handled and columns where many items are computed on, or blocks of columns (eight options’ deltas, then their gammas) that give both. A book of orders handled one message at a time (chapter 19) wants records; a risk engine revaluing every position on every move (chapter 22) wants columns.

## 14.6 Tutorial: scan, parse and lay out

**Goal.** Scan and parse with [vector instructions](#def-ll-vector-instructions-and-data-parallel-code-simd) behind a feature check, held byte for byte to a scalar reference; read the compiler’s decisions; measure layouts. **End state:** Figures [14.2](#fig-ll-vector-instructions-and-data-parallel-code-scan) and [14.4](#fig-ll-vector-instructions-and-data-parallel-code-reval), [Listing 14.1](#lst-ll-vector-instructions-and-data-parallel-code-report), and green tests in C++ and Rust.

1. **Hold the vector code to the scalar code.** The build’s C++ test runs every length from 0 to 200 bytes with delimiters at random positions (and none), twenty messages per length, through the scalar, SSE2, AVX2 and dispatched searches and the position finders, and requires identical answers; it parses 200 000 eight-digit numbers four ways. The buffers are exactly as long as the messages, so a run under AddressSanitizer catches any read past the end.
2. **Read the compiler’s report** : `python ll_vecreport.py` compiles `ll_vecdemo.cpp` at three flag sets and writes [Listing 14.1](#lst-ll-vector-instructions-and-data-parallel-code-report) for the installed GCC; run it with a newer GCC and compare the `-O2` lines.
3. **Measure** with `python bench_simd.py` : searches by length, the split of FIX messages, the parsers, and the revaluation built at three flag sets.
4. **The same in Rust** : `cargo test` in `code/firm/simdscan/rust` runs the twin’s scans for every length and its parsers on the same values.

**What to change next.** Add `__restrict` to the pointers of `reval_columns` and check that the report’s versioning line disappears; write the double sum with four separate accumulators and see whether the compiler vectorises it for real.

## 14.7 Build: the firm’s scanner

**Purpose.** The byte-level primitives of every text protocol the firm reads: the FIX engine splits messages on the delimiter with it (chapter 15), and the WebSocket client finds JSON’s structural characters and parses prices and sizes with it (chapter 17).

**Interface.** C++20 `firm::simdscan`: `find_byte(p, n, c)`, `positions(p, n, c, out, cap)`, `positions_any(p, n, set, m, out, cap)`, each with `_scalar`, `_sse2` (search) and `_avx2` versions; `parse8_scalar`, `parse8_swar`, `parse8_sse`, `is8digits`, `parse_uint(p, n, value, used)`, `parse_fixed(p, n, scale, out)`; `level()`. Rust `firm_simdscan`: `find_byte`, `positions`, `parse8_swar`, `parse_uint`, `parse_fixed`, with the scalar references.

**Rules.** Every vector routine returns what its scalar reference returns for every input, never reads outside $[p, p+n)$, and is called only after the run-time feature check; the AVX2 code is compiled by function attributes, never by compiling the program for AVX2; prices are parsed into integers of a declared scale, never into doubles.

**Acceptance tests.** `code/firm/simdscan/`: every length from 0 to 200 bytes against the scalar references in C++ and Rust, the capacity limit of the position finders respected, 200 000 eight-digit values parsed identically by every method, integers of 19 digits, prices with and without decimals, negative prices, and the rejection of malformed ones.

**Stretch.** An AVX-512 version selected by the same dispatch; a classifier for JSON’s structural characters with a table lookup (one shuffle instead of one comparison per character); a validator for eight digits inside the vector path.

Sources and further reading

- G. Langdale and D. Lemire, “Parsing gigabytes of JSON per second”, *The VLDB Journal* 28(6), 2019.
- D. Lemire, “Number parsing at a gigabyte per second”, *Software: Practice and Experience* 51(8), 2021.
- GCC 12 release notes (vectorisation at `-O2` ); GCC manual, x86 built-in functions ( `__builtin_cpu_supports` ).
- Intel 64 and IA-32 Architectures Software Developer’s Manual, instructions `PCMPEQB` and `PMOVMSKB` (as transcribed in the x86 instruction reference at felixcloutier.com).
- The Rust standard library, `core::arch` and `is_x86_feature_detected` .

## 14.8 Exercises

**Exercise 14.1 ★.**

How many doubles, 32-bit integers and bytes does a 256-bit register hold? How many 256-bit comparisons does it take to look at every byte of a 1 500-byte packet?

**Solution of Exercise 14.1.**

4 doubles, 8 integers of 32 bits, 32 bytes. $1\,500 = 46 \times 32 + 28$: 46 full blocks and one overlapping last block, 47 comparisons.

**Exercise 14.2 ★.**

The mask of a 32-byte block is `0x00041010` (bit 0 the first byte). Where are the delimiters in the block?

**Solution of Exercise 14.2.**

$\mathtt{0x00041010}$ has bits 4, 12 and 18 set: delimiters at bytes 4, 12 and 18 of the block.

**Exercise 14.3 ★.**

Apply [Proposition 14.4](#prop-ll-vector-instructions-and-data-parallel-code-swar) by hand to the digits `20260925`: give the 16-bit lanes after the first step and the 32-bit lanes after the second.

**Solution of Exercise 14.3.**

After the first step the 16-bit lanes hold 20, 26, 9 and 25; after the second the 32-bit lanes hold 2 026 and 925; the third gives $2\,026 \times 10\,000 + 925 = 20\,260\,925$.

**Exercise 14.4 ★★.**

A message of 70 bytes is scanned with 32-byte blocks and an overlapping last block. Which bytes does each load cover, how many bits must be shifted out of the last mask, and why is the result still correct if the delimiter is at byte 60?

**Solution of Exercise 14.4.**

Bytes 0–31 and 32–63, then the last load covers 38–69. After two full blocks the position is 64, so the last mask is shifted right by $64 - 38 = 26$ bits: its remaining bits are bytes 64–69. A delimiter at byte 60 is found in the second block, before the last load; the shift only discards bytes already examined.

**Exercise 14.5 ★★.**

Explain each of the three reasons the compiler gives in [Listing 14.1](#lst-ll-vector-instructions-and-data-parallel-code-report) for not vectorising, or for vectorising only after a check, and how you would remove each.

**Solution of Exercise 14.5.**

Possible aliasing: the output might overlap an input, so the loop is versioned with a run-time check; `__restrict` promises no overlap and removes it. No vector type for the record’s fields: the fields are 80 bytes apart; store them as columns. Control flow in the loop: the search may return early; write it with intrinsics, or search a whole block with a mask as the build does.

**Exercise 14.6 ★★.**

From the measured scan, estimate how long AVX2 takes to search the whole of a 4 096-byte buffer and what that is in bytes per nanosecond. What limits it once the buffer no longer fits in the first-level cache?

**Solution of Exercise 14.6.**

About $52\,\mathrm{n}\mathrm{s}$ on the committed measurement, some 79 bytes per nanosecond. Once the buffer is beyond the first-level cache, the rate at which the next levels deliver lines limits it, not the comparisons.

**Exercise 14.7 ★★★.**

*Coding.* Add `positions_any_sse2` to `firm.simdscan` (16-byte blocks, overlapping last block), use it in the dispatch when AVX2 is absent, and extend the C++ test to compare it with the scalar reference for every length.

**Solution of Exercise 14.7.**

Copy `positions_any_avx2` with 128-bit registers (`_mm_cmpeq_epi8` and `_mm_movemask_epi8`) and 16-byte blocks (the last one at $n - 16$, shifted by $i - (n - 16)$), fall back to the scalar loop below 16 bytes, make the dispatch return it at `Level::sse2`, and add a comparison with `positions_any_scalar` in the length loop of the test.

**Exercise 14.8 ★★★.**

*Find the flaw.* “Our build machine has AVX-512, so we compile with `-march=native`; it passed every test in continuous integration and ran fine on the new servers.”

**Solution of Exercise 14.8.**

`-march=native` compiles for the build machine’s processor, AVX-512 included, everywhere the compiler chooses to use it; the continuous-integration runners and the new servers happened to have it too. The first older production host executes an instruction it does not have and the process dies with an illegal-instruction signal. Compile for the oldest processor in the fleet and dispatch wider code at run time.

## 14.9 Problem: Thirty-Two Bytes at a Time

**Problem 14.1.**

Weekend problem — when does a vector scan pay?

The measured scan (`measured_scan.csv`) gives the cost of each search by message length; the split and parser measurements are in `measured_split.csv` and `measured_parse.csv`. A FIX order gateway receives execution reports of about 200 bytes with 20 fields, 200 000 a second at peak.

**Part I — The costs.**

1. From the measurements at 4 096 bytes, what does each method cost per byte?
2. Fit a line $a + bL$ to the AVX2 costs for $L \ge 32$ ( `ll_simd.fit` ). What are $a$ and $b$ ?
3. Charging the scalar loop only its cost per byte, above what length is the AVX2 search cheaper? And SSE2?
4. Why is charging the scalar loop no fixed cost generous to it?

**Part II — The gateway.**

5. What does splitting one 200-byte report cost with each method, scaled from the measured split?
6. How much core time per second does splitting take at peak, each way?
7. Each report carries four prices and quantities to parse. Using `parse_fixed` rather than `strtod` , what is saved per report?
8. Which is the larger saving per report: the split or the parsing?

**Part III — The limits.**

9. Why does the vector search not help a binary protocol with fields at fixed offsets?
10. What happens on a processor without AVX2?
11. Why must the last block overlap rather than read the 32 bytes beyond the start of the tail?
12. What would AVX-512 change in the cost per byte, and what would it not change?

**Part IV — The verdict.**

13. State the *named result* : the message length below which the vector scan does not repay its setup, from the measured cost per byte and per call.
14. Is any FIX field shorter than that?
15. What measurement would you add before trusting the break-even on a server?
16. Why are the scalar references kept in the build?
17. How would you test that the dispatch picks the scalar path on a machine without AVX2, on a machine that has it?
18. Where else in a trading system would the same thirty-two-bytes-at-a-time pattern apply?
19. What layout change would let the risk checks of chapter 22 use the same instructions?
20. In one sentence: when do [vector instructions](#def-ll-vector-instructions-and-data-parallel-code-simd) pay?

**Solution of Problem 14.1.**

1. About $0.22\,\mathrm{n}\mathrm{s}$ a byte for the scalar loop, $0.024\,\mathrm{n}\mathrm{s}$ for SSE2 and $0.013\,\mathrm{n}\mathrm{s}$ for AVX2.
2. On the committed run, $a \approx 0.3\,\mathrm{n}\mathrm{s}$ and $b \approx 0.0125\,\mathrm{n}\mathrm{s}$ per byte.
3. $L^* = a/(b_{\text{scalar}} - b) \approx 2$ bytes for AVX2 and about 8 for SSE2.
4. The scalar loop also pays per call (the call, the exit branch), so its line lies above the one through the origin, and the true crossing is earlier.
5. Scaling the measured split to 200 bytes: about $120\,\mathrm{n}\mathrm{s}$ one byte at a time, $14\,\mathrm{n}\mathrm{s}$ with AVX2.
6. $200\,000 \times 120\,\mathrm{n}\mathrm{s} \approx 24\,\mathrm{m}\mathrm{s}$ a second (2.4% of a core) against $2.8\,\mathrm{m}\mathrm{s}$ .
7. $4 \times (42.6 - 6.6) \approx 144\,\mathrm{n}\mathrm{s}$ per report.
8. The parsing: $144\,\mathrm{n}\mathrm{s}$ against about $106\,\mathrm{n}\mathrm{s}$ for the split.
9. There is nothing to search: fields are read at known offsets.
10. The dispatch calls the SSE2 version, which every x86-64 processor runs; nothing fails.
11. A load past the end of the message may cross into a page that is not mapped and fault, and it reads bytes that are not the message’s; the overlapping block reads only the message.
12. Twice the bytes per comparison, so roughly half the cost per byte on long buffers; nothing for short messages, where the fixed cost dominates.
13. **Named result.** The AVX2 search costs about $0.3\,\mathrm{n}\mathrm{s}$ per call plus $0.0125\,\mathrm{n}\mathrm{s}$ per byte against $0.22\,\mathrm{n}\mathrm{s}$ per byte for the scalar loop: it repays its setup from about 2 bytes (SSE2 from about 8), so no message is too short for it.
14. Single fields can be ( `54=1` is five bytes with its delimiter), but the scan runs over the whole message, never over one field.
15. The same benchmark on the server’s processor, with the real distribution of message lengths and with cold caches.
16. They define the correct answer, which the tests hold every vector version to, and they are the fallback.
17. Call each version directly in the tests, as the build does, and add a way to force the level (an environment variable read by `detect` ) so that the whole program can run on the fallback on a machine that has AVX2.
18. Checksums, copying, JSON and FIX parsing, searches over price levels, and bulk computations over positions.
19. Keep the fields the checks read (prices, quantities, limits) as columns.
20. When the same operation applies to many contiguous elements.

## 14.10 Interview questions

**Interview question 14.1 ★ developer.**

What is [SIMD](#def-ll-vector-instructions-and-data-parallel-code-simd)? Give an example of a loop that benefits and one that does not.

**Solution of Interview question 14.1.**

One instruction on several elements in a wide register. A loop adding two arrays of doubles element by element benefits; walking a linked list, or a loop whose every iteration depends on the previous one’s result, does not.

*What the interviewer is looking for: independent iterations on contiguous data.*

**Interview question 14.2 ★★ developer.**

How would you find the first occurrence of a byte in a buffer as fast as possible?

**Solution of Interview question 14.2.**

Compare 16 or 32 bytes at once with the byte broadcast into a vector register, take the mask of equal bytes, and count its trailing zeros; finish with an overlapping last block rather than reading past the end; choose the width at run time. Check against a scalar loop on every length.

*What the interviewer is looking for: compare, mask, count, and the tail.*

**Interview question 14.3 ★★ developer.**

What stops a compiler from vectorising a loop? How do you find out why it did not?

**Solution of Interview question 14.3.**

Possible aliasing, early exits, non-contiguous or strided data, calls that are not inlined, floating-point reductions whose order the language fixes, and a cost model that judges it unprofitable. Ask the compiler: `-fopt-info-vec-missed` in GCC gives the reason per loop; then read the assembly.

*What the interviewer is looking for: concrete blockers and the report flag.*

**Interview question 14.4 ★★ developer.**

Your binary uses AVX2 and must run on older machines. How do you ship it?

**Solution of Interview question 14.4.**

Compile for the oldest processor, put the AVX2 code in functions compiled for AVX2 by attribute (or [function multiversioning](https://one-course.com/books/quant/13/en/chapter/8-c-for-latency-iii-the-compiler#def-ll-cpp-for-latency-iii-the-compiler-fmv)), and choose at run time from the processor’s reported features; test both paths.

*What the interviewer is looking for: run-time dispatch, not a global flag.*

**Interview question 14.5 ★★ developer, researcher.**

Array of structures or [structure of arrays](#def-ll-vector-instructions-and-data-parallel-code-soa) for a position book that is revalued on every price move? Why?

**Solution of Interview question 14.5.**

[Structure of arrays](#def-ll-vector-instructions-and-data-parallel-code-soa) for the revaluation: each Greek of consecutive positions is contiguous, so it fills vector registers and fetches only the fields read. Records remain better for code that handles one position at a time; a hybrid of small blocks serves both.

*What the interviewer is looking for: access pattern decides the layout.*

**Interview question 14.6 ★★★ developer.**

Parse an ASCII decimal price into a fixed-point integer without a loop over characters. What must you validate?

**Solution of Interview question 14.6.**

Split at the decimal point, parse each part eight digits at a time inside a 64-bit register (subtract the character zero, then combine pairs, quads and octets with three multiply-and-mask steps), and scale the fraction by the missing decimals. Validate that every byte is a digit (a bit test on the whole word), the number of decimals, the range, and the sign.

*What the interviewer is looking for: the multiply-and-mask steps and the validation.*