English | 中文 | Español

Note: The initial draft of this README was generated by AI (Antigravity) based on real-machine benchmark tests and source code architecture analysis, and subsequently reviewed and fine-tuned by the project author.

HdrHistogram-Kotlin is a high-performance, High Dynamic Range (HDR) histogram library specifically built for Kotlin Multiplatform (KMP), benchmarked against and inspired by Gil Tene's official Java native implementation HdrHistogram.

It supports recording and analyzing sampled data value distributions across a configurable integer range with configurable relative precision (number of significant digits). It is designed specifically for latency-sensitive performance monitoring, APM, network testing, system metrics, and related use cases.

• Core Features
• Why HDR Histogram?
• Supported Platforms
• Core API & Architecture
• Quick Start
  • 1. Basic Single-Threaded Histogram (Histogram)
  • 2. Concurrent Lock-Free Recording (Recorder)
  • 3. Multi-Threaded Atomic Histogram (AtomicHistogram)
• Performance Benchmarks (Benchmark Report)
  • Test Machine Environment & Methodology
  • Cross-Session Consistency (What Actually Reproduces)
  • 1. JVM Throughput Comparison (Throughput - Mean of 3 Forks)
  • 2. JVM Write Latency Comparison (Latency - Mean of 3 Forks)
  • 3. Memory Footprint & Zero-Allocation Testing
  • 4. JVM Statistics Query and Reset Latency
  • 5. KMP Cross-Platform Performance (JVM vs WasmJS vs JS)
• Commands to Reproduce Benchmarks
• Low-Level Performance Analysis & Design Comparison
  • Why the wins are wins
  • Why the losses are not losses
• Acknowledgments & License

• Constant Space and Time Complexity: Physical memory footprint is constant, determined entirely by the configured value range and precision at construction; zero memory allocations (Zero GC / Allocation-free) during value recording, with no linked lists, hash tables, or dynamic array resizing overhead.
• Branchless Bitwise Addressing: Computes bucket and sub-bucket indices directly using countLeadingZeroBits (hardware CPU CLZ instruction) and bitmasks, eliminating if branches from critical hot paths.
• Efficient Concurrency & Double Buffering:
  • The double-buffering Recorder is built on a two-phase rotating synchronizer (WriterReaderPhaser). Writer threads record data with just a single atomic increment, while reader threads periodically flip phases to extract interval snapshots without locking active writers.
  • AtomicHistogram leverages CPU hardware-level atomic bus instructions (XADD / LDADD) to support high-concurrency multi-threaded writes directly.
• Native Kotlin Multiplatform Support: A unified codebase fully covers JVM, Android, Linux (x64), macOS/iOS (Native), WebAssembly (WasmJS), and JavaScript.

In system performance monitoring (such as SLAs, service latencies, and transaction durations), averages often conceal critical tail latencies (such as the 99.9th or 99.99th percentile request spikes).

Traditional histograms either use fixed-width linear buckets (causing memory explosion over large dynamic ranges) or coarse logarithmic buckets (causing severe loss of resolution at higher values).

The HDR Histogram Solution: HDR Histograms partition ranges adaptively based on a configured number of Significant Value Digits:

• For example, configured with a precision of 3 (guaranteeing relative resolution better than 0.1%):
  • In the $1,\mu\text{s} \sim 2,\text{ms}$ range, resolution is accurate to $1,\mu\text{s}$;
  • In the $2,\text{ms} \sim 2,\text{s}$ range, resolution is accurate to $1,\text{ms}$;
  • In the $2,\text{s} \sim 2,000,\text{s}$ range, resolution is accurate to $1,\text{s}$.
• Regardless of the magnitude of the measured value, measurement error is strictly bounded within 0.1%, while the entire histogram occupies only tens to hundreds of kilobytes of memory.

