Page MenuHomeFreeBSD

rb_tree: pass parent to RB_INSERT_COLOR
ClosedPublic

Authored by dougm on Aug 10 2022, 9:09 AM.
Tags
None
Referenced Files
Unknown Object (File)
Jan 25 2024, 8:13 AM
Unknown Object (File)
Jan 25 2024, 8:13 AM
Unknown Object (File)
Jan 25 2024, 8:04 AM
Unknown Object (File)
Dec 20 2023, 2:42 AM
Unknown Object (File)
Nov 29 2023, 6:18 AM
Unknown Object (File)
Nov 27 2023, 8:06 AM
Unknown Object (File)
Nov 26 2023, 10:54 PM
Unknown Object (File)
Nov 25 2023, 8:10 PM

Details

Summary

Change RB_COLOR_INSERT to take a parent parameter, to avoid looking up a value already available. Make adjustments to a linux rbtree header, which invokes it.

Test Plan

This change makes iommu_gas.o 32 bytes larger.

I tested this with a binary that repeatedly inserts 64k items into a tree, nulls the root and repeats. The allocation and initialization and randomization happens untimed, and only the inserts are timed. On lip3 there appears to be a small benefit:

x old.res
+ new.res
+------------------------------------------------------------------------------+
|                       +                                                      |
|                       +      +*           x                                  |
|                 +    ++     *+*     x     x      xxx       x                x|
|+    ++  +   ++  ++ + +++   ****+ xx x     x+ +xx***x  x   xx  x     x    x  x|
|             |__________M_A______|_____|________A_____________|               |
+------------------------------------------------------------------------------+
    N           Min           Max        Median           Avg        Stddev
x  32     29.542046     30.475461      29.93764     29.922804    0.27414741
+  32     29.022955     29.984536     29.471963     29.508554    0.24104074
Difference at 95.0% confidence
        -0.41425 +/- 0.128998
        -1.38439% +/- 0.431103%
        (Student's t, pooled s = 0.258125)

Diff Detail

Lint
Lint Skipped
Unit
Tests Skipped

Event Timeline

dougm requested review of this revision.Aug 10 2022, 9:09 AM
dougm created this revision.
dougm retitled this revision from rb_tree: fine-tune RB_REMOVE to rb_tree: fine-tune tree manipulation.Aug 13 2022, 12:10 AM
dougm edited the summary of this revision. (Show Details)
dougm edited the test plan for this revision. (Show Details)

Apply changes to rebalancing functions, fix linux problems.

hselasky added inline comments.
sys/sys/tree.h
365

Are you sure RB_RED_LEFT is expanded properly in RB_COLOR using different C-code pre-processors?

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

Stop defining RB_RED. Modify the DIAGNOSTIC code in subr_stats.c to compute 'red' on its own.

Reduce code duplication by combining the left-leaning an right-leaning RB_COLOR codes into one.

dougm marked an inline comment as done.
dougm added inline comments.
sys/sys/tree.h
365

I have solved the problem, if any, by rewriting code elsewhere.

dougm marked an inline comment as done.
dougm retitled this revision from rb_tree: fine-tune tree manipulation to rb_tree: pass parent to RB_INSERT_COLOR.
dougm edited the summary of this revision. (Show Details)
dougm edited the test plan for this revision. (Show Details)

Since the last revision, almost everything this change would have done has been checked in separately. Only this little piece remains. I haven't determined that it merits further consideration.

Refactoring looks OK to me, to check parent != NULL once instead of twice.

This revision is now accepted and ready to land.Sep 8 2022, 7:57 AM
This revision was automatically updated to reflect the committed changes.