ChaosTree: Explicit Benchmark Analysis

This document breaks down the mechanical reasons why ChaosTree dominates the JDK baseline in standard, non-bulk operations.

1. Randomized Insertion (10% Faster)

The first benchmark tests the standard use case: feeding completely random, unsorted keys into the map one by one using put().

The Mechanical Reason:

Randomized insertion is the absolute worst-case scenario for any tree structure because it guarantees CPU cache misses (pointer chasing across the heap). Even in this worst-case scenario, ChaosTree beats the JDK by 10%.

It achieves this through the 12-element linear search threshold (preventing branch-prediction pipeline flushes on small nodes) and the Structure-of-Arrays (SoA) layout. While the JDK is busy allocating millions of 16-byte Map.Entry objects and fragmenting the heap, ChaosTree is gracefully sliding keys into pre-allocated contiguous arrays, minimizing Garbage Collection pauses and maximizing L1/L2 cache hits during traversal.

2. Sorted Insertion (3.2x Faster)

The second benchmark feeds strictly sorted, monotonically increasing data into the map one by one using standard put() (not the bulk loader).

The Mechanical Reason: Append and Split

Inserting sorted data into a standard Red-Black Tree (like JDK TreeMap) is a pathological workload. Because the data is monotonically increasing, the tree constantly becomes right-heavy. To maintain its strict balancing constraints, the Red-Black tree is forced to trigger heavy O(log N) tree rotations on almost every single insert.

ChaosTree, however, thrives on sorted data. Because of the dummy overflow slot (which allocates 2t array indices but sets maxKeys = 2t - 1), ChaosTree does not need to preemptively balance.

When you insert sorted data, ChaosTree simply appends the new key to the end of the right-most node's contiguous array in O(1) time. It keeps appending until the array hits exactly 2t capacity. Only then does it execute a clean, predictable splitNode operation to pop the separator up, and then instantly resumes appending to the new right-most leaf.

This "Append and Split" pipeline is infinitely cheaper than constant Red-Black tree rotations. It turns a heavily fragmented tree operation into a smooth, sequential array-fill, resulting in a staggering 3.2x speedup over the JDK.

3. The Bulk Load Progression (O(N) vs O(N))

The ultimate test of a data structure is ingestion at scale. When fed pre-sorted data, both ChaosTree and the JDK TreeMap abandon iterative O(log N) insertions and switch to specialized O(N) bulk-loading algorithms.

I benchmarked three specific ingestion paths for 1,000,000 elements:

The Mechanical Reason: The Dragon Feed

The JDK's buildFromSorted is an O(N) algorithm, but it still allocates a Map.Entry wrapper for every single element, causing massive Garbage Collection overhead and memory fragmentation.

When ChaosTree uses its standard buildFromSorted(Iterator), it easily beats the JDK (36.6ms vs 50.6ms) simply because it builds cache-friendly arrays instead of object wrappers.

But the true masterpiece is the Dragon Feed (importFlatMatrix()). By completely bypassing the Iterator state-machine and accepting a raw 2D array matrix (Object[][] blast), the engine uses native System.arraycopy() to rip the data directly into the tree's memory blocks.

The result is an ingestion engine that is nearly 10x faster than the JDK's fastest possible build path. It reduces 50 milliseconds of CPU execution time down to just 5 milliseconds. It is the absolute physical speed limit of the JVM.

4. The Impossible Iteration (Beating ArrayList)

After optimizing insertions and bulk loads, the final test was to measure iteration speed. I wanted to see how fast ChaosTree could iterate over 1,000,000 elements compared to a standard JDK TreeMap and a raw, flat ArrayList.

The benchmark results were entirely unexpected. Not only did ChaosTree obliterate the JDK TreeMap, it actually executed faster than a raw ArrayList.

Benchmark                                          Score (ms/op)   Allocated (B/op)
-----------------------------------------------------------------------------------
ChaosTreeMapIterateBenchmark.iterateChaosTree        2.540 ± 0.132      8.7
ChaosTreeMapIterateBenchmark.iterateRawArrayList     3.090 ± 0.213     10.6
ChaosTreeMapIterateBenchmark.iterateJavaTreeMap     20.650 ± 3.691     70.6

The Mechanical Reason: Overriding forEach

Standard Java collections use the Iterator interface for advanced for loops. This forces the JVM to constantly check hasNext(), verify expectedModCount, and maintain traversal state on every single element. For standard TreeMap, this overhead causes iteration to drag out to 20.6 milliseconds.

To bypass this, BPlusTreeMap explicitly overrides the forEach() method. Because all values in a B+Tree are stored in a contiguous linked-list of leaf nodes, the forEach override ignores the tree structure entirely. It grabs the first leaf node and executes a raw, hardware-level pointer walk (currentLeaf = currentLeaf.next), blasting through the pre-fetched array blocks.

Because this batched array traversal avoids the constant per-index ArrayIndexOutOfBoundsException bounds-checking that the JVM must execute on a standard ArrayList for loop, ChaosTree actually achieves an iteration speed (2.5ms) that is physically faster than a flat array (3.0ms).

5. The JDK Benchmark Gauntlet (No Cheating Allowed)

To prove the engine's speed, I knew the benchmarks had to be absolutely legitimate. Instead of writing my own custom benchmarks that might favor ChaosTree's architecture, I directly copied the JDK's own internal TreeMap benchmark suite. I forced ChaosTree to play on the JDK's home turf.

The 1-Hour Disappointment

I ran the suite for 1 hour and 13 minutes. When the results came back, I was deeply disappointed: only a single function was faster than the JDK.

I dove into the source code and realized exactly what was happening. ChaosTree's views (like subMap and descendingMap) were falling back to Java's default interface methods (like java.util.Map.computeIfAbsent). As discussed earlier, these default methods perform devastating double-traversals (a get followed by a put). The benchmark was exposing the overhead of generic Java interfaces.

The Override War

What followed was an absolute war of optimization. I refused to alter the benchmark code to make ChaosTree look better. My rule was strict: The benchmark is never implicitly altered, and I expect all future PRs and Issues to follow the same standard.

Instead of cheating the test, I optimized the engine. Every time an API ran slowly because of a default method fallback, I explicitly overrode it in the concrete classes. Every single override stripped away virtual dispatch and enforced single-traversal paths. Optimization by optimization, override by override, ChaosTree clawed its way to equal footing with the JDK—and then completely surpassed it.

A Note on jcstress

As a final note, the concurrent testing (validating that ChaosTree properly throws ConcurrentModificationException on structural interference) was powered by jcstress (Java Concurrency Stress tests). It was a random discovery, but with a bit of help from Google, it proved that ChaosTree fails fast and safely under threading chaos.

6. The Master Benchmark Suite (Raw JMH Data)

Below is the complete, unaltered featofChaosTree JMH dataset comparing the three engines across all mutation operations and map views. It explicitly tracks both CPU Execution Time (ns/op) and GC Allocation Rate (B/op).

Analysis: The data proves that across almost every single mutation operation and map view, the BPlusTreeMap completely dominates the baseline JavaTreeMap in both execution speed and Garbage Collection efficiency. The BTreeMap holds its own, consistently beating Java on speed, but paying the structural allocation penalty for internal nodes.

← Back to ChaosTree Home