4Low Latency

Answer to Question 4.1.

It prints 24 16 64 192 on one line and 16 13 on the next.

On this platform double has alignment 8 and int has alignment 4. In A, c sits at 0, 7 padding bytes put d at 8, e is at 16, 3 more padding bytes put i at 20, and the total is 24. In B, the largest member comes first: d at 0, i at 8, c at 12, e at 13, then padding to a multiple of 8, which gives 16. alignas(64) forces the size of C to a multiple of 64, because each element of an array must be aligned, so three of them take 192.

The standard fixes the order of the members, that sizeof(C) is a multiple of 64, and that row is 3 * sizeof(C). The alignment of double and int, and so the other numbers, belong to the platform.

Answer to Question 4.2.

The program is undefined, so no output can be promised. On this compiler it printed 0, and the reader did not wait.

Both ready and value are read and written by two threads with no synchronisation, so this is a data race, and C++ calls any data race undefined behaviour. What happened here: at -O2, g++ turns on -ffinite-loops, which lets it assume the loop ends and delete it, so the reader prints value at once. With -fno-finite-loops the test run hung, spinning on a single hoisted read. At -O0 it printed 42. All three are observations on g++ 11.4, not promises.

volatile bool printed 42 at -O2, but ThreadSanitizer still reports the race, because volatile creates no ordering between threads and does not make access atomic. The fix is std::atomic<bool>: it printed 42 and ThreadSanitizer stayed silent.

Answer to Question 4.3.

It prints 8, 16, 8, 8, 8, 16, 16, 24, 24, 1. The three sizes for Option<NonZeroU64>, Option<Box<u64>> and Option<&[u8]> are promised; Option<Vec<u8>> and Option<bool> merely come out that way.

Option<u64> needs a tag, because every bit pattern of u64 is a valid value, so it takes 16 bytes with alignment 8. A Box and a reference are never null and NonZeroU64 is never zero, so None can use that spare pattern. The documentation of std::option guarantees this null pointer optimisation for exactly those families. &[u8] is a pointer and a length, 16 bytes. Vec<u8> is 24 bytes, and bool has spare patterns too, so the compiler uses them, but neither case is in the guaranteed list.

Answer to Question 4.4.

It no longer compiles: rustc reports error E0373, that the closure may outlive main’s borrow of prices.

thread::spawn requires a closure that is 'static, because the signature must hold for any caller, and a caller may drop the handle and never join. The borrow checker reads that signature. It does not reason about the join on the next line.

With move, the closure owns the vector, and main can no longer use it. The fix without a reference count is a scoped thread, Listing 4.26: the scope joins every thread it started before it returns, so a plain borrow is safe, and that run printed 300 3.

fn main() {
    let prices = vec![100_u64, 101, 99];
    let total = thread::scope(|s| {
        s.spawn(|| prices.iter().sum::<u64>()).join().unwrap()
    });
    println!("{} {}", total, prices.len());
}

Answer to Question 4.5.

The budget is 4000 cycles, or 8000 instructions. Eleven misses take 990 ns and fill it. Five misses take 450 ns, 45% of the budget, the time of 3600 instructions.

The arithmetic is $1000\text{ ns} \times 4 = 4000$ cycles, and $4000 \times 2 = 8000$ instructions. Then $1000 / 90 \approx 11$ misses, and $5 \times 90 = 450$ ns, which is $450 \times 4 = 1800$ cycles, or 3600 instructions.

The point of the exercise is the comparison. A hot path of a few hundred instructions is cheap, and a handful of cold pointers dominate it, so latency work is largely a matter of how few cache lines a message touches and whether they are already in cache. The figures here are the question’s assumptions; measure your own machine before quoting any.

Answer to Question 4.6.

This is false sharing. The eight 8-byte counters sit on one or two 64-byte cache lines, so every increment drags a line away from whichever core had it. Give each counter its own line, as in Listing 4.27; the struct grows from 64 to 512 bytes.

struct PaddedCounters {
    struct Slot {
        alignas(64) std::atomic<std::uint64_t> hits;
    };
    Slot slot[8];
};
PaddedCounters own_line;

Cache coherence works per line, not per variable. A locked increment needs its core to own the line exclusively, so the line moves between cores on nearly every operation, even though the threads share no data. Measured once here, as an illustration, on an Intel Core Ultra 7 155H under WSL2 with g++ 11.4 and 4 unpinned threads: about 60 ns per increment on the shared line, about 5 ns each on its own line.

The fix costs eight times the memory and eight lines of cache footprint, and a reader who sums all the counters now takes up to eight misses instead of one. On some Intel processors a spatial prefetcher pulls pairs of lines, so some libraries pad to 128 bytes. To confirm, compare the two versions as threads are added, and on hardware that supports it use perf c2c, which reports the contended lines. A VM may not expose those counters.

Answer to Question 4.7.

All three loads, the relaxed and release stores, and ++plain are ordinary instructions (movq, or an unlocked add). The sequentially consistent store is xchgq, and the relaxed fetch_add is a lock-prefixed add.

Two separate needs explain the pattern. Atomicity: a read-modify-write has to hold the line for the whole operation, so it is locked whatever order you ask for, and “relaxed” does not make it cheap. Ordering: x86-64 only lets a later load overtake an earlier buffered store, so only a sequentially consistent store must do more, and xchg is implicitly locked and drains the store buffer. Acquire and release need no instruction at all. Their remaining job is to stop the compiler moving things.

On a weakly ordered processor those orders do cost instructions. The published mapping for ARMv7 turns a load-acquire into ldr; dmb ish and a store-release into dmb ish; str, and POWER uses isync and lwsync forms.

Answer to Question 4.8.

List a visits memory in address order, while b visits it in random order, so nearly every step of b is a cache miss.

