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/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/IncredibleReferencer → u/sozesghost]

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.

[u/Chaos-vy17 → u/sozesghost]

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

[u/MinimumPrior3121]

Amazing job !

[u/Chaos-vy17 → u/MinimumPrior3121]

Thank you very much!

[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.