# 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 of`value`

`record_n(value: u64, count: u64)`

to record`count`

observations of the same`value`

## 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 its`begin`

and`end`

endpoints.