Nodes of a are allocated in list order, so neighbours sit next to each other and the prefetcher keeps up. b allocates nodes in shuffled order, and sort only relinks them. It does not move them. So the list order is sorted while the addresses are shuffled.

There are two checks that need no counters. First, measure how often successive nodes are within 64 bytes of each other: the listing’s program found a share of 1.0000 for a and 0.0000 for b. Second, shrink the list and watch the gap close as it starts to fit in cache. Measured once here on an Intel Core Ultra 7 155H under WSL2, with g++ 11.4, in ns per node for a and b: about 1.2 and 2.5 at $n = 2000$, 1.3 and 5.5 at $20\,000$, 3 and 18 at $200\,000$, 3 and 150 at two million.

The change is to sort a std::vector, which moves the values, or to rebuild the list after sorting if a list is really needed.

Answer to Question 4.9.

The counts are: string 15, 0; string 16, 1; push 1000, 11; reserved, 1; function 16, 0; function 24, 1; shared new, 2; make_shared, 1; map 10, 10.

The string uses its small-string buffer up to 15 characters here. The vector doubles from capacity 1 to 1024, so that is 11 allocations, and reserve replaces them with one. std::function keeps a small trivially copyable callable inside itself, which holds the 16-byte lambda but not the 24-byte one. shared_ptr<long>(new long(1)) allocates the object, then a control block, and make_shared puts both in one allocation. A map allocates one node per element.

The standard leaves all of these sizes to the library: the small-string capacity, the std::function buffer and the growth factor. A different library can print different numbers. The per-node map count and the two allocations for shared_ptr<long>(new long(1)) follow from what those types must do on any common implementation, but neither is a promise, and the standard even allows a compiler to merge or remove new calls. This compiler did neither here.

Answer to Question 4.10.

ts_copy is correct and ts_cast is undefined behaviour, yet at -O2 both compile to the same single instruction, movq 8(%rdi), %rax, with no call.

ts_cast fails on alignment. Header has alignment 8 and the address is 3 bytes past an 8-aligned one, so no Header can live there, even under C++20’s rule that a byte array implicitly creates objects where that would make a program defined. So the read goes through a type the storage does not hold, which the type-accessibility rule makes undefined. Building with -fsanitize=alignment reports a misaligned address on line 12 and nothing on the memcpy line.

It seems to work because x86-64 tolerates an unaligned mov and the compiler happened to use one. Nothing obliges it to: once the code is undefined, the compiler may assume alignment when it optimises, including when it vectorises a loop over such pointers.

memcpy of a known small size costs nothing, as the identical instruction shows, so there is no performance reason to prefer the cast.

Answer to Question 4.11.

The compiler deleted the work. The result of work is unused and the function has no side effects, so main contains no call to it and no loop. What remains is the time between two clock readings: 67 to 69 ns in our runs.

Listing 4.28 forces the work to happen: noinline stops the call disappearing, the empty asm statements hide the input and keep the result, and main’s code then does contain the call.

[[gnu::noinline]] std::uint64_t work(std::uint64_t n) {
    std::uint64_t h = 1;
    for (std::uint64_t i = 0; i < n; ++i) h = h * 31 + i;
    return h;
}

template <class T>
inline void keep(const T& value) {
    asm volatile("" : : "r,m"(value) : "memory");
}

int main() {
    std::vector<long long> ns;
    for (int run = 0; run < 1000; ++run) {
        std::uint64_t n = 100000;
        asm volatile("" : "+r"(n));
        auto t0 = std::chrono::steady_clock::now();
        auto h = work(n);
        keep(h);
        auto t1 = std::chrono::steady_clock::now();
        using std::chrono::nanoseconds;
        ns.push_back(std::chrono::duration_cast<nanoseconds>(t1 - t0).count());
    }
    std::sort(ns.begin(), ns.end());
    std::printf("median %lld ns, p99 %lld ns, max %lld ns\n",
                ns[500], ns[990], ns[999]);
}

The other faults: one run gives no distribution, so collect many and report median, tail and maximum. The first run is cold. A latency benchmark that loops tightly also warms caches and branch predictors in a way that a real message arriving rarely will not. The thread is unpinned. On our machine this version printed a median near 65 microseconds and a maximum several times higher, for 100 000 iterations.

rdtsc is not serialising: it can read the counter before earlier instructions finish, and later ones can start before the read. So the usual pairing is lfence; rdtsc at the start, and rdtscp; lfence at the end. You must also convert ticks to time, which needs the counter’s rate, so confirm that rate is constant on your processor.

Answer to Question 4.12.

It is not correct. There is a data race on payload, so the behaviour is undefined, however many runs print 42. On ARM or POWER the wrong order is also allowed by the hardware.

A relaxed store and load make the flag itself atomic, but create no happens-before between the threads, so the plain write and the plain read of payload conflict. ThreadSanitizer reports it. On x86-64 the hardware does keep two stores in order, and two loads in order, which is why the runs look fine. Even there, the compiler may still reorder the plain write and the relaxed store, since nothing forbids it. On ARM and POWER this message-passing shape can really be observed out of order without barriers.

The fix is store(true, release) in the writer and load(acquire) in the reader. The release store synchronises with the acquire load that reads it, so the write of payload happens before the read. With those two changes ThreadSanitizer is silent and the program prints 42. On x86-64 the machine code gains no fence, as acquire and release are plain moves there.

Answer to Question 4.13.

The correctness fault: lock and unlock use relaxed order, so they protect nothing under the C++ rules. The performance fault: the waiters spin on exchange, a write, so the lock’s cache line bounces between them.

