Arena Map Benchmark: ChaosTree vs JDK, Fastutil, Eclipse

One repeatable mixed workload of get, put and remove on sorted maps, at 10K, 100K and 1M entries. Score is time per operation (ns/op), single-threaded. Lower is better.

Violet marks the winner. Error (JMH 99.9% confidence interval) is drawn at lower opacity than the data.

1. What this benchmark measures

The map is filled once with size keys, inserted by plain put in shuffled order (seed 42). Then every invocation runs 100,000 operations read from a pre-generated pool of 2M packed (op, key) entries. Keys are uniform over 0 … 2×size-1. The cursor advances between invocations, so the map evolves and no rebuild happens between them. Keys and values are pre-boxed Integers, so the timed loop does no RNG work and allocates nothing. Results go to a Blackhole. The op stream is identical for every map at a given seed and mix.

A mix such as 50,25,25 means 50% get, 25% put, 25% remove. Mixes with equal put and remove (50,25,25, 20,40,40, 80,10,10) hold the tree near half full. Mixes with 0% remove saturate the tree, so they measure lookup and overwrite on a full tree.

2. System and reproduction

I did ArenaObject in multiple files (10k,100K,1M) as the ETA: 3hr

java -jar ct-benchmark/target/benchmarks.jar ArenaObject \
  -p size=10000,100000,1000000 -f 3 -wi 10 -w 1s -i 10 -r 1s \
  -jvmArgsAppend "-Xms4g -Xmx4g -XX:+AlwaysPreTouch -XX:+UseParallelGC"

java -jar ct-benchmark/target/benchmarks.jar ArenaPrimitive \
  -p size=10000,100000,1000000 -f 3 -wi 10 -w 1s -i 10 -r 1s \
  -jvmArgsAppend "-Xms4g -Xmx4g -XX:+AlwaysPreTouch -XX:+UseParallelGC"

3. Results

4. How to read this page

5. Caveats

• ChaosBPlusTree and ChaosAVL at 100K are from a rerun of the identical command, because the first pass had wide errors (±32 and ±70). Other rows with wide errors (EclipseRBT, ChaosRBT) may be inflated the same way. Same way there were three combination which had error varying around might be 10~12% which did go through reran.
• No rebuild between invocations. The map evolves across the run, so results reflect steady-state churn, not a fresh build.
• 0%-remove mixes run on a saturated tree and are not comparable to the put=remove mixes.
• Boxing. Every map except the two IntNative ones uses boxed Integer keys. The IntNative maps are Fastutil at its best (no boxing, no Comparable calls), so they are a ceiling reference, not a like-for-like competitor. They come from a separate class and run with the same workload code, seed and mixes.
• JDKConcurrentSkipListMap pays for concurrency this single-threaded benchmark does not use.

6. Findings:

• FastUtil lacks an O(N) bulk-load: FastUtil does not have an O(N) bulk-load capability (like buildFromSorted()). When initialized with sorted data, it falls back to sequential O(log N) put() calls. To maintain a level playing field, bulk-loading benchmarks were excluded from this arena.
• Where is MapDB? MapDB was initially included, but even its in-memory modes rely heavily on serialization and byte-array copying. This generated a massive GC footprint that severely degraded benchmark stability and polluted the heap, even at the lowest datasets. It was ultimately excluded for fairness.
• N-ary Tree Iterator Escape Analysis (EA): B+Tree iterators are streamlined enough that they consistently benefit from JVM Escape Analysis and are completely scalar-replaced (zero heap allocation). In contrast, B-Tree iterators require complex traversal state, which defeats EA and forces a 40B heap allocation per iterator. To strictly adhere to JDK interface contracts, aggressive iterator reuse/flyweight patterns were avoided, leaving the allocation intact.

← Back to ChaosTree