7 · The number Draft

Why each line of the loop exists

8 min read

On this page

Why each line exists

Read the strategy loop alongside this explanation.

Read it once for what it does. The list below is why each line is there, in the order the lines run.

  1. The two ring ends arrive by value, and neither can be cloned, so once they are moved into this thread no other thread can hold them: the type system keeps each ring single-producer and single-consumer, the one condition under which the data-structures chapter’s ring is correct. Run carries what the main thread computed first: the window’s base price, the quoter, the ticks-to-nanoseconds factor from calibrate(), the file’s first sequence number and the one where warm-up ends, the decisions log and the feed thread’s done flag.
  2. Pinning comes before any allocation, for the OS chapter’s reason: Linux places a page on the NUMA node of the core that first writes it, so everything allocated after this line lands next to core 3, and the thread never migrates to a core whose L1 and L2 are cold. A core that does not exist here, or that a cpuset withholds, stops the run with a message before any thread starts, and the assert! turns a pin the kernel still refuses into a stopped run with a message, instead of numbers for an unpinned thread labelled as pinned; run.core is None only when --strategy-core none asks for an unpinned thread on purpose, and the report then says so.
  3. The book chapter’s feed handler is built whole, now: its ArrayBook, 512 KB a side and 1 MB for both, plus 8 KB of bitmap a side, with the window centred on run.base, the file’s first mid; and its buffer of 4,096 updates, reserved before the run so that a gap buffers without allocating. No apply in the run pays the allocator’s 20–50 ns.
  4. The handler starts Live, expecting run.first_seq, because a replay begins at its first sequence number with nothing to join to; on a live feed the handler would wait for a snapshot first. With no snapshot to resync from, a gap takes the handler out of Live for the rest of the run, and the report says so.
  5. Four of the five histograms, about 170 KB each, and the worst-100 list are made here, on core 3, so that their pages are local and no record can allocate; out_hop belongs to core 6, which owns t4.
  6. Batch is four arrays of 4,096 u64s, 128 KB, sized to the most a drain can ever return. It holds each message’s stamps from its pop until the batch’s t3, because the records must come after t3.
  7. The loop spins and never sleeps. A sleeping thread is woken by the kernel in 5–20 µs, 15 to 130 times the predicted p50 of total; the price of spinning is a core at 100% for the whole run, which is why it is an isolated one.
  8. fin is read with Acquire before the drain, pairing with the feed thread’s Release store of done after its last push, as the threads chapter paired them, so a drain that follows a true sees every message. Read after an empty drain instead, the last message could land between the two and be lost. The line is written once per run, so the load costs about 1 ns.
  9. drain takes everything present, never waits for more, and publishes the consumer’s index once at the end: one line transfer back to core 2 per batch, not one per message. n counts the batch and top holds the newest top seen in it.
  10. In the stages build t2 is read first for each message, since t2 means popped, and t1 is copied out of a slot the feed thread will soon reuse. At 20–30 ns a message, inside both think and total, this is the line the default build leaves out.
  11. on_update is the book chapter’s check before every apply: it compares the sequence number with next_seq, applies only while the state is Live, moves the state out of Live on a gap, and returns the new top only when the apply moved it and the book can be trusted; .or(top) keeps the previous top otherwise, and 95% of updates are deep and leave it alone. The Update goes in by value, 32 bytes of a Copy type already decoded on core 2, so no byte of the wire message is read here.
  12. t0 and the sequence number are stored, at about 1 ns, not recorded, at 10–30 ns, by the ladder of a measurement. The sequence number travels with t0 because a histogram keeps no names, and a slow sample without its name cannot be found again.
  13. An empty drain cost one load of head from core 3’s own cache. spin_loop() compiles to pause, which tells the core it is waiting, so that it stops filling its pipeline with speculative loads it must discard when the line changes; the threads chapter priced it at about 140 cycles on Intel parts since Skylake-SP, up to 35 ns on a hop.
  14. A batch that took the handler out of Live has its top thrown away. on_update returned that top when it could still be trusted, but a gap later in the same batch means the book it came from is now known to be wrong, so the strategy reads handler.state once more before it quotes; matches! tests whether the state has the shape BookState::Live.
  15. map_or runs the quoter once per batch, and only if a top moved, and gives two empty orders otherwise. The 5–20 ns of the quote is paid once a batch, and no quote is made for a top in the middle of a batch, which would be out of date before it left.
  16. t3 is read after the quote and before the push, the moment the decision exists. now() puts an lfence before rdtsc because of the hardware chapter’s out-of-order execution: unfenced, the read could run before the quoter’s arithmetic had finished. It is read on every batch, orders or none, because sending nothing is a decision too.
  17. try_push never waits, and a full output ring counts a dropped order, because a strategy blocked on its output stops draining its input. With 1,024 slots and at most two orders a batch the counter must read zero, and t3 rides inside the 32-byte slot, so it adds no line to the hop.
  18. The log takes one entry per batch: the sequence number that closed it, the top of the handler’s book, and the quote the quoter wants, which it keeps in resting. It is preallocated from --records and written to the decisions file by the main thread after the run, and it is what lets two runs be diffed.
  19. The records come after t3, outside this batch’s number but not outside the program: a message that arrives meanwhile waits in the ring, and since its t0 is its scheduled arrival, the wait is in its own total. The default build’s one record and one offer cost 15–40 ns a message, 0.15–0.4% of the 10 µs between messages at 100,000 a second.
  20. The first 100,000 messages, those before run.warm_seq, ran through every line above and are left out of every histogram, because their latencies hold first touches, cold caches and branch predictors still learning the loop.
  21. Ticks become nanoseconds here, in run.ns(later, earlier): one compare, one subtract and one multiply with the calibrated factor. A later stamp below an earlier one can only mean two cores’ counters disagree, so it is counted as a backwards interval and recorded as 0 ns, not wrapped to a false 1 s. saturating_record clamps anything above 1 s to the top of the range, where record would return an error to branch on, so no sample is lost and nothing allocates; offer is, for nearly every sample, one compare against the smallest of the 100 kept.
  22. The stages block’s three records are after t3, each with the message’s sequence number so that the stage’s slowest message can be found again, but the t1 and t2 reads they need cost 40–60 ns a message on the path, about a sixth of a total p50 near 300 ns. So the breakdown build and the headline build are different builds, and the difference between their totals is what the stage timers cost.
  23. The thread hands its histograms, its state and its log back through join and prints nothing, since a println! is a system call of 1–5 µs and a lock.

The same ten questions open any hot loop, in any program, and this one answers all of them. Which core does it run on, and what else may run there? What does it allocate, and does all of it happen before the loop starts? Which lines does it write that another core reads? What does it do when there is nothing to do, and what does that cost the next arrival? Can anything on the path enter the kernel? How many cache-line transfers does one unit of work cost, and does batching divide them? What does it check before it trusts its input? What does it do when its output is full? Where does it read the clock, and what does each reading cost and hide? And where are its samples recorded, and whose latency pays for recording them? A loop whose author can answer all ten has no line in it that is there by accident.