Page MenuHomeFreeBSD

rb_tree:stop symmetric code dup in insert/remove_color
ClosedPublic

Authored by dougm on Aug 30 2022, 7:28 AM.
Tags
None
Referenced Files
Unknown Object (File)
Wed, Oct 2, 2:30 PM
Unknown Object (File)
Wed, Oct 2, 2:22 PM
Unknown Object (File)
Wed, Oct 2, 12:24 PM
Unknown Object (File)
Sat, Sep 28, 3:05 AM
Unknown Object (File)
Fri, Sep 27, 4:13 PM
Unknown Object (File)
Fri, Sep 27, 1:14 PM
Unknown Object (File)
Thu, Sep 26, 1:46 PM
Unknown Object (File)
Sep 10 2024, 11:29 PM

Details

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 requested review of this revision.Aug 30 2022, 7:28 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)
This revision is now accepted and ready to land.Aug 30 2022, 1:11 PM
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.

This revision is now accepted and ready to land.Sep 7 2022, 8:53 AM
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.

This revision was automatically updated to reflect the committed changes.