Show HN: ChaosTree – A zero-dependency Java tree library (AVL,RBT,B-Tree,B+Tree)

Show HN: ChaosTree – A zero-dependency Java tree library (AVL,RBT,B-Tree,B+Tree)(github.com)

9 points by chaos_vy 1 day ago | 9 comments

What is ChaosTree?

ChaosTree is a zero-dependency Java Sorted Set/Map library built around multiple tree implementations.

It provides implementations of: - AVL Tree - Red-Black Tree - B-Tree - B+Tree

I have not made my custom API as it implements NavigableSet, NavigableMap, SequencedSet and SequencedMap. My Custome API are: - buildFromSorted(Iterator> it, float factor) - importFlatMatrix(Object[][] blast, float factor) - Object[][] exportFlatMatrix()

I started ChaosTree because I wanted to explore how far I could learn DS structure, It started as frst release of 7 tree of Set type with Custome API, As i got engrossed into it I moved to Map, During phase of switching from Set to Map there was drastic change and knowledge upgrade where I pushed my Tree limit from jdk11+ support to jdk21+ where paid close attention to dependency-free and memory layout, allocation,JVM behavior, and real-world performance.

Some of the things I experimented with: - Different node layouts and metadata footprints - CRTP/F-bounded polymorphism for tree implementations - Parent-pointer vs parentless nodes - Array-based N-ary tree nodes - B-Tree/B+Tree degree selection - JMH benchmarking and JFR profiling - Differential/randomized testing against java.util.TreeMap/TreeSet

After this rough and tough It also passes these test:

-Guava Testlib compatibility testing -jqwik property-based testing -Randomized differential testing against reference collections -White-box structural validation of tree nodes -Direct validation of B-Tree/B+Tree structural invariants -Exception and iterator-contract testing -Serialization and cloning tests -Nary Tree uses custom jqwick test of API validation as well.

Tail latency behavior is not shown here because it get's truncated into a simple text which made the dat read wrong:https://chaos-vy.github.io/ChaosTree/utils/JMH-Report.html I have also ran benchmark with official JDK TreeMapUpdate to my N-ary tree.

GitHub: https://github.com/Chaos-vy/ChaosTree https://chaos-vy.github.io/ChaosTree/

I'd especially like feedback on the API design, implementation choices, benchmark methodology. I am currently trying to truncate useless and complex branches for performnace tuning.

my-next-account 1 day ago |

You should add an intrusive variant of all the trees.

chaos_vy 1 day ago | |

Intrusive trees are great for specialized use cases, but not for a general-purpose Java Collection. If the payload owns the left/right pointers, the same object can't cleanly participate in multiple Maps/Sets.

ChaosTree keeps the tree topology separate from the domain objects, which is necessary for a NavigableMap-style collection.

my-next-account 1 day ago | | |

You can have both! You can of course implement the non-intrusive case on top of the intrusive one. I think that opens up interesting use cases with Valhalla.

MiroslavPokorny 1 day ago |

Does this really need to be JDK 21 ?

I personally require libs that are JDK 11.

pron 1 day ago | |

Upgrading JDK versions isn't all that much work, and it offers very significant benefits especially when it comes to performance. Applications that don't upgrade don't have the resources to do even that; they're in minimal maintenance mode. Does it make sense, then, for a library that offers some new feature that requires at least some code change to use, to target users who don't have the resources even for a runtime upgrade?

Applications that don't upgrade their runtime are usually not in the market for new libraries (or even new features in old libraries).

vbezhenar 1 day ago | |

If you need, you can trivially backport the code to JDK 11. All new Java features are essentially syntax sugar and trivial to rewrite with early Java code. Just ask LLM, they're really good and mundane and trivial rewrites.

chaos_vy 1 day ago | |

It uses sealed classes, JDK21 SequencedSet and SequencedMap implementation, Math.clamp(), and get benifit from modern JIT optimization.

MiroslavPokorny 1 day ago | | |

That not much to jump all the way to jdk21.

Math.clamp is literally 2 / 3 lines.