Page MenuHomeFreeBSD

rb_tree: balance interior node removal

Authored by dougm on Jul 27 2022, 4:48 AM.



In RB_REMOVE, when the removed node has non-NULL children, we have to replace the removed node with either its predecessor or successor. We always choose the successor. When the successor is the right child of the removed node, this may immediately produce imbalance, and that imbalance is handled with a rotation in RB_REMOVE_COLOR that moves the successor from its new position with a left child back down where it started, without a left child.

To avoid unnecessary rotation, and an invocation of RB_AUGMENT for a successor node that hasn't actually changed, this change has the implementation choose between the predecessor and successor in order to preserve balance, for those cases where the right child of the removed node is its successor.

Test Plan

An iommu-like test app that repeatedly either inserts the first free value or deletes a randomly selected value produced these stats on the various cases:

T: A removed node needed to be replaced: 213775606
A: The successor was not the right child: 111150552 (51.99%)
B: The successor was right child, and predecessor was not left child: 18210957 (8.52%)
C: Successor and predecessor were children, and successor had a right child: 18210957 (7.98%)
D: Succ and pred are children, succ has no right child, but pred has a left child: 15562763 (7.28%)
E: Children are both leaves: 51782171 (24.22%)

In case D, picking the successor always leads to a rotation. In case B, picking the successor can (often?) lead to a rotation, but I think there's a case where it won't.

Diff Detail

Lint Skipped
Unit Tests Skipped

Event Timeline

dougm requested review of this revision.Jul 27 2022, 4:48 AM
dougm created this revision.

A tweak to somewhat reduce the tendency of removals to come from the right branch.

Tighten up the successor-search loop. Find one line of common code to factor out.

Running a micro-benchmark

on the new and old versions of RB_REMOVE, repeatedly, gives these user times (on lip3):
new old
2m38.517s 2m35.862s
2m35.680s 2m36.003s
2m38.448s 2m38.810s
2m38.235s 2m39.267s
2m35.282s 2m38.432s
2m37.927s 2m36.389s
2m37.678s 2m36.199s
2m35.505s 2m35.900s