This is the raw, authentic journey of tracking down the exact cause of tail latency (p1.00) between the JDK TreeMap and ChaosTree. It didn't start with perfect results. It started with a flawed benchmark.
My first attempt at running the Mode.sample benchmark was flawed because I was using Java's autoboxing. This accidental overhead generated massive 2ms ~ 4ms GC pauses in both TreeMap and ChaosTree at 100K elements.
After finding this fault, I redesigned the benchmark to pre-allocate objects rather than autoboxing them on the fly. This isolated the true cost of the data structures themselves.
Once autoboxing was fixed, I ran the benchmarks at w=3, f=3, i=10 (each 1s) at 100K on an i5 13450HX 16-core processor.
The results were phenomenal. The B+Tree and B-Tree never showed a single Stop-The-World GC pause. My absolute highest tail latency (p1.00) was around 150us.
Then came the interesting part. I ran TreeMap under the exact same configuration. It caught a massive Stop-the-World GC pause clocking in at 2383.272us (2.3ms).
I thought I made a mistake, so I reran it. The next time it increased even further: 5922.816µs (5.9ms)!
Seeing this, I thought my benchmark was broken again, so I immediately repeated the ChaosTree benchmark to verify. The result? Both Chaos trees came out at a maximum tail latency of ~142µs. ChaosTree remained completely unfazed.
If you want to reproduce these results, you cannot just run a standard JMH jar. To prevent OS-level page faults from skewing the tail latency, you must force the JVM to pre-allocate memory. To ensure apples-to-apples GC behavior, the garbage collector must be pinned.
Here is the exact command used to execute the benchmark and capture the JVM logs:
java -jar ct-benchmark/target/benchmarks.jar TreeMapVsBTreeVsBPlusBenchmark.treeMapPutRemove -p n=1000000 -bm sample -f 3 -wi 3 -i 10 -jvmArgsAppend "-Xms4g -Xmx4g -XX:+UseParallelGC -XX:+AlwaysPreTouch -Xlog:safepoint=info,gc*=info:file=jvm_pauses.log:time,uptime,pid:filecount=5,filesize=100M"
-Xms4g -Xmx4g: Locks the JVM heap to exactly 4GB to prevent heap resizing pauses during the benchmark.-XX:+AlwaysPreTouch: Forces the JVM to touch all memory pages during startup, preventing OS page faults from artificially inflating the p1.00 latency during the actual benchmark.-XX:+UseParallelGC: Pins the garbage collector to Parallel GC for deterministic, measurable throughput pauses.-Xlog:safepoint=info,gc*=info: Captures the exact GC pause times and safepoint events, allowing cross-referencing of JMH tail latency directly against the JVM's internal GC logs.
To find out exactly what was happening, I used JVM logs (preserved in ct-benchmark/BenchmarkLog). The culprit was the JDK's Map.Entry allocation.
It doesn't hit on every iteration, but in a matrix of 30 samples, the massive GC pause hits 3 or 4 times for the JDK, while ChaosTree completely evades it.
Here is the raw data showcasing the incredible difference at the p1.00 percentile:
It was only one time in 1/30 measurement. Rest measurement were all good, If I leave this specific one it also landed below 150 us/op. (Sometime it might spike more than one time)
TreeMapVsBTreeVsBPlusBenchmark.treeMapPutRemove 100000 sample 303827 0.573 ± 0.064 us/op TreeMapVsBTreeVsBPlusBenchmark.treeMapPutRemove:p0.999 100000 sample 5.080 us/op TreeMapVsBTreeVsBPlusBenchmark.treeMapPutRemove:p0.9999 100000 sample 13.626 us/op TreeMapVsBTreeVsBPlusBenchmark.treeMapPutRemove:p1.00 100000 sample 5922.816 us/op
TreeMapVsBTreeVsBPlusBenchmark.bTreeMapPutRemove 100000 sample 742165 0.427 ± 0.001 us/op TreeMapVsBTreeVsBPlusBenchmark.bTreeMapPutRemove:p0.999 100000 sample 3.787 us/op TreeMapVsBTreeVsBPlusBenchmark.bTreeMapPutRemove:p0.9999 100000 sample 6.851 us/op TreeMapVsBTreeVsBPlusBenchmark.bTreeMapPutRemove:p1.00 100000 sample 105.600 us/op
TreeMapVsBTreeVsBPlusBenchmark.bTreeMapPutRemove 100000 sample 2338495 0.427 ± 0.001 us/op TreeMapVsBTreeVsBPlusBenchmark.bTreeMapPutRemove:p0.999 100000 sample 3.686 us/op TreeMapVsBTreeVsBPlusBenchmark.bTreeMapPutRemove:p0.9999 100000 sample 6.746 us/op TreeMapVsBTreeVsBPlusBenchmark.bTreeMapPutRemove:p1.00 100000 sample 136.960 us/op
These were the astonishing feats that ChaosTree achieved.