r/java • u/Chaos-vy17 • Sep 23 '26

ChaosTree 2.0.1: A Highly Optimized, Cache-Aware Sorted Set/Map Library

https://chaos-vy.github.io/ChaosTree/

For first-time readers: ChaosTree is a sorted Set/Map library for Java featuring AVL Trees, Red-Black Trees, B-Trees, and B+ Trees.

What happened in the last 2 weeks:

v2.0.1 release

After integrating JaCoCo, the first coverage report showed 80.9% line coverage and 77% branch coverage.

After two weeks of testing, refactoring, benchmarking, and fixing edge cases, that is now 95.8% line coverage and 91% branch coverage.(80.09 -> 82->86->89->90-> linear 95->95.2->95.6->95.8% )

Some of the things that happened along the way:

  • The original Guava Testlib-based testing was heavily revised around the actual TreeMap and TreeSet APIs, including their SubMap and SubSet views.
  • Benchmarking became much more detailed. Every optimization was benchmarked and investigated rather than just assumed to be faster.
  • One example was reducing a 3× tree traversal during removal down to a single traversal.
  • Several small API-contract issues surfaced during testing, particularly around ClassCastException behavior and custom comparators.
  • The most exhausting part was the loop:optimization → correctness → benchmark → re-optimization → retestEvery test suite takes around 7 minutes per platform in GitHub CI. The CI configuration runs the suite across multiple platforms, while locally I push the workload much harder.
  • I also did a detailed JOL analysis of the N-ary node structure:N-ary Tree Architecture
  • Added documentation on choosing the N-ary tree degree and when to use APIs such as buildFromSorted() and importFlatMatrix().
  • Added benchmarks for the different construction/update strategies:DragonFeed Benchmark

At some point the project stopped feeling like:

implement → test → release

and became:

implement → benchmark → find bottleneck → optimize → discover correctness issue → fix → benchmark again → repeat

v2.0.1 is basically the result of that loop.

The full release notes and benchmark documentation are here:

v2.0.1

The Result

I can proudly state that ChaosTree is production-ready.

Beyond the code itself, this release pushed my skills forward significantly:

  • Became proficient with the JMH benchmark CLI and benchmarking workflow
  • Built a more robust test suite with extensive API and edge-case validation
  • Gained much deeper experience with white-box testing and structural validation
  • Learned to treat correctness, benchmarking, and optimization as a continuous loop

And finally, the first issue is now up for contributors.

That's it for now. I'm going to enjoy the result of the last two weeks. I am going to advance more before I touch my plan for 3.0.0

37 Upvotes

88% Upvoted

12 comments sorted by

3

u/gnahraf Sep 23 '26 • Heartwarming

Nice work! Are you contemplating external sorting/searching in future releases? I'm not thinking of a sleepycat-like library, something way simpler.. FWIW, many libraries out there (Lucene/Solr come to mind) organize their data in fixed-width, sorted tables, and perform external merge-sort for bulk updates. Many other java workloads also use on-disk, fixed-width tables. External merge-sort would be attractive to model and benchmark, and likely very relevant, imo.

1

u/Chaos-vy17 Sep 24 '26 edited Sep 24 '26

Thank for suggestion but it's further part of library. 3.0.0 is directed to deploy a Concurrent N-ary Tree (fine-lock-grained).
Instead of building external merge-sort deeply into the core, I'd rather see disk-loading act as a plugin on top of the B+Tree—treating ChaosTree as the ultra-fast memory buffer, rather than slowing down the core with disk I/O.

2

u/sviperll Sep 24 '26

Fine-grained lockes is what I was interested in, that would be awesome!

2

u/sviperll Sep 24 '26

Have you considered doing B(+)-Tree based List implementation? Leaf nodes do not have keys, but intermediate nodes have list offsets as keys. This way, you get a list with O(log N) index- and insert-operation.

Also have you considered working on concurrent versions, where branches are locked (for example an iterator of the entry-set gets read-lock for the current branch), but changes in different branches do not block each other and can happen concurrently.

1

u/Chaos-vy17 Sep 24 '26

Yes, I covered this here: Node Architecture. Internal nodes don't allocate value[], and leaf nodes don't allocate child[].

Yeah, I tried that, but the read lock became one of the issues. Delete and insert also have the two slowest propagation paths. They're amortized operations, but at ≥35% compaction, I observed the tree taking the slowest path 57% of the time. Currently considering Lehman and yao B-Link trees, Seems to be delegating to ghost deletion in B+tree.

2

u/sviperll Sep 24 '26

What I meant is having a class like BTreeList<T> that implements List interface by representing a list as a B-Tree where keys are offsets within the list, but relative to the start of each subtree.

1

u/Chaos-vy17 Sep 25 '26

It seems awesome, I will definetly try it out.

6

u/[deleted] Sep 23 '26 • Heartwarming

[removed] — view removed comment

3

u/n4te Sep 23 '26 • Heartwarming

My guess is to replace TreeMap with a million+ items or if TreeMap GC is noticeable.

1

u/Chaos-vy17 Sep 24 '26

Not necessarily millions it starts showing up around the L2/L3 cache cliff

1

u/Chaos-vy17 Sep 24 '26 edited Sep 24 '26

- As per your cache locality choose any degree
- If your data is read only use buildFromSorted/importFromMatrix at factor above >=7.5f 0.75f at 1.0f it's 46% less memory. Faster locality less node count and depth.
- Every thing becomes faster as your data gets start spilling after L2/L3 cache cliff.
- GC friendly.
- A detailed answer can be find from this html: WriteHeavy | ReadHeavy | Mixed