Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

github.com

Post reply on HN
Print view View original

1–10 of 12 posts

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

#1

Post by chaos_vy »

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.

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

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

#3

Post by chaos_vy »

MiroslavPokorny wrote: post #2

Does this really need to be JDK 21 ? I personally require libs that are JDK 11.

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

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

#4

Post by MiroslavPokorny »

chaos_vy wrote: post #3
MiroslavPokorny wrote: post #2

Does this really need to be JDK 21 ? I personally require libs that are JDK 11.

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

That not much to jump all the way to jdk21.

Math.clamp is literally 2 / 3 lines.

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

#5

Post by chaos_vy »

MiroslavPokorny wrote: post #4
chaos_vy wrote: post #3

Earlier quoted context omitted.

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

That not much to jump all the way to jdk21. Math.clamp is literally 2 / 3 lines.

The Tree Supports JEP431(Sequenced Collection) and my whole node structure is based on pattern match and sealed classes.

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

#6

Post by pron »

MiroslavPokorny wrote: post #2

Does this really need to be JDK 21 ? I personally require libs that are JDK 11.

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

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

#8

Post by chaos_vy »

my-next-account wrote: post #7

You should add an intrusive variant of all the trees.

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.

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

#9

Post by my-next-account »

chaos_vy wrote: post #8
my-next-account wrote: post #7

You should add an intrusive variant of all the trees.

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.

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.

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

#10

Post by vbezhenar »

MiroslavPokorny wrote: post #2

Does this really need to be JDK 21 ? I personally require libs that are JDK 11.

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.
Post reply on HN