rb_tree:stop symmetric code dup in insert/remove_color
ClosedPublic
Actions

Authored by dougm on Aug 30 2022, 7:28 AM.

Details

Reviewers

alc
kib

Commits

rG72c99edafa49: rb_tree: reduce duplication in balancing code
rGd0354fa7b6b1: rb_tree: reduce duplication in balancing code

Summary

Change RB_INSERT_COLOR and RB_REMOVE_COLOR so that the blocks of code that are identical except for left and right being exchanged are made only one block with a variable to indicate left- or right-handedness.

Rename RB macros so that those not intended for external use begin with an underscore.

Test Plan

This reduces the size of the iommu_gas.o binary by 432 bytes.

With a test that inserts and removes nodes from a 32k element tree, and with both executables having names of the same length (which, strangely, seems to matter a lot), the runtime performance is improved slightly.

x plain.lip1.now.res
+ plain.lip1.new.res
+-------------------------------------------------------------------------------------+
|          +        + ++                x         x        x      x                   |
|+++   +++++ + ++   ++++      + +   *+ xxx xxx x xxx xx    x xx   x        +         x|
|   |_____________MA_______________|   |_________M_A___________|                      |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     70.108675     71.238568     70.412545     70.444967    0.27058878
+  24     69.284527     71.017242     69.678344     69.714419    0.36450828
Difference at 95.0% confidence
        -0.730548 +/- 0.186535
        -1.03705% +/- 0.264796%
        (Student's t, pooled s = 0.321002)
x plain.lip2.now.res
+ plain.lip2.new.res
+-------------------------------------------------------------------------------------+
|  +                                         x x                                      |
|  +   + +          +     +              x xxx x x       x  x                         |
|+ + + +++++ +++++  + +   +  +     +     xxxxx x x xx    xx x x                      x|
|    |______M_A________|                 |_____M___A________|                         |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24      66.40755     66.842408      66.46865      66.50195   0.097074962
+  24     66.012772     66.345493     66.123726     66.138662    0.08984195
Difference at 95.0% confidence
        -0.363287 +/- 0.0543496
        -0.546281% +/- 0.0817264%
        (Student's t, pooled s = 0.0935284)
x plain.lip3.now.res
+ plain.lip3.new.res
+-------------------------------------------------------------------------------------+
|             *x   xx  + x+                                                           |
|x     +    x *x   *xx +xx***x x x +  +x+  x  +    +    +    x  ++x+ +    +    ++    +|
|          |________|___M_A____________M_|__A_______________________|                 |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     38.148341     39.117977     38.492871     38.521598    0.21811253
+  24     38.234826     39.402013     38.716094     38.790028    0.35940926
Difference at 95.0% confidence
        0.26843 +/- 0.172749
        0.696831% +/- 0.448447%
        (Student's t, pooled s = 0.297278)
x plain.lip5.now.res
+ plain.lip5.new.res
+-------------------------------------------------------------------------------------+
|  +                                                                                  |
|  +                                                                                x |
|  +                                                                                x |
|  +                                                                                x |
|  +                                                                               xx |
| ++                                                                               xx |
| ++                                                                               xx |
| ++                                                                               xx |
| ++                                                                               xx |
| ++                                                                               xx |
|+++                                                                               xxx|
|+++                                                                               xxx|
|+++                                                                               xxx|
| AM                                                                               |A |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     87.907334     88.002397     87.949785     87.951022   0.023984089
+  24     84.763389     84.854964     84.824345     84.818386    0.02432752
Difference at 95.0% confidence
        -3.13264 +/- 0.0140374
        -3.5618% +/- 0.0159604%
        (Student's t, pooled s = 0.0241564)

Diff Detail

Lint

Lint Skipped

Unit

Tests Skipped

Event Timeline

dougm created this revision.Aug 30 2022, 7:28 AM

Herald added subscribers: linuxkpi, emaste. · View Herald TranscriptAug 30 2022, 7:28 AM

dougm requested review of this revision.Aug 30 2022, 7:28 AM

• hselasky added a subscriber: • hselasky.Aug 30 2022, 7:42 AM

• hselasky added inline comments.

sys/sys/tree.h
323–324	Maybe this piece of repeated code should have its own macro for readability: #define RB_SWAP_LR(dir) ((dir) ^ RB_RED_LR)

kib accepted this revision.Aug 30 2022, 1:11 PM

This revision is now accepted and ready to land.Aug 30 2022, 1:11 PM

dougm updated this revision to Diff 110133.Sep 5 2022, 5:39 AM

dougm edited the summary of this revision. (Show Details)

dougm edited the test plan for this revision. (Show Details)

This revision now requires review to proceed.Sep 5 2022, 5:39 AM

Update the DIAGNOSTIC stats code to account for macro renaming.

kib accepted this revision.Sep 7 2022, 8:53 AM

This revision is now accepted and ready to land.Sep 7 2022, 8:53 AM

alc accepted this revision.Sep 7 2022, 4:54 PM

alc added inline comments.

sys/sys/tree.h
491	Since this has proven to be useless, as in it doesn't quiet Coverity, I would argue for deleting it. The above block comment addresses this issue in great detail.