RFR: 8367332: Replace BlockTree tree logic with an intrusive red-black tree
Casper Norrbin
cnorrbin at openjdk.org
Thu Sep 11 09:47:44 UTC 2025
Hi everyone,
Metaspace's `BlockTree` is currently implemented as a simple binary search tree, using the memory blocks it stores as the nodes. While this is straightforward and generally fine, it can become unbalanced depending on insert/remove order, leading to degraded performance.
This is a good fit for the utilities `IntrusiveRBTree`, instead of using internal tree logic. With it, we can replace all tree functions and instead rely on a few insert/remove calls. `BlockTree` still remains as the layer coordinating these blocks, and still handles the list of same-size nodes. The intrusive red-black tree only handles balancing and linking/unlinking nodes in the tree structure.
Validation and printing are preserved by using the hooks provided by the red-black tree. We keep the same checks (and get a few more from the rb-tree), and the printed output is kept identical. The only real difference is that the red-black tree traverses the tree instead.
Testing:
- Oracle tiers 1-8
-------------
Commit messages:
- moved blocktree tree logic to intrusive rbtree
Changes: https://git.openjdk.org/jdk/pull/27212/files
Webrev: https://webrevs.openjdk.org/?repo=jdk&pr=27212&range=00
Issue: https://bugs.openjdk.org/browse/JDK-8367332
Stats: 380 lines in 3 files changed: 35 ins; 290 del; 55 mod
Patch: https://git.openjdk.org/jdk/pull/27212.diff
Fetch: git fetch https://git.openjdk.org/jdk.git pull/27212/head:pull/27212
PR: https://git.openjdk.org/jdk/pull/27212
More information about the hotspot-runtime-dev
mailing list