classDiagram
    direction TB
    class Histogram {
        +totalCount: Long
        +minValue: Long
        +maxValue: Long
        +mean: Double
        +recordValue(value: Long, count: Long)
        +valueAtPercentile(percentile: Double) Long
        +add(other: HistogramCoreAlg)
        +reset()
    }

    class AtomicHistogram {
        +totalCount: Long
        +minValue: Long
        +maxValue: Long
        +mean: Double
        +recordValue(value: Long, count: Long)
        +valueAtPercentile(percentile: Double) Long
        +reset()
    }

    class Recorder {
        +recordValue(value: Long, count: Long)
        +getIntervalHistogram(histogramToRecycle: Histogram?) Histogram
    }

    Recorder ..> Histogram : produces interval
    Recorder ..> AtomicHistogram : internal buffer (concurrent)

1. Histogram: Non-thread-safe base histogram with nanosecond-level recording speed, suitable for single-threaded, coroutine-confined, or batch aggregation scenarios.
2. AtomicHistogram: Lock-free histogram supporting high-concurrency multi-threaded writes, backed by atomic arrays.
3. Recorder: Double-buffered recorder prioritized for throughput. Worker threads record lock-free, while a background reporting thread periodically extracts interval snapshots without stalling writers.

Add the dependency to your build.gradle.kts:

repositories {
    mavenCentral()
}

kotlin {
    sourceSets {
        commonMain.dependencies {
            implementation("io.github.dsqrwym:hdrhistogram-kotlin:0.0.2")
        }
    }
}

Suitable for single-threaded recording, offline log analysis, or as an aggregation container:

import io.github.dsqrwym.hdrhistogram.Histogram

// Create a histogram: lowest discernible value 1ns, highest trackable value 1 hour (3.6e12 ns), 3 significant digits (0.1% precision)
val histogram = Histogram(
    lowestDiscernibleValue = 1L,
    highestTrackableValue = 3_600_000_000_000L,
    numberOfSignificantValueDigits = 3
)

// Record latency measurements (nanoseconds)
histogram.recordValue(1_500L)
histogram.recordValue(25_000L)
histogram.recordValue(100_000L, count = 10L) // Batch record 10 occurrences

// Query key metrics
println("Total count:  ${histogram.totalCount}")
println("Min value:    ${histogram.minValue} ns")
println("Max value:    ${histogram.maxValue} ns")
println("Mean:         ${histogram.mean} ns")
println("P50 Median:   ${histogram.valueAtPercentile(50.0)} ns")
println("P99:          ${histogram.valueAtPercentile(99.0)} ns")
println("P99.9:        ${histogram.valueAtPercentile(99.9)} ns")

// Reset the histogram (without reallocating memory)
histogram.reset()

Recommended for continuous high-throughput recording (e.g., API gateways, RPC services, trading engines) where metrics are reported periodically in the background:

import io.github.dsqrwym.hdrhistogram.Recorder
import io.github.dsqrwym.hdrhistogram.Histogram
import kotlinx.coroutines.*
import kotlin.time.Duration.Companion.milliseconds

val recorder = Recorder(
    lowestDiscernibleValue = 1_000L,         // 1 microsecond
    highestTrackableValue = 60_000_000_000L, // 60 seconds
    numberOfSignificantValueDigits = 3
)

// Simulate multiple concurrent writer threads / coroutines
repeat(8) {
    CoroutineScope(Dispatchers.Default).launch {
        while (isActive) {
            val latencyNs = measureRequestTime()
            recorder.recordValue(latencyNs)
        }
    }
}

// Independent metric collection and logging thread (e.g. collecting every 10 ms)
CoroutineScope(Dispatchers.Default).launch {
    // Passing null initially allocates a Histogram instance on the heap;
    // Passing the same instance back to getIntervalHistogram on subsequent cycles resets and reuses it with zero GC allocation.
    var recycleHistogram: Histogram? = null
    while (isActive) {
        delay(10.milliseconds)
        
        // Flip phase and seamlessly obtain interval histogram, reusing the old instance
        recycleHistogram = recorder.getIntervalHistogram(recycleHistogram)
        
        println("Interval count: ${recycleHistogram.totalCount}, " +
                "P99: ${recycleHistogram.valueAtPercentile(99.0)} ns, " +
                "P99.9: ${recycleHistogram.valueAtPercentile(99.9)} ns")
    }
}

Used when multiple threads concurrently record directly into a single shared histogram:

import io.github.dsqrwym.hdrhistogram.AtomicHistogram

