Crate b2histogram
source ·Expand description
A fast and efficient 64-bit integer histogram with power-of-2 spaced buckets.
- Fixed memory footprint (520 bytes) with no dynamic allocations
- Constant time record and retrieve operations that compile down to a few instructions
no_std
support- Work in progress: Compact binary serialization
Example
extern crate b2histogram;
use b2histogram::Base2Histogram;
fn main() {
let mut hist = Base2Histogram::new();
hist.record(0); // Record a single observation of '0'
hist.record(11); //
hist.record(11); // Two observations of '11'
hist.record_n(300_000, 6); // Six observations of 300,000
// Retrieve counts directly
println!("Observations for 300,000: {}", hist.observations(300_000));
// Retrieve the `Bucket` covering a given value
println!("Bucket corresponding to '11': {:?}", hist.bucket_for(11));
// Iterate buckets that have observations
for bucket in hist.iter().filter(|b| b.count > 0) {
println!("({:5}, {:5}): {}", bucket.start, bucket.end, bucket.count);
}
}
Recording Observations
Use the record()
and record_n()
methods to add observations to the histogram.
record(value: u64)
to record a single observation ofvalue
record_n(value: u64, count: u64)
to recordcount
observations of the samevalue
Retrieving Observations
observations(value: u64)
returns the
current count for the bucket that covers value
.
bucket_for(value: u64)
will return a
Bucket
struct for the bucket corresponding to value
. A
Bucket
provides fields to access the lower and upper bounds of the
bucket along with the current count.
Bucket Ranges
Buckets cover the range [2^n, 2^(n+1)-1]
including their start and end values (closed-closed)
for all powers of 2 from 0 through 2^62. The bottom-most bucket records observations of
zero and the top-most bucket covers [2^62, +infinity]
.
Overflow Behavior
Bucket counts saturate (reach maximum value and stay there) instead of overflowing or wrapping around.
Implementation Details
Bucket Mask
The mask
field is a 64-bit bitmask with each bit corresponding to one of the 64 buckets.
If the bit is 1 then that bucket has one or more observations while a 0 value means the
bucket is has no observations.
The bit position at index i
(from least-significant-bit (LSB) to most-significant
(MSB)) corresponds to bucket [2^(i-1), (2^i)-1)]
. In diagram form:
MSB <------------------------ LSB
+--+--+--+-------+--+--+--+--+--+
|63|62|61| . . . | 4| 3| 2| 1| 0|
+--+--+--+-------+--+--+--+--+--+
^ ^ ^ ^ ^ ^ ^
| | +------+ | | | +-------+
Values | ++ | +----+ | +----+ |
(2^62, +inf) --+ | Values | | | Values
| (8, 15) | | | (0, 0)
Values Values Values Values
(2^61, 2^62-1) (4, 7) (2, 3) (1, 1)
Counts Field
The counts
field is a simple u64
array of 64 elements. There is one array entry for
each bucket and array index i
corresponds to mask bit i
.
Structs
- A compact and efficient integer histogram with fixed memory footprint, constant runtime performance, and very compact binary serialization.
- A bucket maintains a
count
of observations between itsbegin
andend
endpoints.