Histogram costs and replaying an outlier

What it costs

A record costs 10–30 ns: 10–15 ns when its counter’s line is in L1, as the common values’ are, and more for a rare value whose line has gone to L2 or L3. A quantile query costs 10–20 µs and a merge about the same, both after the run. The worst-100 list is 1.6 KB, 1 ns per message in the common case and about 100 ns per replacement. One histogram per second costs its memory again each second. Three significant figures are the usual choice: the step at any value is under 0.1% of it, below the run-to-run variation of every percentile, and 170 KB per histogram fits five of them, the capstone’s set, in under 1 MB. Four buy precision that the next run will not reproduce, at thirteen times the memory and, for a scattered tail, more cache misses per record.

Worked example: ten million samples and one sequence number

A paced replay of ten million messages, 100 seconds at 100,000 a second, on cores that are pinned but not yet isolated, reports for total: count 10,000,000, p50 280 ns, p99 1.4 µs, p99.9 6 µs, max 2.1 ms at sequence number 1,204,117. Every percentile rests on plenty: 100,000 samples above the p99, 10,000 above the p99.9, and 1,000 above the p99.99, so each is safe to quote. The max is one sample, 7,500 times the median, held to within 2 µs.

Something took 2.1 ms, and it was not the loop’s code: the slowest path through apply and quote, a long cursor walk or the last of a 30-message burst, is a few microseconds. Ranked by size, the candidates are a page fault on a page already in memory, 0.5–1 µs, far too small; a page fault served from disk, 100 µs and up; a firmware interrupt, the system management interrupt that firmware uses for its own work and the operating system cannot see, from tens of microseconds to milliseconds; and a preemption, the scheduler giving a core that is not isolated to another runnable thread for a slice of 1–4 ms. The last fits best, and the sequence number is how to find out.

The replay file holds its records in sequence order, 56 bytes each, with consecutive sequence numbers, so message 1,204,117 sits at an offset computed from the first record’s, and its t_arrival_ns says when in the run it came. First, look at it and its neighbours: the last of a burst, a price that moved the best level, a new page of the file. Then replay the same file and see where the max lands. If it lands on 1,204,117 again, the cause travels with the input, a burst or a walk or a page, and replaying a window around that message with the stages build stamped shows which stage it was. If it lands on a different message each run, at a similar size, the cause is the machine, and the worst-100 list says how often: a hundred samples spread evenly over the run suggest something periodic, a timer or a daemon; a cluster in one second, a one-off. The kernel’s own counts of faults, context switches and interrupts on cores 2 and 3, the subject of finding where the time goes, name it.

Seeing it

Print more than three quantiles: value_at_quantile for 0.5, 0.9, 0.99, 0.999, 0.9999 and 1.0, with len(), shows how fast the tail rises, and two runs of the same file should agree to a few percent everywhere except the max. iter_recorded() walks every bucket that has a count, giving each one’s value_iterated_to() and count_at_value(); printed for the capstone’s total, it is the distribution drawn earlier in the chapter, at full resolution, and plotted with the count on a log axis it shows the tail that a linear axis hid. iter_quantiles(5) yields rows like those of the percentile-distribution table that the Java library prints, value against percentile, which the HdrHistogram project’s online plotter reads to draw latency against “number of nines” on a log axis, the standard picture of a latency distribution. To keep a run for later, hdrhistogram::serialization::V2Serializer writes a histogram in the compact binary format that the other HdrHistogram implementations read too, typically a few kilobytes because runs of empty counters encode in a few bytes, so a run’s histograms can be saved beside its output, compared with next week’s, or added to those of another machine. Predict first: the p50 and p99 of two runs within 5% of each other, the max anywhere.

Read more: Gil Tene’s HdrHistogram README, in the project’s repository at https://github.com/HdrHistogram/HdrHistogram, explains the design, the significant-figures promise, the memory it costs and why it records in fixed time with no allocation. The Rust crate’s documentation at https://docs.rs/hdrhistogram describes construction with bounds, recording and saturating recording, quantile queries, iteration, addition and the serialisation formats.