Benchmark: add statistical aggregation, throughput-window mode, and richer result reporting

[jtnelson]

Background

com.cinchapi.common.profile.Benchmark is widely used across Cinchapi projects for measuring server-side and end-to-end timing. cinchapi/concourse alone has 17+ benchmark tests built on it, plus several test classes in concourse-server (e.g. TMapsTest, DatabaseTest, SegmentTest, StoresTest, ByteableCollectionsTest, CompiledInfingramTest).

The current API exposes only the arithmetic mean (average(int)) and total elapsed (run(int)), which limits its usefulness in noise-prone CI environments where outliers dominate single-shot runs and a single mean can be misleading. Concrete CI evidence: the same Concourse code produced 1952 - 4557 ops/sec (2.3x spread) for OpsPerSecondTest.testVerifyAndSwap across four CircleCI shards on the same commit.

This issue tracks improvements needed to make Benchmark a credible regression-detection primitive for the cross-version benchmark suite in cinchapi/concourse.

Current API surface

• Benchmark.run() returns single-sample elapsed (long)
• Benchmark.run(int n) returns sum of n elapsed times (long)
• Benchmark.average(int n) returns arithmetic mean (double)
• Builder path: measure(Runnable).in(TimeUnit).warmups(int).async()?.run() / run(n) / average(n)

No median, no percentiles, no min/max, no stddev, no outlier rejection, no throughput-window mode, no rich result object.

Gaps blocking better testing

