rb_tree: optimize removal

[dougm]

Summary

Improve RB_REMOVE by reading the fields of the removed node only once, and by not writing to the removed node.

Test Plan

This change reduces the size of iommu_gas.o by 64 bytes.

This test program, {F47075485}compiled with '-O2 -DREM_ONLY', reports the time spent repeatedly copying a 64k element rb-tree into place, and then removing all its elements, in a slightly different order each time.

Here are the results of 24 trials on each of 5 machines:

x rem.lip1.res
+ rem.lip1.new.res
+-------------------------------------------------------------------------------------+
|   +                                                                                 |
|   +                                                                       x         |
|  ++                                                                       xx        |
|  ++                                                                      xxx        |
|  ++ + +                                                                  xxxx       |
|  ++ +++                                                                  xxxx       |
|+++++++++                                                               xxxxxxx xx  x|
|  |MA_|                                                                   |_A__|     |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     31.977007     32.320331     32.068799     32.087863    0.07641883
+  24     29.832147     30.066229     29.926628     29.947308   0.064589125
Difference at 95.0% confidence
        -2.14056 +/- 0.041114
        -6.67092% +/- 0.128129%
        (Student's t, pooled s = 0.0707517)
x rem.lip2.res
+ rem.lip2.new.res
+-------------------------------------------------------------------------------------+
|            +      x                                                                 |
|          + +      x                                                                 |
|          + + +   xx  x  xx                                                          |
|       +  + + +   *x xxx xxx                                                         |
|       +++++++++++*x xxx xxx      x                                                 +|
||___________M__A___|__MA___|__|                                                      |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     42.382184     42.695532     42.469389     42.479865   0.074970753
+  24     42.162888     43.675154     42.269793     42.329174    0.29333144
Difference at 95.0% confidence
        -0.150692 +/- 0.124405
        -0.354737% +/- 0.292856%
        (Student's t, pooled s = 0.214084)
x rem.lip3.res
+ rem.lip3.new.res
+-------------------------------------------------------------------------------------+
|  +                                                          x                       |
|  +    ++  +       +                     +   x       xx      x                       |
|+ +  + ++ ++    +  + +++        +  x    ++ + * xx  xxxx x  x x xx x xxxx            x|
|   |_________M____A______________|             |_________MA__________|               |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     18.772724     19.255248     18.991113     18.997486    0.10494604
+  24     18.423612     18.864433     18.554971     18.602799    0.14572267
Difference at 95.0% confidence
        -0.394687 +/- 0.0737895
        -2.07758% +/- 0.388417%
        (Student's t, pooled s = 0.126982)
x rem.lip4.res
+ rem.lip4.new.res
+-------------------------------------------------------------------------------------+
|              +                 x  x                                                 |
|              +      +  +  x    x +x                                                 |
|+   +++  ++++ + +    + ++* x  +xx +x+xx*  +x xxxx  x xxx x                          x|
|        |_________M_A________|_|______M___A____________|                             |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     35.227885     35.380417     35.263539      35.27269    0.03357718
+  24      35.16504     35.272503     35.211737     35.215206   0.030286451
Difference at 95.0% confidence
        -0.0574834 +/- 0.0185803
        -0.162969% +/- 0.0526761%
        (Student's t, pooled s = 0.0319742)
x rem.lip5.res
+ rem.lip5.new.res
+-------------------------------------------------------------------------------------+
| +                                                                                   |
| +                                                                                 x |
| +                                                                                 x |
|++                                                                                 x |
|++                                                                                 x |
|++                                                                                 x |
|++                                                                                xx |
|++                                                                                xx |
|++                                                                                xxx|
|++                                                                                xxx|
|++                                                                                xxx|
|++                                                                                xxx|
|+++                                                                               xxx|
||A                                                                                |A |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     39.168888     39.244556      39.19884     39.202953   0.017768172
+  24      36.36112     36.416104     36.380468      36.38063   0.013820138
Difference at 95.0% confidence
        -2.82232 +/- 0.00924944
        -7.19926% +/- 0.0235937%
        (Student's t, pooled s = 0.015917)

[markj]

sys/sys/tree.h

346–348

Since RB_PARENT_ONLY seemingly isn't meant to be used by consumers, I'd suggest naming it _RB_PARENT_ONLY to better indicate that it's private to the rbtree implementation.

[dougm]

Accept reviewer suggestion.
Note that this is not the only macro not intended for public use.
Also, I could probably just #undef some of them after use.

[kib]

In D36288#825039, @dougm wrote:

Accept reviewer suggestion.
Note that this is not the only macro not intended for public use.
Also, I could probably just #undef some of them after use.

Note that you cannot #undef a macro used inside expanding macro, since it is needed at the expansion time, not at the define time.
The namespace of symbols ^_[A-Z] is reserved for file-local. so indeed changing internal macros to follow this scheme as a follow-up commit would be reasonable.

[kib]

sys/sys/tree.h

694

Extra ()