A lock must make the previous holder’s critical section happen before the next one’s. Relaxed orders give no such edge, so the increments of counter race. ThreadSanitizer reports it, even though the total printed 80 000 on x86-64, where exchange is a locked instruction and the compiler made no harmful move this time. The fix: acquire on the successful exchange, release on the store in unlock.

Under contention each failed exchange demands the line in exclusive state, so waiters slow the holder too. The usual cure is to spin on a relaxed load, which lets all waiters share the line, and try the exchange only when the lock looks free, with pause in the wait loop. Listing 4.29 is that version: it prints 80 000 and ThreadSanitizer is silent. pause tells the processor this is a spin-wait, which avoids a severe penalty on leaving the loop and saves power.

class SpinLock {
    std::atomic<bool> held_{false};

public:
    void lock() {
        for (;;) {
            if (!held_.exchange(true, std::memory_order_acquire)) return;
            while (held_.load(std::memory_order_relaxed)) _mm_pause();
        }
    }
    void unlock() { held_.store(false, std::memory_order_release); }
};

Answer to Question 4.14.

It means that every operation on the 16- and 24-byte types is a call into libatomic, with no promise of progress, so neither belongs on a hot path. The program prints 1 1, 0 0, 0 0, then 99.5 100.5.

For Quote, the binary has undefined symbols __atomic_load_16 and __atomic_store_16, and without -latomic the link fails on them. So every read is a function call, and is_lock_free() returning 0 says you have no promise of progress. libatomic has a fallback built on a table of mutexes hashed by address, so a reader could wait behind a descheduled thread. Even when the 16-byte compare-and-swap is used, that instruction always performs a write cycle on its target, so a 16-byte load done that way would take the line exclusively, and readers would contend with each other.

Instead, make the quote fit in 8 bytes: two 32-bit prices in integer ticks, and one plain move publishes both. If it cannot fit, use a sequence lock, or publish a pointer to an immutable snapshot.

Answer to Question 4.15.

Here is the table, checked by compiling every combination with rustc 1.97.

The rule is that T is Sync exactly when &T is Send. Rc has an unsynchronised count, so it is neither. Cell and RefCell may move to another thread, since ownership is exclusive, but cannot be shared. Arc<T> needs T: Send + Sync, so Arc<Cell> fails. Mutex supplies Sync from Send, so it rescues Cell, but it cannot rescue Rc, whose clones may live outside the mutex. A reference to a Cell is not Send, because Cell is not Sync. Raw pointers opt out by default. MutexGuard must unlock on the thread that locked, so it is not Send, while sharing a reference to it is harmless.

Answer to Question 4.16.

It can print any value from 2 up to 4 000 000, and in practice a value far below 4 000 000: between about one and 1.35 million in our runs. There is no data race and no undefined behaviour. This is a race condition, which safe Rust does not prevent.

Each load and each store is atomic, so no access tears and the outcome is defined. But the read and the write are separate operations, so an increment by another thread between them is overwritten. That is the difference: a data race is an unsynchronised conflicting access, and Rust excludes those; a lost update is a logic error, and it does not.

The lower bound is 2. Take the last store to COUNT in its modification order, made by thread $T$. It was $T$’s final iteration, and $T$ had already stored once, so coherence forbids its read from seeing the initial 0; every other stored value is at least 1. So the final value is at least 2. An exhaustive search over interleavings for small cases confirms that 2 is reached.

The fix is one call, COUNT.fetch_add(1, Relaxed), which printed exactly 4 000 000.

Answer to Question 4.17.

Vec::new 0, with_capacity(8) 1, String::new 0, to_string 1, Box<()> 0, Box<u64> 1, 1000 pushes 9, clear and refill 0, Arc::clone 0.

The documentation promises several of these. Vec::new does not allocate until elements are pushed. Box::new does not allocate for a zero-sized type. clear leaves the capacity alone, and a thousand elements fit in the capacity reserved earlier. Arc::clone only bumps a count.

The 9 is not promised. It comes from one allocation for capacity 4 and eight reallocations up to 1024, but Vec explicitly gives no guarantee about its growth strategy, only amortised constant-time push. to_string on an integer needs a heap String, so that 1 is what you should expect, without being a contract about the count.

Answer to Question 4.18.

sum_b and pick_f still have a bounds check. sum_c and sum_d have one check at the start, from the slice and the assert!, and none in the loop. sum_a, diff_e and pick_g have no panic check at all. None of it is guaranteed.

The optimiser removes a check only when it can prove the index in range. In sum_a the range is the slice’s own length. In sum_b, nothing relates n to the length, so the check stays, and the loop must panic at the right element. In sum_c the reslice makes the length exactly n. In sum_d, the assert! tells the optimiser that the bound holds. In diff_e both $i$ and $i - 1$ are provably in range. pick_f masks to 0 through 7, but the slice could be shorter than 8, so its check remains, while pick_g takes an array of exactly 8, so the mask proves it.

These results come from reading the assembly of rustc 1.97 with -C opt-level=3. Bounds-check elimination is an optimisation, not a language feature, so another version could differ. Check by reading the output when it matters.

Answer to Question 4.19.

With 4 KiB pages the TLB covers 8 MiB, the miss rate is about 99.9%, and translation costs about 30 ns per read. With 2 MiB pages it covers 4 GiB, the miss rate is 50%, and the cost is 15 ns. The last-level entries take 16 MiB and 32 KiB respectively.

The working: $2048 \times 4\text{ KiB} = 8$ MiB, against 8 GiB, so a random read hits only about once in a thousand, and $0.999 \times 30 \approx 30$ ns. At 2 MiB, $2048 \times 2\text{ MiB} = 4$ GiB, half the table, so $0.5 \times 30 = 15$ ns. The table has $2^{21}$ pages at 4 KiB, which is 16 MiB of entries, and only 4096 at 2 MiB, 32 KiB. So the entries themselves fit in cache far more easily, and the real walk gets cheaper than the question’s flat 30 ns assumes.