val atomicHistogram = AtomicHistogram(
    lowestDiscernibleValue = 1L,
    highestTrackableValue = 10_000_000L,
    numberOfSignificantValueDigits = 3
)

// Can be called concurrently from any thread; utilizes atomic instructions under the hood
atomicHistogram.recordValue(12345L)

Important Note: The atomicity of AtomicHistogram only guarantees thread safety for write operations (no lost counts or data races). However, concurrent reads (such as calling valueAtPercentile) do not provide a globally consistent atomic snapshot across all buckets (i.e. writing threads may update subsequent buckets while a reader traverses the array). For production scenarios requiring high-frequency multi-threaded writes alongside periodic consistent metric reads, always use Recorder.

To provide rigorous and objective data, we compared this project against the official native Java library (org.hdrhistogram:HdrHistogram:2.2.2) under identical hardware and runtime conditions (including Gil Tene's 1:1 benchmark logic, typical workload models, and memory overhead).

• Processor (CPU): AMD Ryzen 5 7530U with Radeon Graphics (6 cores / 12 threads, base 2.0 GHz, boost 4.5 GHz)

• Memory (RAM): 16 GB DDR4 (15.3 GB usable)

• Operating System: Windows 11 64-bit (build 26300)

• Java Runtime: Eclipse Temurin 25.0.3 (OpenJDK HotSpot, build 25.0.3+9-LTS)

• Node.js Runtime: v24.15.0 (used for JS and WasmJS tests)

• Benchmark Framework: kotlinx-benchmark 0.5.0 (based on JMH 1.37)

• Methodology — no cherry-picking, ever: every number in the tables below is the arithmetic mean of all forks × all measurement iterations of one single run (3 forks × 5 iterations = 15 measurements per row), with JMH's 99.9% confidence interval. Nothing is selected per benchmark, and no row is taken from a different session than the one it is compared against.

• Session selection: the suite (all 38 JVM benchmarks, both libraries, back-to-back, ~16 min per session) was executed three full times — sessions 2026-10-31 17:39, 18:32 and 18:48. To choose one session as a whole, the official library is used as a machine-state probe (its code never changes), aggregating its three recording-throughput benchmarks, together with the fork-level dispersion of all 38 rows:

  Session	Official probe (sum of 3 Java thrpt, M ops/s)	Mean fork spread	Mean relative CI	Forks beyond ±15%
  17:39 (used for the tables)	848.7	7.1%	6.9%	3
  18:32	836.6	9.4%	8.4%	2
  18:48	715.7	6.9%	7.2%	1

  Session 1 was the healthiest (highest probe, dispersion tied for lowest) and is therefore reported in full. Session 3's probe is 16% lower on an idle-identical machine — a direct measurement of how much "absolute numbers" drift.

• How to read the numbers: a 3-fork, same-session comparison reliably resolves effects above ~15% and nothing smaller. Percentages below that must be treated as measurement noise until a high-fork rerun confirms them, and the ratio columns in the consistency table below are the honest way to see it. Concretely: the official rawRecordingSpeed baseline measured 244M ops/s in an older session on this machine and 332M in the reported one, and the official recordConstant forks inside one session averaged 342M / 211M / 288M on identical code.

The same suite run three times gives ratios (Kotlin / Java) rather than absolute numbers. For thrpt rows, > 1 means this project is faster; for avgt (time) rows, < 1 means this project is faster:

11-fork arbitration. Three sessions agreeing on direction was still not enough for the sub-15% effects, so the three disputed rows were re-measured with 11 forks (55 measurement iterations each), both libraries in the same session:

The lesson is stated explicitly, because it is the whole point of this section: on this machine a 3-fork same-session A/B resolves ~15% and nothing smaller, and a 3/3 direction agreement across three 3-fork sessions still does not fix the sign of a sub-15% effect. No benchmark row below is claimed as a win or a loss that this arbitration could not confirm.

Unit: ops/sec (operations completed per second). Higher is better.

Merge Operation Comparison (add)

Unit: µs/op (microseconds per merge). Lower is better. JMH, 3 forks × (3 warm-up + 5 measurement iterations of 1 s), 1-hour nanosecond range, 3 significant digits, 2,000 recorded samples, 44,032 count slots.

Unit: ns/op (nanoseconds per operation). Lower is better.

One of the defining designs of HDR Histogram is its strictly constant and minimal physical memory footprint, along with zero heap allocations (Zero Allocation) while recording data.

Because over 99.9% of histogram memory is occupied by the underlying LongArray count storage, memory consumption is determined entirely by constructor parameters (object headers and fields take only ~100 bytes). Values below are the actual measured array sizes (test.JvmMemoryAllocationTest):

• Identical layout: both libraries produce exactly the same number of count slots for the same (lowestDiscernibleValue, highestTrackableValue, numberOfSignificantValueDigits) — the test asserts this. The residual 448-byte gap in the last two columns is only the object-header constant each side assumes (512 B vs. 64 B), not a measured difference in live memory.
• Constant Footprint: Whether recording 1 value or 1 billion samples, the physical footprint remains strictly constant, with zero dynamic array resizing (asserted after 200,000 recordings).
• Direct Calculation: The underlying array size can be derived directly via countsArrayLength * 8 bytes.

To verify zero-allocation claims empirically, we used JVM's com.sun.management.ThreadMXBean.getThreadAllocatedBytes() to inspect the actual heap bytes allocated by the operating system and JVM to the thread before and after massive operations, after class loading and JIT warmup. Each row below corresponds to an assertion that runs in the test suite (JvmMemoryAllocationTest, AddOracleTest, CoordinatedOmissionOracleTest, StdDeviationOracleTest):

Evaluated on a pre-populated histogram containing 100,000 realistic samples spanning $\mu\text{s}$ to tail ms (same-session measurement).

All percentile and getter rows are parity: they scanned the same algorithm with no algorithmic difference, and every apparent 2–20% deficit collapsed under the 11-fork arbitration. They are listed anyway, because the failure to reproduce is the finding.

Benefiting from pure bitwise logic and zero-allocation design, this library demonstrates exceptional performance on WebAssembly (Wasm). Each of these three columns is a whole run of the same 19-benchmark suite, selected by the same no-cherry-picking rule used for the JVM tables (JS and WasmJS were each run 3 times; the run with the lowest mean relative confidence interval and an aggregate throughput within 2% of the best was kept, run-for-run):

Cross-Platform Recommendation: When collecting high-frequency performance metrics in browser or Node.js environments, WasmJS is strongly recommended: 19x–38x the write throughput of plain JS (write latency 8.4 ns versus 217 ns), and full-array work stays usable — mean in 31 $\mu\text{s}$ instead of 1.1 ms, a same-layout merge in 53 $\mu\text{s}$ instead of 617 $\mu\text{s}$.

How wide is the JS/Wasm variance? Larger than the JVM numbers. Across the three runs of the identical suite: Wasm rawRecordingSpeed came out 115.1 / 133.4 / 131.9 M (16% spread), Wasm mergeSameLayout 63.3 / 51.9 / 52.6 $\mu\text{s}$ (22% spread), and JS recordConstant 5.49 / 4.93 / 6.42 M (a 30% spread on a 5-iteration run with a 0.6% confidence interval). That gap between "tight CI" and "unstable mean" is exactly why these columns are single complete runs, and why they should be read as orders of magnitude: the JS built-in harness reports a confidence interval that does not capture cross-run variance, so it underestimates the real uncertainty by roughly an order of magnitude. Note too that the Wasm/JS advantage shrinks where both ends become memory-bound: recordVarying is 37.6x, but mergeSameLayout is only 11.7x.

You can reproduce all benchmark data locally using the project's Gradle tasks:

# Run full JVM benchmarks (including both official Java library and this project).
# Note: this uses JMH's default fork count.
./gradlew :library:jvmBenchmarkBenchmark

# Reproduce exactly the 3-fork sessions reported above: build the JMH jar and run it yourself.
./gradlew :library:jvmBenchmarkBenchmarkJar

& "$env:JAVA_HOME\bin\java.exe" -jar library/build/benchmarks/jvmBenchmark/jars/library-jvmBenchmark-jmh-0.0.2-JMH.jar `
    -f 3 -wi 3 -i 5 -r 1s -w 1s -rf json -rff build/bench-results/jvm-all.json

# Arbitrate a disputed sub-15% effect at higher resolution (11 forks = 55 measurement iterations per row).
# The regex below selects the three rows discussed in the consistency table, both libraries.
& "$env:JAVA_HOME\bin\java.exe" -jar library/build/benchmarks/jvmBenchmark/jars/library-jvmBenchmark-jmh-0.0.2-JMH.jar `
    'getMaxValue$|getP50$|rawRecordingLatency$' `
    -f 11 -wi 3 -i 5 -r 1s -w 1s -rf json -rff build/bench-results/jvm-hifork.json

Benchmark output is written under build/ on purpose: it is generated data, not a source of the repository, and every table above can be regenerated by re-running the commands. Each Gradle benchmark run also writes a JSON snapshot to library/build/reports/benchmarks/main/<timestamp>/<target>.json.

# Run JVM ThreadMXBean-based heap allocation and footprint tests
./gradlew :library:jvmTest --tests "test.JvmMemoryAllocationTest"

# Requires Node.js installed locally
./gradlew :library:wasmJsBenchmarkBenchmark

./gradlew :library:jsBenchmarkBenchmark

# Run all unit tests across platforms (including multi-threaded consistency tests)
./gradlew allTests

Current status of the suite (same working tree as the tables above): JVM 71 tests / JS 45 tests / WasmJS 45 tests, all passing, including the differential tests against the official Java library (AddOracleTest, EqualsOracleTest, CoordinatedOmissionOracleTest, StdDeviationOracleTest).

Gil Tene's branchless bucket mapping algorithm based on leading zeros (leadingZeroCountBase - Long.numberOfLeadingZeros(value | subBucketMask)) forms the mathematical cornerstone enabling HDR Histograms to record in nanoseconds.

While inheriting this mathematical model, this project introduces focused engineering simplifications:

1. Elimination of Normalizing Index Offset (normalizingIndexOffset): The official library resolves every count slot through normalizeIndex(index, normalizingIndexOffset, arrayLength) so that auto-resizing and the double-valued histograms can rotate the array instead of moving data. For integer histograms that call hits its documented fast path (if (normalizingIndexOffset == 0) return index, AbstractHistogram.java:2443), so the real cost is one extra field load plus a predictable branch per slot touch, not a modulo. This project maps indices straight to the physical array.
2. End-to-End Inlining (inline): Core operators such as countsArrayIndex, bucketIndex, and lowestEquivalentValue are marked as inline. In combination with Kotlin's compiler inlining, this eliminates call stack frame overhead and virtual method dispatch. (Note the official side pays this too: incrementCountAtIndex, addToCountAtIndex and getCountAtIndex are abstract in AbstractHistogram and only resolved by HotSpot through monomorphic devirtualization.)
3. Direct Array Traversal for Mean Calculation (mean): Official Java's getMean() drives the pre-allocated RecordedValuesIterator, and every step materializes a full HistogramIterationValue (iteration bounds, running totals, percentile level — AbstractHistogram.java:1385-1397). This project iterates directly across the physical LongArray, calculating equivalent midpoint values on non-zero buckets without heap allocations or iterator state overhead.
4. Non-atomic bookkeeping on the non-thread-safe path: The official Histogram is documented as not thread-safe, yet per recorded sample it still performs incrementTotalCount() — an AtomicLongFieldUpdater.getAndIncrement, i.e. a lock xadd read-modify-write (AbstractHistogram.java:176, 566) — and reads the two volatile fields maxValue / minNonZeroValue in updateMinAndMax (lines 125-126, 537-544), escalating to a CAS spin loop only when the sample is a new extreme (lines 197-223). This project keeps plain fields in Histogram and confines atomic operations to AtomicHistogram, so the recording hot path carries no atomic read-modify-write and no memory barrier.
5. Explicit range checks instead of an exception-driven ones: The official record path wraps the counter store in try { ... } catch (IndexOutOfBoundsException) and repairs state in handleRecordException so it can support auto-resize (AbstractHistogram.java:546-577); a negative value check lives in countsArrayIndex (line 2398). This project replaces that with a plain require(value in 0..highestTrackableValue) plus require(count > 0). That is the one place where this project deliberately adds instructions to the hot path: two predictable branches in exchange for a store that is not wrapped in an exception-covered region.

• mean (~5.2x, reproduces in 3/3 sessions within 1% of the same ratio): this is the only algorithmic difference in the whole suite. The official getMean() drives RecordedValuesIterator, whose hasNext()/next() maintain a 12-field HistogramIterationValue object — iteration bounds, cumulativeCount, totalCountToThisValue, percentileLevelIteratedTo — and update all of it per reported slot. This project scans the flat LongArray with an inlined accessor and touches nothing else. The query benchmark's histogram holds 15,360 slots of which only a few thousand are non-empty: both libraries pay a load-and-test for the empty ones, but only one of them additionally runs the iterator's state machine over the non-empty ones — that is where the 5x comes from.
• Same-layout merge (1.5–1.9x): add is O(countsArrayLength) = 44,032 slots, so a per-slot saving is multiplied 44,032 times. The official loop (AbstractHistogram.java:741-747) does a virtual getCountAtIndex, a count > 0 branch, a virtual addToCountAtIndex, and a normalizeIndex per slot. Ours is an unconditional counts[i] += other.countAtIndex(i), which HotSpot auto-vectorizes. We have independent evidence that the branch is the expensive part: adding a count > 0 guard to our loop made it 29–53% slower by breaking vectorization — and the official loop has exactly that guard.
• recordVarying (+7% ~ +15% throughput, 5–13% lower latency, 3/3 sessions): this workload spreads 65,536 values over multiple orders of magnitude, so the counts array misses cache and each sample's cost is dominated by memory latency. That is precisely where removing a lock xadd per sample pays off, because the atomic's read-modify-write cannot be overlapped with the load it serializes against.
• recordConstantLatency (~5%, 3/3 sessions): the smallest effect that stayed signed in every session. Same slot every time, everything in L1, so the removed atomic and volatile reads are the only difference left — consistent with it being small and real.

Nothing in the suite is a demonstrated regression, but three rows looked like one and had to be disproved rather than argued away:

• Percentiles and maxValue appeared 2–20% behind in all three sessions with a consistent sign. At 11 forks, getP50 measured 691.66 ± 37.68 ns (official) versus 692.67 ± 17.00 ns (ours) — a 0.15% difference — and getMaxValue flipped to a 9% lead. Both loops are the same single linear scan with the same early exit, so there is no algorithmic difference to exploit; the "loss" was the machine, not the code.
• rawRecordingLatency looked 8% behind at 3 forks and 11% ahead at 11 forks. This is the same workload as rawRecordingSpeed, where the throughput rows disagreed with each other across sessions (+6.5% / −9.0% / +5.3%) — an effect that changes sign when you measure it twice is not an effect.
• One thing the code review did turn up, recorded here as a shared inefficiency rather than as an asymmetry: both libraries evaluate the leading-zero / bucket chain twice per call inside highestEquivalentValue(v) — ours as lowestEquivalentValue(v) + sizeOfEquivalentValueRange(v) - 1, the official as nextNonEquivalentValue(v) = lowestEquivalentValue(v) + sizeOfEquivalentValueRange(v) (AbstractHistogram.java:1203-1229). So this cannot explain any gap relative to the official library; it is simply a cheap fix available on our side (valueFromIndex(countsArrayIndex(v) + 1) - 1 computes the chain once), and it sits on the path of maxValue and of the exit of every percentile scan — exactly the rows whose apparent losses evaporated at 11 forks. Proving the fix helps would itself require an 11-fork comparison.

Resolution limit, stated as a rule: on this machine (laptop Zen 3, single-thread JMH, no isolation) a 3-fork same-session comparison resolves ~15% and nothing smaller; three such sessions agreeing on direction still do not fix the sign of a sub-15% effect. Any change below that threshold requires an 11-fork (or multi-session-repeated) arbitration before it goes into a table.

• Licensed under the Apache License 2.0.
• Core algorithms, data structures, and mathematical models originate from the outstanding work of Gil Tene: HdrHistogram. Many thanks to the original author and the community for providing such an exceptional performance metric infrastructure to the open-source ecosystem.