Indirect costs and measuring operations

Direct and indirect cost

The table shows the direct cost, the operation’s own instructions timed alone. The indirect cost is what the operation does to the cache, and whatever runs next pays it. A hash map lookup touches two lines of its table at addresses the hash makes unpredictable, and the map for the desk’s 64 positions is 5,264 bytes over 83 lines, against the 2 KB, 32 lines, of an array of them; an allocation touches the allocator’s free lists, lines the strategy never asked for. Each line that enters L1 evicts one, often the strategy’s own, whose next use then costs 4 ns from L2 or 10–40 ns from L3 instead of 1 ns. A thread woken by a channel or a lock returns to caches that whatever ran meanwhile has refilled, and rebuilding them costs the 10–100 µs Chapter 2 measured, many times the wake itself. The third indirect cost is the queue. A thread does one thing at a time, so a 1–5 ms rehash on one insert delays every update that arrives meanwhile, twenty to a hundred of them at 20,000 a second. The operation pays its row once; the indirect costs are paid by everything after it.

Which rungs matter

The rows above the tail are paid by every operation of their kind, and they set the p50. The tail rows may be paid by only one operation in thousands or millions. They can dominate the maximum and the highest percentiles while leaving p99 unchanged. Their effect on p99 depends on how many operations are slow, including those queued behind the original delay. The twist is who chooses the moment. The tail rows are paid when the library decides, at the moment its bookkeeping runs out, and that moment is not random. A vector fills, a map reaches its limit and the allocator’s lists run dry when more data is alive at once than ever before, which is during the busiest burst of the day, when the update that matters is the one queued behind the copy. That is the whole case for structures that have no tail rows at all rather than rare ones: a fixed array never doubles, a pool never calls the allocator, a ring never takes a lock.

Seeing it

The method must suit the scale. For the cheap rows a clock read is the wrong tool: rdtsc, the instruction that reads the time-stamp counter, costs 5–10 ns itself, as much as a ring push. Instead run the operation millions of times under perf stat, which counts hardware events across a run, pinned to one core with taskset, and divide each count by the number of operations, here the lookup lab’s ten million:

perf stat -e cycles,instructions,cache-misses,branch-misses \
    -- taskset -c 3 ./lookup map 10000000
perf record -g -- taskset -c 3 ./lookup map 10000000
perf report

Cycles per operation is the number to set against the ladder. Instructions over cycles is high when the operation computes on lines in L1 and low when the core waits on loads; cache-misses counts, on most parts, misses that go to DRAM, and branch-misses mispredictions at 15–20 cycles each. Subtract a run of the loop doing nothing, whose own work is in every count. For the tail rows the clock read is the right tool, since 5–10 ns is nothing beside microseconds: time every operation of a replay with rdtsc and report p50, p99 and max, and the tail rows appear as a handful of outliers thousands of times the median, one per doubling, rehash or slow path. The counting allocator, read around the same replay, says how many operations called the allocator at all.

perf record -g samples where the cycles land, with the calls that led there, and perf report names the functions: the allocator as glibc’s malloc and free, with _int_malloc beneath them when the thread cache is empty; a doubling as realloc under alloc::raw_vec, over a copy routine such as __memmove_avx_unaligned_erms; a rehash as hashbrown::raw::RawTable<…>::reserve_rehash. SipHash is inlined into the lookup and has no name of its own; its 15–25 ns is the gap between profiles made with each hasher.