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

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.

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

Diff 73750 seems to only contain the man changes?

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

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

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

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.

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.

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

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.

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

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

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

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.

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

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

"... 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?

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

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?

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.

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.

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.