rb_tree: avoid double-writing in double rotation

[dougm]

Summary

RB_ROTATE_LEFT (and it symmetric twin) modify the rb-tree, adjusting pointers so that what started as a proper tree ends up a proper tree. When two consecutive rotations move the same node up the tree, some of the pointers changed in the first rotation are immediately changed again in the second - namely, the pointer from the rising node to its new parent, and the pointer from that parent back to the rising node. This change removes from RB_ROTATE macros the responsibility for managing those two pointers, and leaves it to the code that calls for rotations to fix up those pointers afterward. That drops a comparison and a pair of assignments from every INSERT_COLOR or REMOVE_COLOR call that ends in a double rotation.

A side-effect of this change is that the SWAP_CHILD macro must take as a parameter a pointer to the node that is changing children, where it is now computed from the old child. Since this macro is called in a couple of places besides the RB_ROTATE macros, those calls are also affected.

Test Plan

A test program that does nothing but invoke RB_INSERT and RB_REMOVE repeatedly on a fixed node set shows performance improvement with this change often, on some available test machines, but not always. Average running times were reduced by 4.55%, by 10.38%, by 3.61%, by 10.11%. They were also increased by 5.68%, 0.86% and 0.02 %

The size of a particular NODEBUG binary, iommu_gas.o, shrank from 9112 to 8760 bytes.

A dump of ministats results for the tests follow. There are 5 test machines, lip1 to lip5. Note that lip6 is the same as lip5, but logged in as root. lip7 is the same as lip3, but logged in as root.

x plain.lip1.res
+ plain.lip1.new.res
+--------------------------------------------------------------------------+
|       +  +                                                    x   xxx    |
|       +  +    +                                               xx  xxx    |
|  + +  +  +  +++       +                                       xx xxxxx x |
|+ +++ +++ +++++++ ++++ +                             x  x x x xxx xxxxxxxx|
|     |_____A______|                                          |____AM__|   |
+--------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  32     73.126851     74.357373     73.966546     73.918887    0.28178833
+  32     69.864714     71.276387     70.538137     70.557231    0.39186779
Difference at 95.0% confidence
	-3.36166 +/- 0.170562
	-4.54776% +/- 0.230743%
	(Student's t, pooled s = 0.341295)
x plain.lip2.res
+ plain.lip2.new.res
+--------------------------------------------------------------------------+
|   +                             x                                        |
|   +                             x                                        |
|   +                             x                                        |
|   +                             x                                        |
|   +                             x                                        |
|   +                             x                                        |
|   +                             x                                        |
|   +                             x                                        |
|   +                             x                                        |
|   +                             x                                        |
|   ++                            x xx                                     |
|   ++  ++                        xxxx                                     |
|   ++ +++                        xxxx   x                                 |
|   ++++++   ++       +      +  + xxxxx  x  x   x           x             x|
||___M__A______|              |____M__A________|                           |
+--------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  32     77.265475     88.177796      77.55878     78.448446     2.2977762
+  32     69.116265     76.831343     69.468469     70.307918     1.9148623
Difference at 95.0% confidence
	-8.14053 +/- 1.05697
	-10.3769% +/- 1.34735%
	(Student's t, pooled s = 2.115)
x plain.lip3.res
+ plain.lip3.new.res
+--------------------------------------------------------------------------+
|                 +                                 xx                     |
|          + ++   +                                 xxx                    |
|          + ++   +        + + +                    xxx x x  x           x |
|+   +    ++++++++++ + +++ +++ +      x           x xxxxx xx xx  x x x xxxx|
|         |______MA_______|                       |____M__A________|       |
+--------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  32     40.511732     41.846975      41.14674     41.262585    0.31417693
+  32     39.142457     40.253734     39.739057     39.772375    0.28433464
Difference at 95.0% confidence
	-1.49021 +/- 0.149739
	-3.61153% +/- 0.362893%
	(Student's t, pooled s = 0.299628)
x plain.lip4.res
+ plain.lip4.new.res
+--------------------------------------------------------------------------+
|++                                                                      x |
|++                                                                      x |
|++                                                                      x |
|++                                                                      x |
|++                                                                      x |
|++                                                                      x |
|++                                                                      x |
|++                                                                      x |
|++                                                                      x |
|++                                                                      x |
|++                                                                      xx|
|++                                                                      xx|
|++                                                                      xx|
|++                                                                      xx|
|++                                                                      xx|
|++                                                                      xx|
|AM                                                                      A||
+--------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  32     63.880321     63.987626     63.921197     63.922629   0.023384875
+  32     57.416264     57.497433     57.462177       57.4596   0.018895407
Difference at 95.0% confidence
	-6.46303 +/- 0.0106242
	-10.1107% +/- 0.0166204%
	(Student's t, pooled s = 0.021259)
x plain.lip5.res
+ plain.lip5.new.res
+--------------------------------------------------------------------------+
|                       x            +                                     |
|                       x      x   + + x       +                           |
|x                  x*+ xxx *xx*  x+ +**x+**  ++ xxx +++  +  +x +         +|
|                   |_________|M_A________MA__|__________|                 |
+--------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24      84.07309     84.191225     84.130794     84.135619   0.024919027
+  24     84.111672     84.214656     84.152107     84.155414   0.025447998
Difference at 95.0% confidence
	0.0197942 +/- 0.014635
	0.0235265% +/- 0.0173946%
	(Student's t, pooled s = 0.0251849)
x plain.lip6.res
+ plain.lip6.new.res
+--------------------------------------------------------------------------+
|                                                                        + |
|                                                                        + |
|                                                                        + |
|                                                                        + |
|                                                                        + |
|                                                                        + |
|x                                                                       + |
|x                                                                       + |
|x                                                                       + |
|x                                                                       + |
|xx                                                                      + |
|xx                                                                      + |
|xx                                                                      + |
|xx                                                                      + |
|xx                                                                      + |
|xx                                                                      + |
|xx                                                                      + |
|xx                                                                     ++ |
|xx                                                                     ++ |
|xx                                                                     +++|
|A|                                                                      A |
+--------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     84.112555     84.192469     84.137266     84.144705   0.020043424
+  24     88.886254     88.994568     88.932721     88.929204    0.02290112
Difference at 95.0% confidence
	4.7845 +/- 0.0125052
	5.68604% +/- 0.0148615%
	(Student's t, pooled s = 0.0215198)
x plain.lip7.res
+ plain.lip7.new.res
+--------------------------------------------------------------------------+
|           +                                                              |
|           +                                                              |
|           +                                                              |
|           +                                                              |
|         x +                                                              |
|         x +                                                              |
|         x +                                                              |
|      x  x +    x                                                         |
|      x  x +    x                                                         |
|     xx xx++ +  x                                                         |
|x    xx *x++ + xx    +                                                    |
|xx   **x**+++*+xxx+++++                                                  +|
|   ||____A_M__A___________|                                               |
+--------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  32     38.877582     39.973933     39.442159     39.462951     0.3089786
+  32     39.173058     43.610485     39.590039     39.802498      0.748281
Difference at 95.0% confidence
	0.339547 +/- 0.286081
	0.860419% +/- 0.724935%
	(Student's t, pooled s = 0.572447)

[alc]

Otherwise, I'm fine with this change.

sys/sys/tree.h

390–403

I would add a block comment here explaining what this function does vs. doesn't do, i.e., what it used to do, but no longer does, and explains why not.

687

These used to be in alphabetical order.