The catches: explicitly reserved huge pages (the hugetlb pool) are best reserved at boot, as later reservations can fail when memory is fragmented. Mapping them needs privileges or configuration. Transparent huge pages avoid the reservation, but a fault can stall on compaction if the mode allows it, and a kernel daemon collapses pages in the background at times you do not choose. And a 2 MiB page means whole-page granularity for protection and for placement on a NUMA node.

Answer to Question 4.20.

In (a) and (b), both registers can end at 0, in C++20 and on x86-64. In (c) they cannot. Acquire and release are no help here, and the instruction that makes the difference is the xchg in the sequentially consistent store.

In any interleaving of the four operations that respects each thread’s order, the last operation is a load, and by then both stores have run, so it reads 1; a small enumeration confirms it. That is what (c) promises. Release and acquire only order a release with an acquire that reads its value. Here each load reads a value the other thread has not yet stored, so no synchronisation arises, and the language allows both zeros.

The hardware does it too. On x86-64 each store can wait in a FIFO store buffer while the following load, from the other variable, goes to memory. A locked instruction such as xchg drains the buffer first.

To show it, run the pair in a tight loop with a release of both threads per round, and count double zeros. Our run, on an Intel Core Ultra 7 155H under WSL2 with g++ 11.4 at -O2, gave about 3600 for relaxed and 4400 for acquire-release, in 200 000 rounds, and 0 for sequentially consistent. The count varies by run; the rule does not.

Answer to Question 4.21.

Listing 4.30 is the ring buffer. Each side owns one index: load your own with relaxed, load the other’s with acquire, write the slot, then publish your index with release.

template <class T, std::size_t N>
class Spsc {
    static_assert(std::has_single_bit(N));
    alignas(64) std::atomic<std::size_t> head_{0};  // written by the consumer only
    alignas(64) std::atomic<std::size_t> tail_{0};  // written by the producer only
    alignas(64) T slots_[N];

public:
    bool push(const T& v) {
        const std::size_t t = tail_.load(std::memory_order_relaxed);
        if (t - head_.load(std::memory_order_acquire) == N) return false;
        slots_[t & (N - 1)] = v;
        tail_.store(t + 1, std::memory_order_release);
        return true;
    }
    bool pop(T& out) {
        const std::size_t h = head_.load(std::memory_order_relaxed);
        if (h == tail_.load(std::memory_order_acquire)) return false;
        out = slots_[h & (N - 1)];
        head_.store(h + 1, std::memory_order_release);
        return true;
    }
};

The defence, each point confirmed by relaxing that one order and running ThreadSanitizer, which then reports a race:

• tail_.store(release) in push: publishes the slot. Relaxed, the consumer may read the slot before the write is visible.
• tail_.load(acquire) in pop: pairs with that release. Relaxed, the consumer’s read of the slot is not ordered after the producer’s write.
• head_.store(release) in pop: hands the slot back. Relaxed, the producer may overwrite the slot while the consumer’s read is still unfinished.
• head_.load(acquire) in push: pairs with that one.

A thread’s load of its own index can be relaxed, as no other thread writes it. No read-modify-write is needed, as each index has a single writer, so x86-64 pays no locked instruction at all. The indices run freely and are masked only to pick a slot, so all $N$ slots are usable (the test pushes 8 into an 8-slot ring, and the ninth fails) and t - h stays correct across wrap-around.

Answer to Question 4.22.

The two mechanisms are false sharing between the indices and needless reads of the other side’s index. The further change gives each side a private copy of the other’s index, as in Listing 4.31.

struct Cached {
    alignas(64) std::atomic<std::size_t> head{0};
    std::size_t tail_seen = 0;  // consumer's private copy of tail
    alignas(64) std::atomic<std::size_t> tail{0};
    std::size_t head_seen = 0;  // producer's private copy of head
    alignas(64) long slots[N];

    bool push(long v) {
        const std::size_t t = tail.load(std::memory_order_relaxed);
        if (t - head_seen == N) {
            head_seen = head.load(std::memory_order_acquire);
            if (t - head_seen == N) return false;
        }
        slots[t & (N - 1)] = v;
        tail.store(t + 1, std::memory_order_release);
        return true;
    }
    bool pop(long& out) {
        const std::size_t h = head.load(std::memory_order_relaxed);
        if (h == tail_seen) {
            tail_seen = tail.load(std::memory_order_acquire);
            if (h == tail_seen) return false;
        }
        out = slots[h & (N - 1)];
        head.store(h + 1, std::memory_order_release);
        return true;
    }
};

In the listing, head, tail and the first slots share one line, so every store by one thread takes that line from the other, which needs it for its next load. Padding gives each index its own line. But each operation still reads the other side’s index, and because that line is written constantly, each read is a miss. With a private copy, the producer rereads head only when the queue looks full, and the consumer rereads tail only when it looks empty. The copy lives on the owner’s line, written only by the owner, so it costs nothing to keep.

The cost is small: a few more lines of code, and one more branch. A stale copy can only make the queue look fuller or emptier than it is, and the slow path then checks the truth, so the memory orders and the correctness are unchanged (ThreadSanitizer is silent on all three).

Measured a few times here, as an illustration, on an Intel Core Ultra 7 155H under WSL2 with g++ 11.4, in unpinned threads and with a noisy result: adjacent 13 to 24 ns per item, padded about 9.5, cached about 3. To confirm, run all three on pinned cores and compare, and use perf c2c where the hardware allows it.

Answer to Question 4.23.

It can first go wrong after about 72 minutes, when tail wraps past $2^{32}$, and only if more than 296 items are in the queue across that moment. tail - head is fine. The smallest fix is a power-of-two capacity, such as 1024.

