base2histogram 0.1.1

A Rust histogram library using base-2 logarithmic bucketing for fast percentile estimation
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108

# base2histogram

`base2histogram` is a Rust histogram library for fast percentile estimation with
base-2 logarithmic bucketing.

It is designed for latency and metrics workloads where:

- recording should be `O(1)`,
- memory usage should stay bounded,
- percentile queries should be cheap,
- and large `u64` values should still be representable without resizing.

## Features

- Fixed-size histogram over the full `u64` range.
- Base-2 logarithmic buckets with bounded relative error.
- Cheap percentile queries such as `P50`, `P99`, and `P99.9`.
- Optional multi-slot mode for sliding-window style aggregation.
- No external runtime or allocator tricks required.

## Bucket Model

The default configuration uses 3 significant bits to define a bucket:

- values `0..=7` are represented exactly,
- values `8..=15` are grouped with step size `2`,
- values `16..=31` are grouped with step size `4`,
- larger values keep doubling the bucket width with the magnitude.

This keeps relative error bounded while covering the entire `u64` range in a
small, fixed number of buckets.

## Usage

```rust
use base2histogram::Histogram;

let mut hist = Histogram::<()>::new();

hist.record(5);
hist.record(8);
hist.record(13);
hist.record_n(21, 3);

assert_eq!(hist.total(), 6);

let p50 = hist.percentile(0.50);
let p99 = hist.percentile(0.99);

assert!(p50 <= p99);
```

`percentile()` returns the minimum value of the bucket that contains the target
percentile. This is intentional: the histogram stores bucketed counts, not raw
samples.

## Sliding Window

Use `with_slots()` plus `advance()` when metrics should be aggregated over a
bounded set of recent windows:

```rust
use base2histogram::Histogram;

let mut hist = Histogram::<&'static str>::with_slots(2);

hist.record_n(10, 2);
hist.advance("warm");
hist.record_n(100, 3);

assert_eq!(hist.total(), 5);

hist.advance("steady");

// The oldest slot is evicted once the slot limit is reached.
assert_eq!(hist.total(), 3);
```

## Common Stats

```rust
use base2histogram::Histogram;

let mut hist = Histogram::<()>::new();
hist.record_n(20, 80);
hist.record_n(80, 20);

let stats = hist.percentile_stats();

assert_eq!(stats.samples, 100);
assert_eq!(stats.p50, 20);
assert_eq!(stats.p90, 80);
```

## Development

Common local commands:

```bash
make check
make test
make lint
make doc
```

## License

Licensed under Apache-2.0. See [LICENSE](./LICENSE).