SharedHistogram

Cross-process bucketed counter for distribution tracking. Caller supplies N bucket boundaries at create time; record(v) finds the right bucket via binary search and atomically increments its counter. K boundaries -> K+1 buckets (overflow on top).

The “cross-process latency / size distribution at lock-free cost” primitive. record at 13.06 ns vs Mutex<Vec<u64>> 15.73 ns (1.20x faster). count at 1.70 ns vs 16.94 ns (9.96x faster - lock-free atomic load vs full lock cycle). percentile p99 at 95.81 ns. Architectural lever: each bucket’s counter is its own cache line so concurrent recorders into different buckets never contend; the mutex baseline serializes everything regardless of bucket.

Constraints (read first):

• Native sidecar integration: the struct carries a HandshakeHeader + ObservationRing and implements subetha_sidecar::AdaptiveInstance. Wrap in SidecarBox::new to register with the global sidecar; raw create() / open() return the unregistered type unchanged.

• Boundaries fixed at create: ascending; verified at open.

• K boundaries -> K+1 buckets: bucket 0 = v < b0, bucket i = b{i-1} <= v < bi, bucket N = v >= b{N-1}.

• Per-bucket AtomicU64 counters: independent cache lines.

• fetch_add(1, AcqRel) per record; lock-free, no spin.

• percentile(p) walks buckets accumulating counts + linear interpolation. Granularity = bucket width.

• Cross-process backed by MMF.

Table of contents

• What it is
• Bench evidence
• Worked examples
• Use case patterns
• Known limitations
• Common pitfalls
• References

What it is

    block-beta
  columns 1
  hdr["HistogramHeader - 64 B: magic, n_boundaries, total_count (atomic)"]
  b["boundaries [u64; K] - ascending"]
  c["counters [AtomicU64; K + 1] - per-bucket counts"]
  classDef hdrC fill:#1e3a8a,color:#ffffff
  classDef bC fill:#475569,color:#ffffff
  classDef cC fill:#0f766e,color:#ffffff
  class hdr hdrC
  class b bC
  class c cC
  

Bench evidence

Bench harness: crates/subetha-cxc/benches/shared_histogram.rs. Captured 2026-06-02 on Windows 11 / Zen+ R7 2700, Criterion with --sample-size=15 --warm-up-time=1 --measurement-time=2.

Workload: 7 latency boundaries [10, 100, 1k, 10k, 100k, 1M], record value 500 (bucket 3).

Reading the trade-offs

1. record 1.20x faster: binary search of 7 boundaries + one atomic fetch_add vs mutex lock + indexing + increment + unlock.
2. count 9.96x faster: one atomic load vs full lock cycle.
3. Concurrent recording win is multiplied (not measured here): different buckets = different cache lines = no contention. Mutex baseline serializes ALL recorders.
4. percentile p99 at 96 ns: linear walk + interpolation; granularity is bucket width.

Rule 3b bench audit

• Fair contender: Mutex<Vec<u64>> with same boundaries + same binary-search bucket lookup. Identical protocol shape.
• No thread::spawn inside b.iter: single-threaded.
• Sizing: 7-boundary histogram (typical latency dashboard config); record 1000 then percentile.
• MMF lifecycle managed: create + ops + drop + remove_file.

What the numbers do NOT show

• Cross-process recording: N processes each record into the same histogram via lock-free fetch_add; observers query percentiles without locks.
• Concurrent recording into different buckets scales linearly: distinct cache lines mean no contention. Mutex baseline serializes all recorders.
• Latency dashboard pattern: cheap concurrent recording + cheap observer reads makes real-time p99 monitoring feasible.

Worked examples

Basic latency tracking

use subetha_cxc::SharedHistogram;

let h = SharedHistogram::create("/tmp/lat.bin",
    &[10, 100, 1_000, 10_000, 100_000, 1_000_000]).unwrap();
for &lat_us in latencies.iter() {
    h.record(lat_us);
}
let p50 = h.percentile(0.50);
let p99 = h.percentile(0.99);
println!("p50={p50} p99={p99}");

Cross-process aggregate dashboard

// Each worker:
let h = SharedHistogram::open("/tmp/lat.bin",
    &[10, 100, 1_000, 10_000, 100_000, 1_000_000]).unwrap();
let start = std::time::Instant::now();
do_request();
h.record(start.elapsed().as_micros() as u64);

// Dashboard:
let h = SharedHistogram::open("/tmp/lat.bin", &[/*same bounds*/]).unwrap();
println!("p99: {} us", h.percentile(0.99));

Use case patterns

Pattern: cross-process latency distribution

Each worker records request latency; dashboard reads p50/p99/p999 without polling logs.

Pattern: queue-depth sampling

Periodic sampler records queue depths; an observer computes distribution stats.

Pattern: request-size or memory-allocation distribution

Anything bucketable. Boundaries chosen log-spaced for wide dynamic range with bounded memory.

Known limitations

• Boundaries fixed at create: no auto-rebucket.
• Percentile granularity = bucket width: coarse boundaries give coarse percentiles.
• No min / max tracking: callers track separately if needed.
• u64 counters: 2^64 records per bucket cap (practically unreachable).
• Cross-process backed by MMF.

Common pitfalls

• Linear-spaced boundaries for wide-range data. Latencies span 6+ decades; use log-spaced bounds [10, 100, 1k, 10k, …].

• Mismatched boundaries at open. Open verifies boundaries match the creator’s; pin in a shared spec.

• Reading percentile during heavy recording. percentile walks all buckets with Acquire loads; concurrent fetch_add is fine but the percentile may shift between reads. Read total_count first as a snapshot anchor.

• Wrapping in a Mutex. Pointless; per-bucket fetch_add is already the synchronization mechanism.

References

• Source: crates/subetha-cxc/src/shared_histogram.rs (581 lines, unit tests covering record + bucket placement, percentile, cross-handle visibility, boundary validation, and out-of-bounds rejection).
• Bench: crates/subetha-cxc/benches/shared_histogram.rs (record, count, percentile_p99 vs Mutex<Vec<u64>>).
• Sibling primitive: SHARED_COUNT_MIN_SKETCH.md - per-key frequency estimate (probabilistic); Histogram is per-bucket exact count.
• Sibling primitive: SHARED_HYPER_LOG_LOG.md - cardinality estimate (distinct count).
• Sibling primitive: SHARED_RESERVOIR_SAMPLER.md - uniform random sample; Histogram is the aggregate-by- bucket variant.