Unsigned arithmetic wraps cleanly, so tail - head is right across the wrap, and 72 minutes is $2^{32} / 10^6$ seconds. The bug is in the slot index. $2^{32} \bmod 1000 = 296$, so the index goes $\dots, 2^{32} - 1$ to 0 while % capacity jumps from slot 295 to slot 0, skipping 704 slots. If the items straddling the jump number more than 296, the new items land on slots still in use. The program in the file holds 500 across the jump, 400 before and 100 after, and reports 100 wrong of 500.

With capacity 1024, $2^{32}$ is a multiple of the capacity, so the slot sequence is continuous, and the same run gives 0 wrong. So does using 64-bit indices with capacity 1000: they would take about 584 years to wrap at a billion messages a second.

This passes tests because it takes hours to reach, and at most moments the queue is short, so the condition is rarely met even then.

Answer to Question 4.24.

Use a log-linear histogram: 64 buckets per doubling, 1600 buckets in all, 12 800 bytes at 8 bytes each, with a relative error of at most $1/64 \approx 1.6\%$.

From 128 up, each power-of-two range is divided into 64 equal parts, so a bucket’s width over its lower bound is at most $1/64$. Below 128, there is one bucket per value. That gives 2% with an easy power of two to spare; 32 parts would give 3.1%, too coarse. Values up to $2^{30}$, about 1.07 s, need $(30 - 6 + 1) \times 64 = 1600$ buckets. One bucket per nanosecond would need $2^{30}$ counters, 8 GiB.

    static constexpr int kSubBits = 6;  // 64 buckets per doubling
    static constexpr int kMaxBits = 30;  // up to about 1.07 s in nanoseconds
    static constexpr std::size_t kSub = std::size_t{1} << kSubBits;

public:
    static constexpr std::size_t kBuckets = (kMaxBits - kSubBits + 1) * kSub;

    static std::size_t index(std::uint64_t v) {
        if (v >= (std::uint64_t{1} << kMaxBits)) return kBuckets - 1;  // saturate
        const int bits = std::bit_width(v);
        if (bits <= kSubBits) return static_cast<std::size_t>(v);
        const int shift = bits - kSubBits - 1;
        return (static_cast<std::size_t>(shift) + 1) * kSub
               + static_cast<std::size_t>((v >> shift) - kSub);
    }
    static std::uint64_t lower_bound(std::size_t i) {
        if (i < 2 * kSub) return i;
        const int shift = static_cast<int>(i / kSub) - 1;
        return static_cast<std::uint64_t>(kSub + i % kSub) << shift;
    }
    void record(std::uint64_t v) { ++counts_[index(v)]; }

The largest relative error found over a dense sweep of values was 1.53%. Recording the values 1 to one million and reading the 99th percentile gave 983 040 against a true 990 000, which is 0.70% low, because a percentile is reported as its bucket’s lower bound.

The work per record is constant: one bit-width, a shift and an increment, with no loop. The array is fixed, so there is no allocation.

Answer to Question 4.25.

Our run printed malloc 1, first pass 16383, second pass 0 and then vector 16385, first pass 0. So malloc barely touches memory, the first touch of each page faults, and the vector’s faults all happen in its constructor, which zeroes the memory.

64 MiB is 16 384 pages of 4 KiB. A large malloc obtains address space and no physical memory. Each page gets a minor fault on first touch, so the first pass pays them all and the second pays none. Building the vector value-initialises every byte, which touches every page, so the faults move there.

So the first messages to reach a cold buffer each take a page fault, on top of cold caches. At start-up: map memory with MAP_POPULATE or touch every page yourself, call mlockall with MCL_CURRENT | MCL_FUTURE to keep it there, and run some fake messages through the path to warm it.

On two sockets, the default policy allocates a page on the node of the processor that first faults it, at fault time. So the vector built in main sits on main’s node, and the pinned thread on the other socket pays a remote access on every read, unless automatic NUMA balancing later migrates the pages, at a cost of its own and at a time you do not choose. Construct and touch the data on the pinned thread.

Answer to Question 4.26.

The tool reports about 1 ms for both percentiles and about 1 s for the maximum. A client on schedule sees 99th percentile near 500 ms and 99.9th near 950 ms. Believe the second: the tool’s own stall hid the delays. This error is known as coordinated omission.

The tool: it sends 500 requests a second, so 50 000 in 100 s, minus the 500 it never sent while waiting, which leaves 49 500 samples. One of them took about 1 s, and the rest took 1 ms. One sample in 49 500 is beyond the 99.9th percentile.

The client on schedule: when the freeze ends, 500 requests are queued, with waits from 1 s down to nearly 0. The server then drains at a net 500 a second, $1000 - 500$, so the backlog clears in another second, during which 500 more requests arrive and wait. In all, 1000 requests in 50 000, or 2%, wait for between 0 and 1 s, roughly uniformly. The worst 1% is the upper half of those, so the 99th percentile is near 500 ms, and the worst 0.1% is the top 50, near 950 ms. The mean rises from about 1.02 ms to about 11 ms. A simulation of both clients agrees.

The fix is to measure from the scheduled send time, and to keep to the schedule on its own thread whatever the server does, so that a stall is charged to every request it delays.

Answer to Question 4.27.

You get 67.2 ns per packet, about 202 cycles at 3 GHz, at 14.88 million packets a second. One call per packet handles 1.5 million a second, about a tenth of the need; one call per 32 packets handles about 6 million. For this constraint, choose AF_XDP.

