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
  • 1. JVM Throughput Comparison (Throughput - Best Single Run)
  • 2. JVM Write Latency Comparison (Latency - Best Single Run)
  • 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
• 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: Histogram)
        +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
• Java Runtime: OpenJDK 64-Bit Server VM (build 25.0.3+11-LTS)
• Node.js Runtime: v24.15.0 (used for JS and WasmJS tests)
• Benchmark Framework: kotlinx-benchmark (based on JMH 1.37)
• Methodology: Executed 3 independent benchmark runs, selecting the overall best-performing full run (Run 2) to ensure temporal and system load consistency across all reported metrics.

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

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):

• Constant Footprint: Whether recording 1 value or 1 billion samples, the physical footprint remains strictly constant, with zero dynamic array resizing.
• 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:

Evaluated on a pre-populated histogram containing 100,000 realistic samples spanning $\mu\text{s}$ to tail ms (data from the best full run).

Benefiting from pure bitwise logic and zero-allocation design, this library demonstrates exceptional performance on WebAssembly (Wasm):

Cross-Platform Recommendation: When collecting high-frequency performance metrics in browser or Node.js environments, WasmJS is strongly recommended—it delivers 25x ~ 80x higher throughput than plain JS, with write latency as low as 7 ~ 9 nanoseconds.

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)
./gradlew :library:jvmBenchmarkBenchmark

# 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

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 Java library dynamically calls normalizeIndex(index, offset, length) during every write to support auto-resizing and floating-point conversions. This project focuses on fixed-range and fixed-precision high-performance integer scenarios, mapping indices directly to the physical array and eliminating an extra addition, modulo, and potential bounds checking branches.
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.
3. Direct Array Traversal for Mean Calculation (mean): Official Java's getMean() instantiates a RecordedValuesIterator to traverse the histogram. This project iterates directly across the physical LongArray, calculating equivalent midpoint values on non-zero buckets without heap allocations or iterator state overhead.

• 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.