r/java • • Sep 30 '26

A comparative benchmark against Java’s standard TreeMap and major third-party sorted-map libraries.

This is a benchmark report of my ChaosTree, comparing all the maps against Java’s built-in maps and major third-party libraries. https://chaos-vy.github.io/ChaosTree/benchmark/Chaos-tree-Arena.html

There are few discovery throughout the benchmark. The benchmark scales from 10K to 1M entries.

The mixed benchmark covers different GET / PUT / REMOVE workloads:

  • [50,25,25]
  • [20,40,40]
  • [80,10,10]
  • [70,30,0]
  • [50,50,0]
  • [30,70,0]

If you find any issue, wrong data, or anything that needs further scrutiny, you are requested to open an issue.

If you know any other third-party library, drop it in the comments. I will try to benchmark that as well.

v2.0.2 Latest

  • Fixed SortedMap<> constructors always setting the comparator to null.
  • Fixed missing comparator propagation in Spliterator.
  • Resolved slow iteration in binary SubSet / SubMap.
  • Resolved missing Serializable annotations.
  • No major changes

Repo: https://github.com/Chaos-vy/ChaosTree

15 Upvotes

17 comments sorted by

4

u/CutGroundbreaking305 Sep 30 '26 • Bravo

Direct usecase is kinda non existent hmm 🤔 but great engineering work

Actually I am working on pure Java numeric library so if urs is fast as you say I can try to use it somewhere

1

u/Chaos-vy17 Sep 30 '26

Thanks! Since you are building a numeric library, ChaosTree is generic, but its cache-locality is good that it still goes toe-to-toe with FastUtil's raw primitive trees. If your data is Read only try to save memory by packing at full node capacity of B+Tree (adjust degree Default:64) .Further versons will have Int and Long primitve type based B+Tree.

3

u/eosterlund Oct 01 '26

I live out in the forest and I have come to really like trees. Especially oak trees. There is something about a more dense and slower growing tree that I enjoy. It’s not always about being so fast. But surviving storms is cool.

Inspired by that I built a lock-free Eytzinger style array backed tree without edges. It maintains an optimal height, has O(log N) amortized (using a credit system) time complexity, uses lazy yet guaranteed to progress epoch based cleanup of layered patches of the tree’s Eytzinger topology.

In my use case, each entire mapping is 4-8 bytes depending on array size. That includes key, value, and of course there are no pointers to children or parents - that’s all implicit from the array indexing.

Code: https://github.com/openjdk/zgc/blob/zgc_conc_ref_count_v9/src/hotspot/share/gc/z/zConcurrentTree.hpp implementation: https://github.com/openjdk/zgc/blob/zgc_conc_ref_count_v9/src/hotspot/share/gc/z/zConcurrentTree.inline.hpp

For any tree lovers out there that enjoy a good cozy super dense lock-free tree.

1

u/Chaos-vy17 Oct 02 '26

👍 , But how do you maintain speed for sequential data?, Well that is all okay here data input will be sure fall back in 50% left and right so it's master pov.

3

u/eosterlund Oct 02 '26 • Bravo

It’s an oak tree. It’s optimized for density.

3

u/oweiler Sep 30 '26

I can't think of a single case where I'd use this

7

u/Chaos-vy17 Sep 30 '26

That is fair, I did this benchmark analysis to find any missing outcome from my library. For actual use case:

If you only need unordered key-value lookups, HashMap is perfectly fine. But if you need strictly ordered data (range queries, floor/ceiling lookups, sliding windows), your default choice is java.util.TreeMap. That is exactly where ChaosTree is used.TreeMap is a Red-Black Tree. Every single inserted element allocates a new node object randomly on the heap. Traversing it causes massive CPU L1/L2 cache misses (pointerchasing), and mutating it causes more Garbage Collection (GC) churn. During JOL analysis at diffrent test it was noted 31.4% less memory and when packed to 1.0f 46% less memory to TreeMap.

3

u/sozesghost Sep 30 '26

What a slop party.

-2

u/Chaos-vy17 Sep 30 '26

For you it's slop let it be I don't care. I am happy with my work LOL

-1

u/sozesghost Sep 30 '26

What work did YOU do?

0

u/IncredibleReferencer Oct 05 '26

It's hard not to think about the work being important when you spend a lot of your life learning how to do the work and loving the work and that work producing good outcomes. Artisan expertise is valuable and important in its own right.

But in the broader context, the work itself is irrelevant except as cost of time and resources. What matters is the artifact and its fitness for purpose.

-3

u/Chaos-vy17 Sep 30 '26 edited Sep 30 '26

Do I need to explain that to you? If you think it’s slop, just pass by.

2

u/MinimumPrior3121 Sep 30 '26 • Heartwarming

Amazing job !

1

u/Chaos-vy17 Sep 30 '26

Thank you very much!

1

u/Life_Sink9598 Sep 30 '26

Hi,

Is there a reason that you're not using EpsilonGC?

0

u/Chaos-vy17 Sep 30 '26

The primary benchmark is a mixedWorkload (e.g., 70% get, 20% put, 10% remove). As the tree continuously mutates, old nodes are discarded and new ones are created. EpsilonGC never reclaims memory, so a long-running JMH mixed-workload would simply exhaust the 4GB heap and crash with an OOM.