Each frame takes $84 \times 8 = 672$ bits on the wire, so $10^{10} / 672 \approx 14.88$ million frames a second. One call per packet costs $500 + 150 = 650$ ns. Batching spreads the 500 ns over 32 packets, $15.6 + 150 = 165.6$ ns, or 6.04 million a second. Under these assumptions, the per-packet stack cost is what stops any socket path, however large the batch. Real feeds do not run at minimum-size line rate all the time, but bursts set the queue depth, so this is the right worst case.

The choices:

• Sockets with SO_BUSY_POLL: nothing changes in your tools, and it can cut wake-up latency at the price of more processor time and power, but the stack cost stays. It helps latency, not this throughput.
• AF_XDP: an XDP program redirects chosen frames into a user-space ring and returns everything else to the kernel, so management traffic keeps working on the same port. Zero-copy needs driver support and falls back to copy mode otherwise.
• DPDK: poll-mode drivers read descriptors directly on a dedicated core with no interrupts. Most devices must first be unbound from their kernel driver, so ordinary kernel tools and traffic no longer see that port without a separate arrangement. It fits a dedicated port, not this one.

Answer to Question 4.28.

Removing a core from the scheduler stops other tasks running there, and little else: interrupts, the timer tick, kernel housekeeping, flushes requested by other threads and firmware can all still take the core. Check them in that order, measure first, and change one thing at a time.

Start with a tool that attributes the noise. The osnoise tracer runs a sampling loop per processor and counts lost time by source: NMI, interrupt, softirq, thread, or hardware if nothing in the kernel explains it. In a VM, the host’s interference appears as hardware noise. Then:

• Interrupts: read /proc/interrupts over time for the core, and steer devices away. The managed_irq flag of isolcpus helps only on a best-effort basis.
• The tick: isolcpus does not stop it. nohz_full avoids the tick on a core with one runnable task, though about one per second can remain, and one other core must keep ticking.
• Kernel housekeeping: nohz_full requires RCU callbacks to be offloaded with rcu_nocbs, and those threads should be pinned elsewhere.
• Your own process: on x86, a munmap in another thread makes the kernel flush translations on every processor running that process, including the isolated core, so avoid it after start-up. Lock memory, or a page fault will land in the loop.
• Firmware: system-management interrupts are invisible to the kernel and can take milliseconds. The hwlat tracer finds them by spinning with interrupts off and looking for gaps. That would fit the one-millisecond outliers, and the remedy, if there is one, lies in the firmware settings.

Answer to Question 4.29.

The first two lines are 16 12 and 16 24. The sizes of Wire, Packed and Fixed are fixed by their repr; the 16 for Free is not promised. ts_cast is undefined behaviour: the debug build aborts with “misaligned pointer dereference”, and the release build printed the value the correct code gives.

repr(C) lays fields out in declaration order, so Fixed has padding around its u64 and takes 24. The default representation may reorder fields, and here it got Free down to 16, but the only promises for it concern alignment and non-overlap. repr(C, packed) removes padding, so Packed takes 12.

ts_cast reads a u64 through a pointer that is not aligned for it. Rust’s debug build inserts a check that caught this; the release build has no such check, and the printed value proves nothing.

{ p.ts } makes a copy, and the compiler knows that a packed field needs an unaligned read. &p.ts would create a reference that may be misaligned, which is undefined however it is used, so it is rejected as error E0793, and unsafe does not help.

Write ts_cast as ts_read is written: u64::from_le_bytes on a byte range, which also states the wire byte order. Or use read_unaligned on a raw pointer.

Answer to Question 4.30.

There are two soundness holes and two ways to lose a value. The bound on Sync is missing, so non-thread-safe types can cross. put and take take &self, so two threads can race on the slot. A value left in the box is never dropped, and a value put into a full box is dropped.

First hole. unsafe impl<T> Sync promises sharing is safe for every T, including Rc. The listing’s main, with no unsafe in it, sends an Rc to another thread, and both threads clone it. ThreadSanitizer on the nightly compiler reports a race inside Rc’s count. With unsafe impl<T: Send> Sync, the same main fails to compile with E0277.

Second hole. Nothing limits who calls put. Two threads can both see full false and both write the slot; two callers of take can both read the same value, a double drop for a type that owns memory. A test with two threads calling both methods gets a ThreadSanitizer race in Mailbox. The fix is either a compare-and-swap claim on a three-state flag, or the type-level way: split the mailbox into a sender and a receiver whose methods take &mut self.

The leak: MaybeUninit never runs a destructor, so a value still inside when the mailbox is dropped is lost. A drop counter stays at 0. That is safe, as leaking is not undefined behaviour, and the fix is an impl Drop that checks full.

The lost value: put takes the value by move, and on a full box drops it and returns false, so the caller has nothing left to retry with. A value with a printing destructor prints its drop before the false comes back. Return Result<(), T> instead.

Answer to Question 4.31.

It is not correct. The data race on data_ makes it undefined, even though a torn copy would be thrown away, and two reorderings are allowed that x86-64 happens to hide. Listing 4.33 is the rewrite: the fields become relaxed atomics, with a release fence after the writer’s first store and an acquire fence before the reader’s second load.

class SeqLock {
    std::atomic<unsigned> seq_{0};
    std::atomic<std::uint64_t> bid_{std::bit_cast<std::uint64_t>(0.0)};
    std::atomic<std::uint64_t> ask_{std::bit_cast<std::uint64_t>(1.0)};

public:
    void write(const Quote& q) {  // exactly one writer thread
        unsigned s = seq_.load(std::memory_order_relaxed);
        seq_.store(s + 1, std::memory_order_relaxed);
        std::atomic_thread_fence(std::memory_order_release);
        bid_.store(std::bit_cast<std::uint64_t>(q.bid), std::memory_order_relaxed);
        ask_.store(std::bit_cast<std::uint64_t>(q.ask), std::memory_order_relaxed);
        seq_.store(s + 2, std::memory_order_release);
    }
    Quote read() const {
        for (;;) {
            unsigned s1 = seq_.load(std::memory_order_acquire);
            if (s1 & 1) continue;
            Quote copy{std::bit_cast<double>(bid_.load(std::memory_order_relaxed)),
                       std::bit_cast<double>(ask_.load(std::memory_order_relaxed))};
            std::atomic_thread_fence(std::memory_order_acquire);
            unsigned s2 = seq_.load(std::memory_order_relaxed);
            if (s1 == s2) return copy;
        }
    }
};

