Capstone labs and references

7.10 Lab and reading

Lab

The lab runs the capstone, the crate ch07-capstone/, whose binary gen writes the replay file and whose binary run assembles the threads, instruments them and reports, taking --paced or --flat, --book array|tree|vec, --queue spsc|mutex|mpsc, --stall-every <ms>, --records <n>, --file <path>, the replay file to read in place of replay.bin, and --decisions <path>, the file that takes one line per batch for the join that proves a swap changed no decision, with the stage timers behind the stages feature. As in the earlier labs, write the prediction down before each run, report count, p50, p99, p99.9 and max and never an average, keep the hot threads pinned to isolated cores with memory locked, and subtract the p50 of two back-to-back clock reads from every stage.

ch07-capstone/
  Cargo.toml          the stages feature
  src/
    lib.rs            now() and calibrate(), the histograms and the worst 100,
                      Stamped and StampedOrder, the replay reader
    pipeline.rs       the three threads and the loop, in the library so that
                      the zero-allocation test runs it in-process
    queue.rs          the --queue swaps behind two small traits
    synth.rs          the synthetic feed gen writes
    stats.rs          the kernel's per-thread counters, read from /proc
    bin/
      gen.rs          writes the replay file
      run.rs          assembles, instruments and reports: exercises 1 to 5
  tests/
    no_alloc.rs       the assembled loop allocates nothing after warm-up
    mpsc_allocates.rs the counting allocator sees the channel swap allocate
    decisions.rs      every swap decides the same wherever two runs both decided

Two builds are needed, because the headline and the breakdown come from different binaries. --release builds with optimisation, the only build whose numbers mean anything; --features stages turns the feature on; and --target-dir puts the second build in a directory of its own, so that the two binaries do not overwrite each other.

cargo build --release                                              # headline: t0 and t3 only
cargo build --release --features stages --target-dir target/stages # breakdown: all five points
./target/release/gen                                               # 2,000,000 records, 112 MB, into replay.bin
./target/stages/release/run --flat --decisions flat.decisions      # exercise 1

