Change from red-black to wavl balancing for RB trees

[dougm]

Summary

Rank balanced (RB) trees are a class of balanced trees that includes AVL trees, red-black trees, and others. Weak AVL (wavl) trees are a recently discovered member of that class. This change replaces red-black rebalancing with weak AVL rebalancing in the RB tree macros.

Wavl trees sit between AVL and red-black trees in terms of how strictly balance is enforced. They have the stricter balance of AVL trees as the tree is built - a wavl tree is an AVL tree until the first deletion. Once removals start, wavl trees are lazier about rebalancing than AVL trees, so that removals can be fast, but the balance of the tree can decay to that of a red-black tree. Subsequent insertions can push balance back toward the stricter AVL conditions.

Removing a node from a wavl tree never requires more than two rotations, which is better than either red-black or AVL trees. Inserting a node into a wavl tree never requires more than two rotations, which matches red-black and AVL trees. The only disadvantage of wavl trees to red-black trees is that more insertions are likely to adjust the tree a bit. That's the cost of keeping the tree more balanced.

Testing has shown that for the cases where red-black trees do worst, wavl trees better balance leads to faster lookups, so that if lookups outnumber insertions by a nontrivial amount, lookup time saved exceeds the extra cost of balancing.

[markj]

Oh, the irony. :)

Please give me a few days to read up on WAVL trees, I haven't encountered them before. (I know I usually take a few days anyway, sorry about that.)

[dougm]

In D25480#562572, @markj wrote:

Oh, the irony. :)

Please give me a few days to read up on WAVL trees, I haven't encountered them before. (I know I usually take a few days anyway, sorry about that.)

Take your time.

In case you ever wonder about the rebalance-after-delete single rotation case, in figure 3, when the rank difference between y and v is 2, and why I did that differently that is depicted, it is because the nodes x and v could both be null, and doing exactly what the picture shows would create a leaf with rank 1, an no-no. So, I'm demoting z to keep that from happening.

[pho]

A r362642 kernel with D25480.73723.diff applied does not compile.

[dougm]

Assuming that the failure to compile is because of the RB_AUGMENT call not within a loop, change to put it within a trivial loop. I've been testing with non-null augmentation so that this problem was not apparent.

[pho]

Diff 73750 seems to only contain the man changes?

[dougm]

Restoring the missing tree.h changes.

[pho]

Yes, this compiles nicely.

20200627 14:23:01 all (21/723): nullfs9.sh

Fatal trap 12: page fault while in kernel mode
cpuid = 19; apic id = 27
fault virtual address   = 0x10
fault code              = supervisor read data, page not present
instruction pointer     = 0x20:0xffffffff8234315d
stack pointer           = 0x28:0xfffffe01389757c8
frame pointer           = 0x28:0xfffffe01389757d0
code segment            = base 0x0, limit 0xfffff, type 0x1b
                        = DPL 0, pres 1, long 1, def32 0, gran 1
processor eflags        = interrupt enabled, resume, IOPL = 0
current process         = 26930 (rm)
trap number             = 12
panic: page fault
cpuid = 19
time = 1593260584
KDB: stack backtrace:
db_trace_self_wrapper() at db_trace_self_wrapper+0x2b/frame 0xfffffe0138975470
vpanic() at vpanic+0x182/frame 0xfffffe01389754c0
panic() at panic+0x43/frame 0xfffffe0138975520
trap_fatal() at trap_fatal+0x387/frame 0xfffffe0138975580
trap_pfault() at trap_pfault+0x99/frame 0xfffffe01389755e0
trap() at trap+0x2a5/frame 0xfffffe01389756f0
calltrap() at calltrap+0x8/frame 0xfffffe01389756f0
--- trap 0xc, rip = 0xffffffff8234315d, rsp = 0xfffffe01389757c8, rbp = 0xfffffe01389757d0 ---
tmpfs_dir_RB_REMOVE() at tmpfs_dir_RB_REMOVE+0xfd/frame 0xfffffe01389757d0
tmpfs_dir_detach() at tmpfs_dir_detach+0x7a/frame 0xfffffe0138975800
tmpfs_remove() at tmpfs_remove+0x107/frame 0xfffffe0138975850
VOP_REMOVE_APV() at VOP_REMOVE_APV+0x79/frame 0xfffffe0138975870
kern_funlinkat() at kern_funlinkat+0x298/frame 0xfffffe0138975ab0
sys_unlink() at sys_unlink+0x28/frame 0xfffffe0138975ad0
amd64_syscall() at amd64_syscall+0x159/frame 0xfffffe0138975bf0
fast_syscall_common() at fast_syscall_common+0x101/frame 0xfffffe0138975bf0
--- syscall (10, FreeBSD ELF64, sys_unlink), rip = 0x8004219fa, rsp = 0x7fffffffe388, rbp = 0x7fffffffe4a0 ---
KDB: enter: panic
[ thread pid 26930 tid 100290 ]
Stopped at      kdb_enter+0x37: movq    $0,0x10c4dc6(%rip)
db>