The three faults. First, a plain read overlapping a plain write is a data race, whatever you do with the result; ThreadSanitizer reports it on line 17. Second, in the writer, a release store orders what came before it, and says nothing of what follows, so the data write may become visible before the odd value. Third, in the reader, an acquire load orders what comes after it, and so does not stop the data reads sinking below the second load. On x86-64 the hardware keeps stores in order and loads in order, so only the compiler can do this there.

The defence of the rewrite. If the reader’s data load sees a value written after the writer’s release fence, the fence pair synchronises, and its second load then cannot miss the odd value, so s1 != s2. If the first acquire load reads the even value of a finished write, it sees all of that write’s data. The fields must be atomic words: the compiler may not tear or invent reads of those. The test ran the rewrite with 0 torn reads and no ThreadSanitizer report. That report only checks for data races, however: GCC’s manual says ThreadSanitizer does not support atomic_thread_fence, so the fences rest on this argument.

The costs. The writer never waits, and on x86-64 its write compiles to plain stores with no locked instruction. Readers write nothing, so they do not contend with each other, where a mutex would have each of them write its lock word. They do still cost the writer cache misses: each read takes the lines into shared state, and the writer’s next store must take them back. And a reader can retry for as long as the writer keeps writing. The payload must be safe to copy word by word, and more than one writer needs a lock of its own.

Answer to Question 4.32.

The two faults are a use-after-free on line 23 and the ABA problem. The first occurs because pop reads n->next while another thread may already have deleted n. The second occurs because the compare-and-swap checks an address, not the history behind it.

Use-after-free. Threads 1 and 2 both load the same head. Thread 2 wins, pops it and calls delete. Thread 1 now evaluates n->next on freed memory, which can fault if the page has gone. Under stress with four threads, AddressSanitizer reports a heap-use-after-free on that line, and ThreadSanitizer, depending on the schedule, a race between the read and the delete or the use after free itself.

ABA. The stack is A, B, C. Thread 1 reads head A and next B, and stops. Thread 2 pops A, pops B and frees it, then pushes A back, its address reused. Thread 1’s compare-and-swap sees A, succeeds, and sets the head to B, which is free. Listing 4.34 replays exactly that without threads, and it prints that the swap succeeded, the head is 1 (B) and its in-use flag is 0.

int main() {
    push(2);  // C, the bottom
    push(1);  // B
    push(0);  // A, the top
    int a = head.load();     // thread 1 reads the top, A
    int b = pool[a].next;    // thread 1 reads A's next, B, and is suspended
    pop();                   // thread 2 pops A
    int freed = pop();       // thread 2 pops B: B is free now
    push(a);                 // thread 2 reuses A and pushes it back
    bool won = head.compare_exchange_strong(a, b);  // thread 1 resumes
    std::printf("untagged: cas %d, head %d, head in use %d, freed %d\n", won, head.load(),
                pool[head.load()].in_use, freed);

The fixes, with costs:

• A pool of nodes that are never returned to the system, indexed, with a counter beside the index in one 64-bit word. This cures both faults, as the read stays in valid memory and the tag changes on every update, provided next is itself an atomic, read relaxed: a stale read is then harmless, as the tag makes that swap fail. In the same replay the swap fails. The cost is a fixed pool, and a 32-bit tag can come round again: at 10 million updates a second it wraps every 430 seconds, though a stale swap then needs the exact count.
• Hazard pointers: each thread publishes what it is about to read, and a node is freed only when no one has published it. The cost is an ordered store and load on every read, and a periodic scan.
• Epochs: nodes are freed once every thread has passed a grace period. Reads are cheap, but one stalled thread blocks all reclamation.
• Avoid the structure: on a hot path, give each thread its own pool, which is usually what one should do.

Answer to Question 4.33.

Not if completing an operation means delivering an item. While that producer is stalled, other producers can fill whatever slots remain, 7 if the queue was otherwise empty. Once consumers have taken everything ahead of the stalled position, every try_pop returns empty, even though completed pushes are waiting behind the stalled slot. A consumer’s wait is as long as the suspension.

The replay in the file claims position 0 and does not commit. A second producer then succeeds 7 more times and is told the queue is full. A consumer gets empty, because position 0’s seq says not ready, and consumers take positions in order. When the first producer resumes and commits, the consumer gets its value at once, and the rest then flow. Under stress the code is sound: ThreadSanitizer is silent, and the sum over two producers and two consumers came out exact.

Read narrowly, each try call does return, which is why the word gets used. But reporting “empty” after other pushes have finished is not the pop a queue promises, and no call can deliver an item until that one thread runs again, whichever other threads are running. A blocking pop built on this would wait for it. Calling such a queue lock-free because it holds no mutex is common, and misleading.

The worst case is therefore unbounded by the queue: it is whatever the operating system does to that thread, and the mutex’s classic flaw is back without the mutex. To tighten it, keep producers from being preempted, with pinned threads on isolated cores, which reduces the chance, not the possibility. Or redesign: give each producer its own single-producer ring, and let the consumer poll them round-robin. A stalled producer then delays only its own items. The cost is global order: you merge by timestamp or sequence if order across producers matters, and the consumer does more work per poll.

Answer to Question 4.34.

Split the queue into a Producer and a Consumer, neither of them Clone, whose methods take &mut self. peek returns a guard that borrows the consumer mutably, and the Sync impl on the shared state is bounded by T: Send. Listings 4.35 and 4.36 give the core.

struct Shared<T> {
    head: AtomicUsize,
    tail: AtomicUsize,
    slots: Box<[UnsafeCell<MaybeUninit<T>>]>,
}
// Each slot is touched by one side at a time, and T itself moves between threads.
unsafe impl<T: Send> Sync for Shared<T> {}

pub struct Producer<T>(Arc<Shared<T>>);
pub struct Consumer<T>(Arc<Shared<T>>);
pub struct Peek<'a, T>(&'a mut Consumer<T>, PhantomData<&'a T>);

pub fn channel<T>(capacity: usize) -> (Producer<T>, Consumer<T>) {
    assert!(capacity.is_power_of_two());
    let slots = (0..capacity)
        .map(|_| UnsafeCell::new(MaybeUninit::uninit()))
        .collect();
    let (head, tail) = (AtomicUsize::new(0), AtomicUsize::new(0));
    let s = Arc::new(Shared { head, tail, slots });
    (Producer(Arc::clone(&s)), Consumer(s))
}

impl<T> Producer<T> {
    pub fn push(&mut self, v: T) -> Result<(), T> {
        let s = &self.0;
        let t = s.tail.load(Relaxed);
        if t.wrapping_sub(s.head.load(Acquire)) == s.slots.len() {
            return Err(v);
        }
        unsafe { (*s.slots[t & (s.slots.len() - 1)].get()).write(v) };
        s.tail.store(t.wrapping_add(1), Release);
        Ok(())
    }
}

    pub fn peek(&mut self) -> Option<Peek<'_, T>> {
        let s = &self.0;
        if s.head.load(Relaxed) == s.tail.load(Acquire) {
            return None;
        }
        Some(Peek(self, PhantomData))
    }
}
impl<T> Deref for Peek<'_, T> {
    type Target = T;
    fn deref(&self) -> &T {
        let s = &self.0 .0;
        let h = s.head.load(Relaxed);
        unsafe { (*s.slots[h & (s.slots.len() - 1)].get()).assume_init_ref() }
    }
}
impl<T> Drop for Peek<'_, T> {
    fn drop(&mut self) {
        drop(self.0.pop()); // the value leaves the ring only when the borrow ends
    }
}

