Batching and amortisation

5.7 Batching and amortisation

To amortise a cost is to pay it once and spread it over many items, so that each item’s share is small. A Vec’s doubling is the textbook case. For 1,024 elements of 32 bytes the copy is 32 KB, 2–3 µs, and it buys room for the next 1,024 pushes, so spread over them it adds 2–3 ns to pushes that otherwise cost 1–2 ns. However large the Vec grows, the average push stays a few nanoseconds, which is what “amortised O(1)” means. It says nothing about the push that doubles, which still takes 2–3 µs, two to three budgets, and milliseconds at a million elements, between moving 32 MB and faulting in its new pages. That is the difference between an average and a tail: the p50 of those pushes is 1–2 ns and their max a thousand times higher. Amortisation lowers the average and leaves the spike where it was.

A batch is a group of items handled together so that a cost paid per handling is paid once for the group, and batching is amortisation the program chooses, not one a library imposes. On a hot path it has one shape: drain, process, publish once. Drain means take every item available now, as the ring’s drain does; process means apply each item to the thread’s own state; publish once means write the result other threads read a single time, after the last item.

The rule that keeps this from costing latency is never to wait to fill a batch. A consumer that waits until it has 16 items, or until 10 µs have passed, holds the first item for as long as it waits: latency added by design. A consumer that takes what is there adds none: with one update waiting the batch is one, handled at once, and in a quiet market every batch is one, which is correct. Batches then size themselves: during a burst, items queue while the thread works through the previous batch, so the next drain finds many, and when the burst passes the size falls back to one. TCP’s Nagle algorithm, which holds a small segment back until the previous one is acknowledged, is the classic case of waiting to fill a batch; trading sockets turn it off with TCP_NODELAY.

The kernel already batches on the way in. The networking chapter showed NAPI, the driver’s polling loop, taking up to 64 frames per interrupt; GRO merging a flow’s segments into one before the protocol code sees them; and one recv returning every byte queued, dozens of updates after a burst. The program should batch at each of its own hand-offs. On a venue feed, preserve complete event boundaries before publishing a book state: a socket read or a ring drain can contain only part of a multi-level event. In the ring that is push_batch’s single Release store of head, which moves head’s line once per batch, not once per item. The thread that keeps the book publishes one Top, the best bid and ask in one cache line, per batch, as the order-book chapter does, which also spares readers a top that existed only halfway through a message. The gateway thread on core 6 drains the orders the strategy queued and sends them in one write: one system call and one pass down the kernel’s send path, 2–5 µs, instead of one per order. And the timestamp a batch needs is read once, 20–30 ns through the vDSO, which never enters the kernel, not once per update.

What it costs

A batch saves each item its share of the overhead: a cost h paid per handling becomes h/k for a batch of k. What it cannot change is the queue. One core handles the 30 updates of a burst one after another however they are grouped, so the 30th waits behind 29 either way; a batch never shortens the queue, only the overhead inside it. It also charges the earlier items, because nothing is published until the batch is done: the first update’s result now waits for the 29 applied after it. So the trade is worth making only when the overhead is large against the work. A 50–100 ns line transfer (200–400 cycles) against a 2–5 ns apply (8–20 cycles) is, the overhead being 10–50 times the work. A 1 ns bitmap test is not: done once per batch instead of once per item it saves 1 ns, and every earlier item pays the wait.

Worked example: the same burst, item by item and as a batch

At 14:30:00.000 the burst on BTC-USDT-PERP, instrument id 42, reaches the feed thread on core 2, and one recv returns 30 updates. The feed thread pushes them into the ring for the strategy on core 3, which applies each to its book for id 42, 2–5 ns, and publishes a Top for a risk monitor on another core. Count from the moment recv returns.

Item by item, the feed thread stores head after every push and the strategy, polling as fast as it can, loads it before every pop, so head’s line crosses 30 times at 50–100 ns, 1.5–3 µs. The strategy publishes after every apply, and the monitor’s reads pull the Top line across each time: 30 more, another 1.5–3 µs. The first update’s Top is out after 100–200 ns; the 30th’s after 3–6 µs, 12,000–24,000 cycles, three to six budgets, of which the applies are 60–150 ns.

As a batch, push_batch writes the 30 slots and stores head once. One drain on core 3 loads it once, one transfer of 50–100 ns, applies all 30 in 60–150 ns, and publishes one Top, one more transfer of 50–100 ns. The 30th update’s effect is out after 160–350 ns, a sixth to a third of a budget, and so is the first’s, 60–150 ns later than item by item: the 29 applies it now waits for. The 15 slot lines carrying the 960 bytes of updates cross in both versions, the data’s own price, and are left out of both sums. The batch removed 58 of 60 transfers; the queue of 30 applies is the same in both.

Seeing it

Count batch sizes where they form: on core 2, how many updates each recv returned; on core 3, how many each drain returned. Record both into a fixed-memory histogram such as the hdrhistogram crate’s, print p50, p99 and max, and count publishes and updates beside them; here sizes is the histogram and slot the place the Top goes:

let mut changed = false;
let n = rx.drain(|u| changed |= book.apply(&u)); // everything there now; never waits
if n == 0 { continue; }                          // nothing there: no batch to fill
sizes.saturating_record(n as u64);
updates += n as u64;
if changed {
    slot.publish(book.top());                    // once per batch
    publishes += 1;
}

In a quiet market both histograms should show a p50 of 1, the rule working, and in a burst a p99 in the tens. drain sizes that keep growing past the recv sizes mean the strategy is falling behind and its queue is building. Publishes per thousand updates should be well under a thousand; a thousand means something publishes per item. Then replay a recorded burst through both versions under perf stat -e cache-misses,L1-dcache-load-misses and divide by the number of updates. The L1 count, loads that missed L1 with the transfers among them, should fall by about two per update from the per-item version to the batch, the head and Top lines, leaving the slot lines both pay. cache-misses, which on most parts counts last-level misses, may not count a line fetched from another core at all; comparing the two counts shows which this part does.

Read more: Martin Thompson, “Smart Batching” (Mechanical Sympathy blog, October 2011, mechanical-sympathy.blogspot.com/2011/10/smart-batching.html), states the rule as sending as soon as anything is there, and shows batch sizes following load while latency stays flat until the device saturates. Martin Thompson, Dave Farley, Michael Barker, Patricia Gee and Andrew Stewart, “LMAX Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads” (2011, lmax-exchange.github.io/disruptor/disruptor.html), describes the same effect from the consumer’s side.