# base2histogram

![](logo.svg)

`base2histogram` is a 2 KB histogram that tracks any `u64` distribution and
answers percentile queries (P50, P99, P99.9, …) with under 2% error for
typical latency workloads.

- **Near-zero error for API latency tracking** — log-normal distributions
  (typical for API/service latency) achieve **< 0.1% error at P50/P95/P99**
  with just 2 KB (default WIDTH=3, 252 buckets):
  ```text
  LN-API  P50  0.000%     P95  0.080%     P99  0.086%
  ```
- **`O(1)` recording**, fixed memory — no sorting, no resizing, suitable for
  hot paths.
- **Full `u64` range** — from nanoseconds to hours in a single histogram.
- **Sliding-window** aggregation via multi-slot mode.

## 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);
assert_eq!(hist.percentile(0.50), 12);
assert_eq!(hist.percentile(0.99), 23);
```

## 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, 21);
assert_eq!(stats.p90, 87);
```

## Percentile Accuracy

`percentile()` uses **trapezoidal density interpolation**: it examines
neighboring bucket counts to estimate a density gradient across the target
bucket, then solves the inverse CDF to pinpoint the value within the bucket.
This requires no additional storage beyond the bucket array itself.

The `WIDTH` parameter controls bucket granularity: each bucket group uses
`WIDTH` bits, giving `2^(WIDTH-1)` buckets per group. Higher `WIDTH` means
finer resolution but more memory. The default is `WIDTH=3` (252 buckets).

Measured with 1,000,000 samples per distribution (`cargo run --bin accuracy`).
Error = `|exact - estimated| / exact × 100%`, shown at P50 / P95 / P99:

```text
                        W=1        W=2        W=3        W=4        W=5        W=6
  --------------------------------------------------------------------------------
  Uniform P50        0.108%     0.028%     0.012%     0.018%     0.019%     0.002%
          P95        2.317%     1.988%     1.035%     0.475%     0.005%     0.005%
          P99        4.290%     4.129%     3.706%     1.486%     0.298%     0.162%

  LN-API  P50        2.281%     0.182%     0.000%     0.000%     0.000%     0.000%
          P95       20.256%     3.963%     0.080%     0.040%     0.040%     0.000%
          P99       11.951%     3.594%     0.086%     0.000%     0.029%     0.000%

  Bimodal P50        1.381%     0.394%     0.394%     0.197%     0.197%     0.197%
          P95        3.918%     0.172%     0.012%     0.028%     0.038%     0.008%
          P99        1.521%     1.344%     0.543%     0.078%     0.016%     0.014%

  Expon   P50        1.012%     0.000%     0.145%     0.145%     0.145%     0.000%
          P95       10.989%     0.200%     0.000%     0.000%     0.033%     0.033%
          P99       18.665%     4.574%     0.824%     0.022%     0.022%     0.022%

  LN-DB   P50        2.018%     0.034%     0.000%     0.000%     0.000%     0.034%
          P95        2.027%     0.368%     0.039%     0.006%     0.019%     0.026%
          P99        3.764%     1.066%     0.187%     0.007%     0.003%     0.062%

  Sequent P50        0.095%     0.000%     0.000%     0.000%     0.000%     0.000%
          P95        2.271%     1.967%     1.011%     0.496%     0.000%     0.000%
          P99        4.272%     4.118%     3.696%     1.521%     0.305%     0.169%

  Pareto  P50       10.127%     1.899%     0.633%     0.633%     0.633%     0.000%
          P95        9.239%     0.272%     0.000%     0.136%     0.000%     0.000%
          P99        3.517%     0.879%     0.231%     0.093%     0.046%     0.046%

  --------------------------------------------------------------------------------
  Buckets                65        128        252        496        976       1920
  Mem/slot            520 B     1.0 KB     2.0 KB     3.9 KB     7.6 KB    15.0 KB
  Mem total          1.0 KB     2.0 KB     3.9 KB     7.8 KB    15.2 KB    30.0 KB
  --------------------------------------------------------------------------------
```

Distributions: Uniform [0, 1M], Log-normal API latency (σ=0.5),
Bimodal cache hit/miss (90/10), Exponential IO wait, Log-normal DB query
(σ=1.0), Sequential [1..N], Pareto heavy tail (α=1.5).

## License

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