Each of the three mistakes was compiled, and each fails. Cloning a Producer gives E0599, since no such method exists. Putting one in an Arc and calling push gives E0596, as you cannot get &mut through a shared handle. Calling pop while a Peek is alive gives E0499, a second mutable borrow. Sending a Producer<Rc<u64>> to a thread gives E0277.

Only the Sync line is needed, because UnsafeCell is not Sync, which is what blocks sharing. Send follows automatically from T: Send. The promise that makes the line correct is that each slot is accessed by one side at a time. The bound T: Send is required, as items really do cross threads. T: Sync is not needed by the queue itself, which hands items over whole. But peek gives out &T, so Peek carries a PhantomData<&'a T>, and a Peek can reach another thread only when T: Sync. Without that field, safe code shares one Peek<Cell<u64>> between two threads and races on the cell. With it, the same code gives E0277.

What the compiler will not catch: the memory orders. Change Release to Relaxed, and it compiles. The same goes for an off-by-one in the indices, and for failing to drop unread items, which here is the Drop impl on Shared, tested to drop each unread item exactly once. A stress run under ThreadSanitizer on the nightly compiler gives no report in this module, though with a precompiled standard library it must ignore reports from Arc’s own final drop, which uses a fence the tool cannot see. Also, masking the index does not remove the bounds check on slots, as the assembly of push shows, because the slice’s length is known only at run time.

Answer to Question 4.35.

Clone’s Relaxed is correct, and Drop’s is not. The decrement must be Release, and the thread that frees must perform an Acquire first, as in Listing 4.37. This is the same pattern as in the standard library’s Arc.

impl<T> Drop for MyArc<T> {
    fn drop(&mut self) {
        if unsafe { self.ptr.as_ref() }.count.fetch_sub(1, Ordering::Release) != 1 {
            return;
        }
        fence(Ordering::Acquire);
        drop(unsafe { Box::from_raw(self.ptr.as_ptr()) });
    }
}

Clone is safe because a thread can only clone a handle it can already reach, and however it got that handle already carried the necessary synchronisation, so the count cannot be falling to zero meanwhile. No ordering on the increment is needed.

What goes wrong. Thread A reads the value through its handle, then decrements to 1. Thread B decrements to 0 and frees. With relaxed decrements, nothing makes A’s read happen before B’s free, so they conflict: this is a data race, and undefined. A stress program with a heap-allocated value gets a ThreadSanitizer report naming this code, on the nightly compiler.

Why both sides. The Release on every decrement makes that thread’s uses happen before its decrement. The Acquire before the free joins all of them into the freeing thread. The fence is only taken by the last owner, so other decrements pay nothing extra. ThreadSanitizer does not model fences, so the test replaces the fence by an acquire load of the count, which the standard library does in the same situation, and that form is clean. The fence version rests on the argument above and on the standard library’s own use of it.

The bounds. T: Sync, because handles on many threads hand out &T. T: Send, because the last drop may run on any thread, which moves ownership of T there. Sending a MyArc<Rc<u64>> to a thread fails with E0277.

The cost on x86-64: the decrement is a locked instruction whatever its order, and an acquire needs no instruction, so the fix adds nothing there beyond what the compiler may no longer move. On a weakly ordered processor the release and the acquire each need a stronger instruction or a barrier. Using a fence only on the last decrement saves the acquire on the others.