]> git.ipfire.org Git - thirdparty/dovecot/core.git/commit
lib: bits - new fractional log-like helper
authorPhil Carmody <phil@dovecot.fi>
Wed, 3 Feb 2016 16:34:13 +0000 (18:34 +0200)
committerTimo Sirainen <timo.sirainen@dovecot.fi>
Thu, 27 Apr 2017 07:26:15 +0000 (10:26 +0300)
commitb9735121d7895babd3aa17f4f9f70e9b1f1e279a
tree6e915f16fb95ef3997a2c934b3ef10802b24c8ca
parent3d6b8ea7b57071c80db4145ac6db3b477d39d7a9
lib: bits - new fractional log-like helper

For stats gathering, where the data can have a wide range of values, you
don't necessarily need the same granularity along the full range of values.
For example, 1ms and 11ms latencies are very different, but 1.001s and
1.011s latencies are not worth distinguishing. Something logarithmic seems
more apt. Simply looking at power-of-2 sized bands (e.g. doing log2(n)),
however, is too granular, so these new helpers let you specify how fine
to (linearly) subdivide each of those bands. 1 fractional bit splits
each power of 2 band into 2 halves. 2 fractional bits splits each power
of 2 band into 4 quarters, and so on. 0 fractional bits is just log2().

Exact identification of percentiles is impossible, but it was anyway, as you
simply cannot store all the data required to calculate them. However, a mere
896 buckets will permit you to have 32 bands per power of 2, 5 fracional bits.
The above example would have buckets such as 2.432s-2.496s, and 55.3s-56.3s.
Assuming smooth distribution lets you calculate percentiles more accurately,
just assume within each bucket is a trapezial distribution. This holds even
if the distribution is multi-modal, which it will be. However, maths required.

Signed-off-by: Phil Carmody <phil@dovecot.fi>
src/lib/bits.h