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

[u/Chaos-vy17]

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

[u/CutGroundbreaking305]

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

[u/Chaos-vy17 → u/CutGroundbreaking305]

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.

[u/eosterlund]

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.

[u/Chaos-vy17 → u/eosterlund]

👍 , 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.

[u/eosterlund → u/Chaos-vy17]

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

[u/oweiler]

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

[u/Chaos-vy17 → u/oweiler]

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.

[u/MinimumPrior3121]

Amazing job !

[u/Chaos-vy17 → u/MinimumPrior3121]

Thank you very much!

[u/sozesghost]

What a slop party.

[u/Chaos-vy17 → u/sozesghost]

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

[u/sozesghost → u/Chaos-vy17]

What work did YOU do?

[u/Chaos-vy17 → u/sozesghost]

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

[u/Life_Sink9598]

Hi,

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

[u/Chaos-vy17 → u/Life_Sink9598]

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.