1. Statistical aggregation — median (p50), p95, p99, min, max, stddev. A single mean is fragile under GC pauses on shared CI infrastructure; we routinely see 2-2.5x variance on the same code across CI shards.
2. Throughput-window mode — for tests that measure ops/sec over a fixed time window rather than latency over a fixed iteration count (e.g. Concourse's TransactionThroughputTest, OpsPerSecondTest, AbstractTransporterThroughputTest). These tests roll their own loop with System.currentTimeMillis() today.
3. Rich result object — a BenchmarkResult (or similar) carrying min/max/mean/median/percentiles/iterations/totalElapsed in one object so callers do not have to run twice to print two stats.
4. Outlier trimming — drop top/bottom k samples before aggregating (trimmed mean), a cheap defense against single-GC-pause outliers.

Proposed API sketch

Existing API stays compatible. New chainable configuration on the builder:

BenchmarkResult result = Benchmark.measure(() -> ...)
        .in(TimeUnit.MILLISECONDS)
        .warmups(3)
        .iterations(10)
        .reportPercentiles(50, 95, 99)
        .trimOutliers(1, 1)   // drop top 1 and bottom 1
        .run();               // returns BenchmarkResult

New throughput-window mode for ops/sec measurement:

BenchmarkResult result = Benchmark.measure(() -> ...)
        .in(TimeUnit.SECONDS)
        .warmups(2)
        .runFor(Duration.ofSeconds(10));
// result.throughput()  => ops/sec
// result.iterations()  => total ops completed
// result.totalElapsed() => actual wall time

BenchmarkResult exposes:

• min(), max(), mean(), median()
• percentile(double p) for arbitrary percentile
• stddev()
• iterations(), totalElapsed(), throughput() (when runFor was used)
• samples() for raw per-iteration samples so callers can do their own analysis

Implementation Plan

1. Introduce BenchmarkResult with the fields above. Keep it immutable.
2. Add iterations(int), reportPercentiles(int...), trimOutliers(int low, int high), runFor(Duration) to the builder.
3. Update the abstract-class instance API (Benchmark subclassing path) to support the same configuration via setter methods or by routing through the builder internally.
4. Make warmup runs explicitly excluded from the result aggregation (today warmups(int) exists on the builder but its semantics relative to average(int) are not documented).
5. Add unit tests that:
   • Verify percentile math on a known sample distribution
   • Verify runFor(Duration) runs at least N iterations within tolerance and reports the right throughput
   • Verify warmup samples are excluded from the result
   • Verify trimmed-mean math drops the requested top/bottom k samples
6. Update Javadoc to describe the new contract end-to-end.

Acceptance Criteria

• BenchmarkResult exposes min, max, mean, median, p95, p99, stddev, iterations, totalElapsed, throughput, samples
• Builder gains iterations(int), reportPercentiles(int...), trimOutliers(int low, int high), runFor(Duration)
• Existing run(), run(int), average(int) continue to compile and behave unchanged
• Warmup runs are documented as excluded from result aggregation
• Unit tests cover percentile math, throughput-window mode, warmup exclusion, and outlier trimming

Out of scope (file separately if pursued)

• Forked-JVM isolation (JMH-style)
• Multi-thread workload generation
• JIT dead-code-elimination prevention via Blackhole-equivalent
• Annotation-based parameterization (@Param)

Caller using this work

cinchapi/concourse will depend on this in its perf-test hardening effort.

[jtnelson]

Recommendation: back this with HDR Histogram, and add two API refinements the original sketch doesn't cover

Building on the design above, I want to flag two gaps that came up while planning the consumer side of this work (the new concourse-bench harness under cinchapi/concourse#739). Both are addressable inside the API shape already proposed, but require explicit decisions before implementation begins.

1. Storage backend: HDR Histogram

Rolling our own percentile aggregation works at small N but produces subtly wrong numbers at the scale benchmarks actually run at (millions of samples), and the alternatives have known tradeoffs we shouldn't relitigate.

Option	Verdict for this use case
HDR Histogram (org.hdrhistogram:HdrHistogram)	Recommended. ~80KB jar, no transitive deps. Constant memory regardless of sample count. Lossless aggregation across recorders. Industry standard (Cassandra, Kafka, gRPC, wrk2). Built-in coordinated-omission correction.
TDigest	Better when the value range is unknown. For latency it isn't — we know it's non-negative, finite, and has a useful upper bound. HDR is the better fit here.
Apache DataSketches	Designed for distributed sketches and approximate joins. Overkill.
Roll our own (sorted array + index math)	Works under a few million samples; falls apart on merging across recorders and on streaming-quantile efficiency. Avoid.

HDR's design assumptions match Benchmark's use case exactly: known range, need fast recordValue in the hot loop, need precise percentiles after the fact, need to merge histograms across threads/processes/runs.

2. Coordinated omission — the closed-loop vs open-loop distinction

This is the single biggest reason most homegrown benchmark harnesses produce p99/p999 numbers that look great but don't match production behavior. Concrete example: a closed-loop benchmark loop measures end - start per call. One call hits a 500ms GC pause. The next 100 calls don't start until that one finishes — they back-pressure. Naive measurement records those 100 calls with their nominal latencies (say, 1ms each) and misses that they were actually delayed by hundreds of milliseconds of queue time. Your p99 reports ~1ms when production users actually saw hundreds of milliseconds.

HDR Histogram has the fix built in: recordValueWithExpectedInterval(value, expectedInterval) interpolates the missing samples. But the caller has to know whether they're running closed-loop (need the correction) or open-loop (don't — the arrival process itself models contention).

The API needs to expose this distinction explicitly. Proposed delta to the builder:

// Closed-loop (default): caller loops as fast as possible; HDR corrects for
// coordinated omission against the expected per-iteration interval.
BenchmarkResult result = Benchmark.measure(() -> ...)
        .iterations(100_000)
        .expectedInterval(Duration.ofMicros(100))  // target per-op interval
        .reportPercentiles(50, 95, 99, 999)
        .run();

// Open-loop: caller drives arrivals externally (e.g., Poisson schedule).
// No coordinated-omission correction; each recorded value is independent.
BenchmarkResult result = Benchmark.measure(() -> ...)
        .arrival(ArrivalProcess.openLoop())
        .runFor(Duration.ofMinutes(5))
        .reportPercentiles(50, 95, 99, 999)
        .run();

Closed-loop is the right default since it matches the existing semantics of run(int n) and average(int n). The expectedInterval is optional — if omitted, HDR's correction is disabled (matching today's naive behavior, so existing callers see no surprises). Documenting that omitting it underreports tail latencies is the key thing.

3. Mergeable BenchmarkResult

The original sketch's BenchmarkResult is final and standalone, which is right. The one capability to add: lossless merge between two results.

BenchmarkResult a = thread1Result;
BenchmarkResult b = thread2Result;
BenchmarkResult combined = a.merge(b);   // p99 of the union, not the average

This becomes essential the moment any consumer runs multi-threaded workloads (which concourse-bench will), or aggregates CI runs over time. HDR makes this trivial because Histogram already supports add(Histogram) losslessly. Without HDR backing, this is hard to do correctly — you can't compute the merged p99 from two pre-aggregated p99s.