1. Assemble. Run the stages build in flat mode on the default file and write down updates per second, the count, p50, p99 and max of think, and every counter that must read zero. Predict first: 10–30 million updates a second, set by whichever thread is slower, so write down which you expect that to be and why. If it is the strategy, the ring stays full, drains return thousands of messages, and think, which holds a whole batch’s applies, grows with the batch; so write the number of batches, the line count of the decisions file, beside the number of messages, and say whether the think you measured is comparable with a paced one.
2. Instrument. Run both builds paced and write down the five histograms, each as count, p50, p99, p99.9, max and the sequence number of the max, except out_hop, since the StampedOrder that crosses to core 6 holds t3 and the order and no sequence number, beside the predicted table in the capstone’s description, then the worst 100 total samples with their sequence numbers. Predict first which rows will miss their prediction and in which direction, and how much higher the stages build’s total p50 will be than the headline build’s: the two extra clock reads, 40–60 ns. Then replay the slowest message alone. Cut from the replay file, here replay.bin, that message and the 100,000 before it, so that it lands just after the warm-up. A record is 56 bytes, so record k, counting from 0, starts at byte 56 × k, where k is the message’s sequence number less the file’s first; and dd, which copies a file in blocks, cuts whole records when its block size is one record: dd if=replay.bin of=slow.bin bs=56 skip=$((k - 100000)) count=100001, where skip is the number of blocks to leave out and count the number to copy. The cut file keeps its original arrival times, so a paced run of it idles until the first of them comes round. Predict whether the message is slow again. If it is, the cause is in the data, such as a walk across a wide stretch of the bitmap; if it is not, it was the machine.
3. Profile. Build with frame pointers and debug symbols, as the section on finding where the time goes set out, and, with perf installed, which this exercise needs, record core 3 with sudo ``perf record -F 4000 -g -C 3 -o strategy.data -- ./target/release/run --flat, where -C 3 keeps only the samples taken on CPU 3, which with the strategy pinned there are the strategy thread’s, -o names the file the samples go to, and -- ends perf’s options so that the rest of the line is the command it runs. Do the same for a paced run, and turn each recording into a flame graph with sudo ``perf script ``-i strategy.data ``| inferno-collapse-perf | inferno-flamegraph > flame.svg. Predict first: paced, the thread is busy 1% of the time or less, 100,000 messages a second at 30–100 ns each, so the widest box should be the empty poll, drain returning nothing and pause; flat, it should be the work, on_update and the apply inside it widest, then on_top, try_push and the clock reads. Name the three widest boxes of each and say whether each was expected. Then count with sudo ``perf stat -a -C 3 -D 2000 -e cycles,instructions,cache-misses,branch-misses,context-switches,cpu-migrations,page-faults ``-- ./target/release/run --paced, where -D 2000 starts counting two seconds after the program starts, after the warm-up, and divide each counter by the number of messages: predict an IPC of 1–2 and zeros for the last three.
4. Vary. Run the three swaps one at a time, paced, --book tree, --queue mutex and --queue mpsc, and for each write down the histogram that moved, by how much, and the zero counter that broke. Predict each delta first from the chapter that explains it, as the capstone’s table of swaps sets them out: think p50 to 150–500 ns for the tree, hop p50 to 200–600 ns for the mutex with a p99 in the microseconds, the channel like the mutex plus an allocation every 31 messages. Then prove the decisions did not change: join each variant’s decisions file with the default’s on sequence number, which the Unix join command does for two files sorted on their first field, and compare the rest of each joined pair of lines. Every pair must match, and the number of pairs says how many decisions the proof covers. --book vec is a fourth swap, for anyone who finishes early.
5. Break it honestly. Run --stall-every 1000 paced and write down think and total beside the paced run without it. Predict first: think barely moves, and total gains about 1,000 samples per stall between 0 and 10 ms, about 19,000 in 1.9 million, with a p99.9 near 9 ms and a max near 10 ms. Run the same flag in flat mode and predict that it meets no stall at all, because the whole file goes through in a tenth to a fifth of a second; write that down as a finding, since it is a closed loop compressing 20 seconds of market into a fraction of one. Then run flat with --stall-every 50, which stalls one to four times in the run, and predict that each stall is charged once, to at most the 4,096 messages queued in the ring when it began, however long it lasted. Show the paced and the flat total side by side and say which one is the product.
6. Close the loop. Take the loop printed in the previous section, or, for a team run, the hot path of the codebase the team works on, and pick ten lines of it. For each, name the chapter that explains it, say why it is there, and put a number on doing it otherwise. Predict first which of the ten would cost the most if it were done the other way, and say how you would measure that.

Check: everyone presents one histogram and one flame graph from their own runs and names one concrete change for a real codebase. A good answer reads the histogram as count, p50, p99, p99.9 and max with the machine and the build beside it, says which stage the tail was in and how that is known, says which boxes of the flame graph were expected and why the tail is not among them, and names the change with its predicted effect in nanoseconds and the measurement that would show it.

Reading

1. Gil Tene, “How NOT to Measure Latency”, a talk given at many conferences and recorded at several: coordinated omission from the person who named it, service time against response time, and why a latency without its max and its count is not yet a number.
2. Brendan Gregg, “The Flame Graph”, ACM Queue, 2016, reprinted in Communications of the ACM, June 2016, with the tools and examples at https://www.brendangregg.com/flamegraphs.html: how the picture is built from sampled stacks, why its x-axis is not time, and the variants not used here, among them flame graphs of time spent off the CPU.
3. The hdrhistogram crate’s documentation, https://docs.rs/hdrhistogram: the calls the capstone uses, new_with_bounds, saturating_record, value_at_quantile and the += that merges two histograms, and the iterators and serialisation formats.
4. Carl Cook, “When a Microsecond Is an Eternity: High Performance Trading Systems in C++”, CppCon 2017: a practitioner’s account of the book’s material from inside a trading firm, on keeping the hot path’s caches warm while it waits and the kernel and the allocator off it. Watch it last, with numbers of your own to set against it.
5. Jeffrey Dean and Luiz André Barroso, “The Tail at Scale”, Communications of the ACM, February 2013: the tail treated as a design problem in systems far from trading, with techniques such as sending a second copy of a request that is late.