https://people.freebsd.org/~pho/stress/log/dougm073.txt

[dougm]

Add checking for null parent in RB_REMOVE.

[dougm]

Simplify RB_REMOVE. Let RB_REMOVE_COLOR do more of the color changing.

[dougm]

Move the handling of the deleting-a-leaf special coloring case from RB_REMOVE to RB_REMOVE_COLOR, to avoid entangling rebalancing with augmentation.

[pho]

I have started a full test of D25480.73797.diff.

[dougm]

Optimize the color-changing code in RB_INSERT_COLOR and RB_REMOVE_COLOR by allowing both colors to be set to red, or not-red, at once, in some cases.

[pho]

I ran tests on D25480.73926.diff for 12 hours without seeing any problems.

[dougm]

Tighten up RB_REMOVE_COLOR a bit.

[dougm]

treerace.c948 BDownload

For a test case that inserts and removes items in sorted order, so that the tree stays as unbalanced as possible, this modification improves performance from
real 0m20.837s
user 0m20.728s
to
real 0m16.141s
user 0m16.059s
and no color-balancing at all would be terrible.

For a test case that inserts and deletes in random order, the modified code does more to maintain balance than the current code, with little payoff from faster lookups, so it's a little slower. No color-balancing at all would probably be faster than red-black, for randomly ordered operations.

[markj]

This looks ok to me. My comments are just suggestions and observations. I think this is easier to follow than the old algorithms.

In D25480#562589, @dougm wrote:

In case you ever wonder about the rebalance-after-delete single rotation case, in figure 3, when the rank difference between y and v is 2, and why I did that differently that is depicted, it is because the nodes x and v could both be null, and doing exactly what the picture shows would create a leaf with rank 1, an no-no. So, I'm demoting z to keep that from happening.

There is a sentence in the description of the single-rotation case, "If z is a leaf, demote it again", that sounds like it is referring to this case. I don't quite see how z could be a leaf though, it looks like it should say "unary node".

share/man/man3/tree.3

390 ↗