Expose the underlying Histogram too, for consumers that want to do their own analysis (e.g., the concourse-bench results-publication pipeline merges histograms across nightly runs into long-term trends):

Histogram raw = result.histogram();    // org.HdrHistogram.Histogram

Integration plan

Concretely, on top of the implementation plan already in the ticket:

1. Dependency. Add org.hdrhistogram:HdrHistogram:2.1.12 (or current) to accent4j's build.gradle. ~80KB, no transitive deps, mature library, Apache 2.0 licensed.
2. Internal data structure. Each Benchmark execution maintains one Histogram per recording phase (warmup vs measurement). Default configuration:

   Histogram h = new Histogram(
       1L,                              // lowestDiscernibleValue (1 ns)
       TimeUnit.MINUTES.toNanos(1),     // highestTrackableValue
       3                                // numberOfSignificantValueDigits
   );

   This is ~5KB per histogram and covers the full µs-to-minute range at three significant digits. Expose the bounds and precision as builder options for edge cases (Benchmark.measure(...).histogramBounds(...)), but the defaults above will be right for >95% of callers.
3. Hot loop changes. In the measurement loop:

   long start = System.nanoTime();
   action.run();
   long elapsed = System.nanoTime() - start;
   if (expectedIntervalNanos > 0) {
       histogram.recordValueWithExpectedInterval(elapsed, expectedIntervalNanos);
   }
   else {
       histogram.recordValue(elapsed);
   }

4. BenchmarkResult becomes a thin wrapper. Most accessors delegate to Histogram:

   public double mean() { return histogram.getMean(); }
   public long min() { return histogram.getMinValue(); }
   public long max() { return histogram.getMaxValue(); }
   public double stddev() { return histogram.getStdDeviation(); }
   public long percentile(double p) {
       return histogram.getValueAtPercentile(p);
   }
   public BenchmarkResult merge(BenchmarkResult other) {
       Histogram merged = histogram.copy();
       merged.add(other.histogram);
       return new BenchmarkResult(merged, /* ... */);
   }

5. samples() from the original sketch. Drop it from the API. The whole point of the histogram is that we don't keep per-iteration samples in memory at scale. If a caller really needs them (rare), they can subclass Benchmark and record to their own list in addition to the histogram. Document that explicitly in the Javadoc.
6. Outlier trimming. Reframe in HDR terms: trimOutliers(double lowPercentile, double highPercentile) filters the reported aggregate to values between those percentiles. The histogram itself keeps everything; trimming is a view, not a destructive operation.
7. Tests. Add to the existing test plan in the ticket:
   • Verify HDR-merged percentiles match the union percentile from two known input distributions
   • Verify recordValueWithExpectedInterval produces measurably different (worse, more honest) p99 than recordValue on a workload with injected stalls
   • Verify histogram() returns the same Histogram instance across BenchmarkResult accessor calls (no defensive copying in the hot path)

Backwards compatibility

The existing API (run(), run(int), average(int)) keeps working unchanged. Internally those methods build a Benchmark configured with no expectedInterval (matching today's naive recording), record into a Histogram, and return the scalar the caller expects. New consumers get the rich BenchmarkResult via the builder path.

The one observable behavior change worth documenting in the changelog: average(int) will now compute the mean from the histogram rather than from a separate accumulator. For unimodal distributions the two are within rounding error; for distributions with extreme tails the histogram is more accurate.

Risks

• Default histogram bounds (1 ns to 1 min, 3 sig figs) — values above the max get clamped to the highest tracked value. Document this; provide a builder hook to widen the range. For pathological workloads (multi-minute operations) callers can configure their own bounds.
• recordValueWithExpectedInterval is the right default but changes p99 numbers vs naive recording. When this lands, expect existing benchmark results (cross-version tables, CI history) to show p99 jumps on workloads that previously suffered from coordinated omission. That's the bug, not the regression — but it's worth a CHANGELOG note so it doesn't look like a real perf regression.
• HDR Histogram is in the org.HdrHistogram package (capital H). Cosmetic, not a real issue, but worth flagging since it's an unusual convention.

Downstream commitment

If this lands with HDR backing as described, cinchapi/concourse#740 (concourse-bench harness) commits to consuming BenchmarkResult directly without wrapping it — the harness becomes thin glue rather than a parallel statistics layer. That simplification was the main reason for tracking this work as an upstream prereq.