Histograms have been widely used to estimate the probability distribution of a continuous variable. Choosing the bin size is difficult: using a logarithmic progression gives a wide range, but at a cost to resolution (particularly in the upper part of the range). Histograms using a linear progression require a large amount of space to compensate for their decreased range.
The logarithmic-linear histogram is a compromise between the two, and provides improved resolution while maintaining a wide range and a reduced space requirement. It does this by using a two-level binning scheme. The top-level bins (which are called buckets) are sized logarithmically (base 2). Each bucket also has a set of second-level bins (which are called slots) -- 16 per bucket -- which are sized linearly within the bin.
The entire implementation is contained in the header file llh.h
; there's no library to link against.
Create a new LLH by initializing it with the provided static initializer, or by just allocating some cleared memory for it:
llh_t histogram1 = LLH_INIT;
llh_t* histogram2 = calloc(1, sizeof(llh_t));
To record an event in a histogram, call llh_record
:
llh_record((llh_t*)histogram, (uint64_t)value);
To get data back out of a histogram, you have three choices, depending on the degree of aggregation desired -- total over the entire histogram, total for one bucket, or the value in a specific slot.
(uint64_t)llh_population_get((llh_t*)histogram);
(uint64_t)llh_population_get((llh_t*)histogram, bucket);
(uint64_t)llh_population_get((llh_t*)histogram, bucket, slot);
Finally, you can use the provided accessor to get the number of overflows:
(uint32_t)llh_overflows_get((llh_t*)histogram);
To run the provided unit tests, use the provided Makefile
:
make clean && make && bin/llh_test
Incrementing histogram values is done by means of an atomic increment. If your platform does not support the INCL
instruction, you'll need to compile with the LLH_UNSAFE_INCREMENT
flag set.