Details

Reviewers

Commits

rG35b262e57114: rb_tree: avoid extra reads in rebalancing
rG5d91386826d0: rb_tree: avoid extra reads in rebalancing

Summary

In RB_INSERT_COLOR and RB_REMOVE_COLOR, avoid reading a parent pointer from memory, and then reading the left-color bit from memory, and then reading the right-color bit from memory, since they're all in the same field. The compiler can't infer that only the first read is really necessary, so write the code in a way so that it doesn't have to.

Drop RB_RED_LEFT and RB_RED_RIGHT macros that reach into memory to get those bits.
Drop RB_COLOR, the only thing left using RB_RED_LEFT and RB_RED_RIGHT after the other changes, and go straight to DIAGNOSTIC code in subr_stats to implement RB_COLOR for its single, dubious use there.

Test Plan

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

On a test code (

rb_toy.c7 KBDownload

) compiled with -O2 -DPLAIN that repeatedly inserts and removes nodes from a tree keeping it as close as possible to 32k in size, this change improves performance on 4 of 5 machines tested:

x plain.lip1.res
+ plain.lip1.new.res
+-------------------------------------------------------------------------------------+
|   +                                                                                 |
|   +                                                                                 |
|   ++                                                                   xxx          |
|   ++   +                                                              xxxx          |
|+++++   +                                                              xxxxxx        |
|+++++++++++                                                          xxxxxxxxx   x  x|
| |__A__|                                                              |__MA__|       |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     69.555135     70.258062      69.75464     69.777408     0.1579122
+  24     66.286562     66.743278     66.457209     66.488963    0.13198151
Difference at 95.0% confidence
        -3.28844 +/- 0.0845654
        -4.71276% +/- 0.121193%
        (Student's t, pooled s = 0.145526)
x plain.lip2.res
+ plain.lip2.new.res
+-------------------------------------------------------------------------------------+
| ++                                                                                  |
| ++                                                                                  |
| ++                                                                               x  |
| ++                                                                             xxx  |
| ++                                                                             xxx  |
| ++                                                                            xxxx  |
| ++                                                                            xxxx  |
| ++++                                                                          xxxx  |
|++++++                                                                         xxxx x|
| |A|                                                                            |A|  |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     73.971392     74.419757     74.126437     74.123822    0.11015063
+  24     66.351963      66.79616     66.526073     66.527292     0.1106494
Difference at 95.0% confidence
        -7.59653 +/- 0.0641539
        -10.2484% +/- 0.0865497%
        (Student's t, pooled s = 0.1104)
x plain.lip3.res
+ plain.lip3.new.res
+-------------------------------------------------------------------------------------+
|        +                                                                            |
|        ++                                                                           |
|        ++            +                                                       x      |
|      + +++           +                              x         x            x xx     |
|+     + +++++++ ++    + +                            x  x  x x xxxxxxxx   x x xx x  x|
|      |___M_A_____|                                         |_______MA________|      |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     40.559234     42.046492     41.295055      41.33403    0.43762768
+  24     38.005898     39.138651     38.471001     38.569402    0.28571529
Difference at 95.0% confidence
        -2.76463 +/- 0.214753
        -6.6885% +/- 0.519556%
        (Student's t, pooled s = 0.369561)
x plain.lip4.res
+ plain.lip4.new.res
+-------------------------------------------------------------------------------------+
| +                                                                                x  |
| +                                                                                x  |
| +                                                                                x  |
| +                                                                                x  |
| +                                                                                x  |
|++                                                                                x  |
|++                                                                                x  |
|++                                                                                xx |
|+++                                                                               xx |
|+++                                                                              xxx |
|+++                                                                              xxx |
|++++                                                                             xxxx|
||A|                                                                               A| |
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  24     61.300374      61.50657       61.3641     61.373103   0.052427644
+  24     55.100894     55.316134     55.161839     55.174412   0.056165408
Difference at 95.0% confidence
        -6.19869 +/- 0.0315706
        -10.1% +/- 0.0514404%
        (Student's t, pooled s = 0.0543287)
x plain.lip5.res
+ plain.lip5.new.res
+-------------------------------------------------------------------------------------+
| x                                                                                 + |
| x                                                                                 + |
| x                                                                                 + |
| x                                                                                 + |
| x                                                                                 + |
| x                                                                                 + |
| x                                                                                 + |
| x                                                                                 + |
| x                                                                                 + |
| x                                                                                 ++|
|xx                                                                                 ++|
|xx                                                                                +++|
|xxx                                                                               +++|
|xxx                                                                               +++|
||A                                                                                |A||
+-------------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  22     83.027081     83.128148     83.082776     83.079594   0.024554289
+  22     87.782023     87.901107     87.834571     87.841198   0.033430836
Difference at 95.0% confidence
        4.7616 +/- 0.017846
        5.73138% +/- 0.0214806%
        (Student's t, pooled s = 0.0293303)

Diff Detail

Repository

rG FreeBSD src repository

Lint

Lint Not Applicable

Unit

Tests Not Applicable

Event Timeline

dougm requested review of this revision.Aug 25 2022, 11:01 PM

dougm created this revision.

Update after merging in another patch.

alc added inline comments.Aug 28 2022, 6:44 PM

sys/sys/tree.h
486	blank line after
497	normally, we write == 0, not !
525	normally, we write == 0, not !
575	blank line after
593	normally, we write == 0, not !
639	normally, we write == 0, not !