Page MenuHomeFreeBSD

rb_tree: avoid extra reads in rebalancing
ClosedPublic

Authored by dougm on Aug 25 2022, 11:01 PM.
Tags
None
Referenced Files
Unknown Object (File)
Dec 20 2023, 8:08 AM
Unknown Object (File)
Dec 8 2023, 10:55 AM
Unknown Object (File)
Dec 8 2023, 2:30 AM
Unknown Object (File)
Dec 7 2023, 9:05 PM
Unknown Object (File)
Nov 20 2023, 10:32 PM
Unknown Object (File)
Nov 3 2023, 3:54 AM
Unknown Object (File)
Oct 26 2023, 10:37 PM
Unknown Object (File)
Oct 26 2023, 10:37 PM
Subscribers

Details

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 (

) 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 created this revision.
dougm edited the test plan for this revision. (Show Details)

Update after merging in another patch.

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 !

dougm marked 6 inline comments as done.

Apply reviewer recommendations on formatting.

sys/kern/subr_stats.c
3412

parent == NULL

This revision is now accepted and ready to land.Aug 29 2022, 4:02 PM
This revision was automatically updated to reflect the committed changes.