Tail latency Benchmark

This is the setup doc: what TreeMapVsBTreeVsBPlusBenchmark builds, what each benchmark method measures, and exactly what the reproduction command does to it. No narrative here, just the mechanics.

1. The Class

One JMH state class, six @Benchmark methods — a Get and a PutRemove for each of TreeMap, BTreeMap, and BPlusTreeMap. Both ChaosTree maps are constructed with DEGREE = 64, so every internal node holds up to 64 children before it splits.

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
@State(Scope.Benchmark)
@Warmup(iterations = 5, time = 2, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 2, timeUnit = TimeUnit.SECONDS)
@Fork(value = 3, jvmArgsAppend = {"-Xms6g", "-Xmx6g"})
public class TreeMapVsBTreeVsBPlusBenchmark {

    private static final int DEGREE = 64;
    @Param({"100000", "1000000"})
    public int n;
    ...
}

Those class-level annotations are defaults, not the last word — every one of them can be, and is, overridden from the command line. @Param({"100000", "1000000"}) is what's in the source; the actual runs on this site use -p n=... on the CLI to override it per run instead of editing the class.

2. The Data Setup — @Setup(Level.Trial)

Runs once per fork, before any timed iteration:

treeMap = new TreeMap<>();
bTreeMap = new BTreeMap<>(DEGREE);
bPlusTreeMap = new BPlusTreeMap<>(DEGREE);

key = new ArrayList<>(n);
value = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
    key.add(i);
    value.add(i);
}
Collections.shuffle(key, new Random(42));
Collections.shuffle(value, new Random(43));

keyDel = new ArrayList<>(key);
Collections.shuffle(keyDel, new Random(44));

for (int i = 0; i < n; i++) {
    treeMap.put(key.get(i), value.get(i));
    bTreeMap.put(key.get(i), value.get(i));
    bPlusTreeMap.put(key.get(i), value.get(i));
}

Three fixed seeds, three different roles: Random(42) shuffles the key order, Random(43) shuffles the value order independently, and Random(44) shuffles a separate copy of the keys (keyDel) that drives deletion order later. Fixed seeds mean every fork, every run, every map gets the exact same insertion and deletion sequence — the only thing that changes between TreeMap, BTreeMap, and BPlusTreeMap is the data structure itself, not the data. All three maps are pre-loaded with all n entries before a single timed op runs.

nextIndex() is a plain round-robin cursor shared by every benchmark method — it walks 0..n-1 and wraps back to 0, so each op touches the next key in the fixed shuffle order rather than a freshly-random one per call. That keeps op-to-op overhead down to the map operation itself, not RNG cost.

3. The Two Workloads

Get is the read path — round-robin through key and look each one up:

@Benchmark
public void treeMapGet(Blackhole bh) {
    bh.consume(treeMap.get(key.get(nextIndex())));
}

PutRemove is the workload that actually matters for tail latency. Each invocation removes a key, then immediately re-inserts the same key with the value that was just removed:

@Benchmark
public void treeMapPutRemove(Blackhole bh) {
    Integer k = keyDel.get(nextIndex());
    Integer removed = treeMap.remove(k);
    bh.consume(treeMap.put(k, removed));
}

That's a deliberate churn pattern — one alloc/dealloc cycle of tree-node and boxed-Integer turnover per op, held at a constant map size forever. Steady-state churn is what exposes GC-driven tail latency; a pure read benchmark never touches the allocator hard enough to show it.

4. The Benchmark Table

PutRemove results only — that's the churn workload section 3 describes, and the one the tail latency actually shows up in. n = 10K / 100K / 1M, heap pinned at 6GB/6GB, 3 forks, 10 warmup + 10 measurement iterations at 500ms each. Each mean carries JMH's own Score ± Error confidence interval.

TreeMap

BTreeMap

BPlusTreeMap

Even After running multiple of time this was the result. There is nothing wrong in the result the Outlier I got was also 1/30(measurement).

← Back to ChaosTree Home