(On Diff #74182)

I would include a sentence clarifying that wavl trees can be used for the same purposes as red-black trees.

703 ↗

(On Diff #74182)

You might consider adding a link to the original paper here. See share/man/man4/cc_cubic.4 for a formatting example.

sys/sys/tree.h

67 ↗

(On Diff #74182)

It is a bit confusing that during rebalancing, a 0-child's rank difference is even, but the child is not red. I can't see a way around that without complicating the encoding, though.

340 ↗

(On Diff #74182)

I think these should be enclosed by parentheses since they are used in compound expressions, like ~RB_BITS(...). RB_BITS() is also used as an lvalue, but I believe that they can be parenthesized.

[markj]

In D25480#562589, @dougm wrote:

In case you ever wonder about the rebalance-after-delete single rotation case, in figure 3, when the rank difference between y and v is 2, and why I did that differently that is depicted, it is because the nodes x and v could both be null, and doing exactly what the picture shows would create a leaf with rank 1, an no-no. So, I'm demoting z to keep that from happening.

There is a sentence in the description of the single-rotation case, "If z is a leaf, demote it again", that sounds like it is referring to this case. I don't quite see how z could be a leaf though, it looks like it should say "unary node".

Sorry, never mind, you even pointed it out - x and v can both be null.

[dougm]

Apply reviewer suggestions.

[dougm]

Adding a test result to reflect the downside of this change. If you replace the sorted inserts and removals with randomly generated ones (random() % maxsize), then the red-black tree takes this time:
real 0m19.819s
user 0m19.801s

and the wavl tree takes this time:
real 0m20.461s
user 0m20.445s

[markj]

In D25480#566453, @dougm wrote:

Adding a test result to reflect the downside of this change. If you replace the sorted inserts and removals with randomly generated ones (random() % maxsize), then the red-black tree takes this time:
real 0m19.819s
user 0m19.801s

and the wavl tree takes this time:
real 0m20.461s
user 0m20.445s

I take it that this test does not do any lookups? I am personally not overly concerned by a pessimization in a write-heavy benchmark, since a binary search tree is probably not the best choice for that scenario to begin with.

[dougm]

I take it that this test does not do any lookups? I am personally not overly concerned by a pessimization in a write-heavy benchmark, since a binary search tree is probably not the best choice for that scenario to begin with.

An insert has a lookup built-in, even in cases when the thing to be inserted is in the tree already so that the insert is a no-op. A remove must be preceded by a lookup, since I'm generating random numbers to remove, and some of them may not be in the tree to be removed.

To eliminate these issues, I'll eliminate randomness and just insert and remove a list of unsorted values, by changing a couple of lines to

		ins->val = count * 61803398;

and

			key.val = (count - maxsize) * 61803398;

so that I can expect the insert attempts to always insert something, and the remove lookups to always produce something to remove.
With that, red-black gives this:
real 0m19.809s
user 0m19.804s
and wavl gives this:
real 0m20.173s
user 0m20.166s

[alc]

I have two comments.

1. I would develop a test that shows the benefits for a lookup-heavy test. In other words, a test where lookups are more common than insertions and removals.
2. I would socialize this change a bit. For example, send an email to the arch and/or current mailing lists pointing to this review and arguing for/motivating the change

[dougm]

treerace.c1 KBDownload

Insert in sorted order, remove in sorted order once tree reaches 100000 items, after every remove, do lookups for the next 100 items that will be removed.

R-B tree:
real 0m28.814s
user 0m28.795s

wavl tree:
real 0m22.784s
user 0m22.767s

If the number of lookups is reduced from 100 to 10:
R-B tree:
real 0m4.068s
user 0m4.058s

wavl tree:
real 0m2.952s
user 0m2.951s

[dougm]

Offline, a reviewer has suggested that I improve the advocacy for wavl trees in the tree manpage, so I've attempted to do that.

[dougm]

Enforce the requirement that sentences in man pages must begin in column 1.

[alc]

share/man/man3/tree.3

368–371 ↗

(On Diff #74345)

Can you define "rank" for trees in a sentence? I don't think that it's a familiar concept for most people who would read this.

372 ↗

(On Diff #74345)

The motivation for this sentence is unclear.

374–375 ↗

(On Diff #74345)

I think that this sentence belongs in the previous paragraph, probably as the second sentence.

389–391 ↗

(On Diff #74345)

"For example, ...

396–400 ↗

(On Diff #74345)

For most people who read this, you will need to explain what this means. Is this a good thing?

[dougm]

Address more feedback on the manpage.

I can't define 'rank' in a sentence. The original paper says that rank exists, but does not define it, and then defines rank-differences from ranks, and sets conditions on rank-differences. I can, instead, state that 'weights' exist for tree edges and then define rank from weights. It's how I would explain it to a class of sophomores, but it means I'm wandering away from the terminology used in the paper. Also, I'm adding 1 to the definition of rank used in the paper.

[dougm]

Make clear that red-black and avl trees also have rank-1 leaves.

[alc]

I think that you are trying to emulate the style of the original text describing red-black trees, and I think that you should break away from that style. Specifically, don't start with low-level definitional details. With red-black trees those details are so short that typical readers will stick around to the end of the text that says what they want to know in deciding to use red-black trees versus something else. For better or worse, those details are not so short for WAVL. So, you need to restructure the text to summarize the case for WAVL trees in the first paragraph, specifically, that they equal or dominate red-black trees in every dimension. In particular, you never explicitly say that WAVL insertion has the same complexity as red-black insertion both in the overall sense and in terms of rotations yet achieves better balance.

In summary, you should write this text assuming that most people will never read more than one paragraph, and that one paragraph should make it clear that WAVL trees equal or dominate red-black trees in every respect.

[dougm]

Endeavor to apply reviewer suggestions, with a briefer, punchier, less detailed paragraph on wavl trees.

[alc]

Here is what I would suggest for quickly getting "rank-balanced" out of the way and moving on to the more important part, the properties of "WAVL" trees:

"Rank-balanced (RB) trees represent a modern, unified approach to defining and implementing different kinds of height-balanced binary search trees, including AVL and red-black trees. Instead of a balance factor that is specific to the implementation of AVL trees or a color that is specific to the implementation of red-black trees, each node of the tree is augmented with a rank difference. Different kinds of height-balanced binary search trees are realized by enforcing a different set of restrictions on the rank differences throughout the tree.

The set of restrictions implemented by the RB macros yields a weak AVL (WAVL) tree, which combines the best aspects of AVL and red-black trees. ...

[dougm]

Replace some manpage text with what alc has offered.

[dougm]

Try to tighten up the introduction to rb trees in the manpage.

[alc]

"They have all the advantages of AVL trees ..." -> "They have the stricter balance of AVL trees ..."

[alc]

"... but the balance of the tree can start to get red-blackier." -> "but the balance of the tree can decay to that of a red-black tree."

Won't subsequent insertions nudge the balance back toward AVL's stricter balance?

[alc]

The current third paragraph of the summary should be the second paragraph. The current second and fourth paragraphs should be merged. Then, it's no longer necessary for the current fourth paragraph to say, "while no insertion adjusts the tree too much".

[dougm]

Copy a bit from the summary into the man page.

[dougm]

The code here has been tested and reviewed. I need to know that the man page is clear enough, and that the change itself isn't going to annoy a lot of people. A message to current a couple of weeks ago drew no response. Does anyone want to comment, favorably or unfavorably, or suggest who else ought to be consulted before this is checked in?

[gbe]

In D25480#570691, @dougm wrote:

The code here has been tested and reviewed. I need to know that the man page is clear enough, and that the change itself isn't going to annoy a lot of people. A message to current a couple of weeks ago drew no response. Does anyone want to comment, favorably or unfavorably, or suggest who else ought to be consulted before this is checked in?

From the manpages perspective everything is fine. I proofread the changes and with a little mathematical background I understand what has changed.

[emaste]

and that the change itself isn't going to annoy a lot of people

I can't imagine that would be the case - I expect responses to vary from indifference to mild encouragement. My input, "go for it."

If you have some macro-level performance or other metrics you can share that'd be worth doing also.

[markj]

In D25480#570691, @dougm wrote:

The code here has been tested and reviewed. I need to know that the man page is clear enough, and that the change itself isn't going to annoy a lot of people. A message to current a couple of weeks ago drew no response. Does anyone want to comment, favorably or unfavorably, or suggest who else ought to be consulted before this is checked in?

I think the change itself should not be controversial. In past commits you have changed the RB_* internal interfaces quite a bit without any major fallout except for the LinuxKPI problem. In this diff you made very few changes to the RB_* internals - it's just the insertion and deletion code that has changed, really.

[alc]

I'm convinced that replacing red-black trees with wavl trees is reasonable. There is barely even a trade-off between them. Wavl trees are either equal to or better than red-black trees in almost all respects. In the type of use case that actually favors red-black trees, i.e., no lookups, just random inserts and removes, the performance advantage for red-black trees that Doug reported was slight, about 2-3%. On the other hand, in a lookup-heavy workload the performance advantages of wavl trees were much more significant.

share/man/man3/tree.3

384 ↗

(On Diff #74811)

"become" -> "becoming"

704 ↗

(On Diff #74811)

Add:

.%J "ACM Transactions on Algorithms"
.%V "11"
.%N "4"
.%D "June 2015"