Tony Finch – blog
Since my blog post about hg64 histograms in July I have
continued occasional hacking on the code, so it’s time to post an
update.
As before, my proof-of-concept histogram data structure hg64 is
available from:
simpler allocation
My original version used popcount packed arrays to avoid storing
empty counters. It’s difficult to make this trick efficiently
thread-safe, so I switched it out for a simpler but slightly less
memory-efficient design.
Now there is a top-level array of pointers, one for each possible logarithm of a value, 0 .. 63. Each pointer is assigned at most once (with an atomic compare-and-swap) to an array of counters. The sub-array size depends on the precision (number of significant digits) of the histogram.
separate summary totals
When calculating ranks and percentiles, hg64 uses summary totals so
that it can skip over most of the counter arrays. These totals can’t
be updated in multithreaded code in a way that is both fast and
consistent.
Instead, you need to take an immutable snapshot of the histogram. This separate copy is immune from multithreading issues so its summary totals are always consistent with its counter arrays.
And we save work in the hg64_inc() hot path by removing summary
totals from mutable histograms.
branch-free key calculation
Paul Khuong encouraged me to understand his code for log-linear
bucketing which does the same job as my function to map a 64-bit
value to a low-precision floating-point key. Paul’s bin_down_of()
function uses a clever trick which allows me to remove a branch from
the fast path.
Together, these improvements (unpacked arrays, no summary totals, branch-free bucketing) mean that in the best case (single threaded, histogram is warmed up and in cache) it takes about 2.3 nanoseconds to atomically increment a histogram counter on my M1 Mac. That’s about half the time of my original code back in July.
space / time tradeoffs
The hg64 test code tries hammering a histogram concurrently from
multiple threads. The time measurements mostly show the cost of
high-contention atomic operations - it can be 50x slower than
single-threaded increments on my M1 Mac.
This slowdown isn’t a problem for me, because I aim to use hg64 in
situations where updates are relatively rare; they need to be
thread-safe but cheap.
The hg64 test code illustrates an alternative setup where each
thread has its own histogram, which can be updated fast with zero
contention. The per-thread histograms can be merged to get a
whole-system histogram (even while the update threads are active,
though the test code does not do that).
The real test is that we get the same results from the single concurrent histogram, and the merged per-thread histograms.
todo
I still don’t have any useful way to export or import histogram data. BIND’s built-in statistics web server exports in JSON and XML; I think it would also be useful to support a compressed binary format, and CSV.
And I would like to be able to visualize the data without having a whole prometheus + grafana setup!