# [−][src]Crate b2histogram

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 (open-open)
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

Buckets 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

Base2Histogram | A compact and efficient integer histogram with fixed memory footprint, constant runtime performance, and very compact binary serialization. |

Bucket | A bucket maintains a |