[−][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 `count` of observations between its `begin` and `end` endpoints.