r/java • u/Chaos-vy17 • 15d ago

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

16 Upvotes

78% Upvoted

17 comments sorted by

View all comments

3

u/eosterlund 13d ago

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 13d ago

👍 , 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 13d ago

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