My test code {F48022144} includes copies of the old and new augmentation code from iommu_gas.c.
I ran three sets of tests. All tests start by initializing 64k nodes to be moved into and out of a tree repeatedly.
The plain test does as many insertions as deletions. (-DPLAIN -DTEST_AUGMENTATION -O2)
The ins test does only insertions, and when the tree is full nulls the root pointer and repeats. (-DINS_ONLY -DTEST_AUGMENTATION -O2)
The rem test does only removals, and then the tree is empty, memcpys the tree back into place and repeats. (-DREM_ONLY -DTEST_AUGMENTATION -O2)
I counted the number of calls to the augmentation function for each test, with and without the changes to avoid extra augmentation.
```
plain ins rem
old 4007758921 4242664268 3252700484
new 2567285772 1484862806 2233542332
```
I timed 64 instances of each test. The results show considerable speedup. Here are the results:
```
x lip3.plain.old.res
+ lip3.plain.new.res
+------------------------------------------------------------------------------+
| + x |
| + x |
| ++ x x |
| ++ + x x |
| ++ + x x |
| ++ + + x x |
| ++++ ++ xx x |
| ++++ ++ xxxxx xx|
| ++++ ++ xxxxx xx|
| +++++++ x xxxxx xx|
| +++++++ x xxxxx xx|
| + +++++++ x xxxxxxxx|
|++++++++++ xxxxxxxxxx|
| |_A__| |_MA_| |
+------------------------------------------------------------------------------+
N Min Max Median Avg Stddev
x 64 74.612116 76.477624 75.548696 75.588976 0.49696997
+ 64 61.048206 62.867461 62.065347 62.116771 0.44406353
Difference at 95.0% confidence
-13.4722 +/- 0.163283
-17.823% +/- 0.216015%
(Student's t, pooled s = 0.47126)
x lip3.ins.old.res
+ lip3.ins.new.res
+------------------------------------------------------------------------------+
| + + x x x |
| ++ + x x x |
| ++ + + xxxx x |
| ++++ ++ + xxxx xx |
| ++++ ++ ++ xxxx xxx |
| ++++ ++ + ++ xxxxxxxxx x |
| + +++++++ + ++ xxxxxxxxxxx x |
|+++++ +++++++++++++++ xx xxxxxxxxxxx xxx|
| |___MA____| |__MA__| |
+------------------------------------------------------------------------------+
N Min Max Median Avg Stddev
x 64 45.715224 46.965312 46.252267 46.293999 0.26769006
+ 64 41.345114 42.798423 42.031399 42.0985 0.3560509
Difference at 95.0% confidence
-4.1955 +/- 0.109136
-9.06273% +/- 0.235747%
(Student's t, pooled s = 0.314984)
x lip3.rem.old.res
+ lip3.rem.new.res
+------------------------------------------------------------------------------+
| + |
| + |
| + |
| + |
| + |
| + |
| ++ |
| ++ |
| ++ |
| ++ |
| +++ |
| +++ x |
| +++ x |
| +++ x |
| +++ xxxx |
| +++ xxxx |
| +++ xxxx |
| +++ xxxxx |
| +++ xxxxx |
| +++ xxxxxxx |
|+++++ xxxxxxx |
|+++++ xxxxxxx |
|+++++ xxxxxxxx |
|+++++ xxxxxxxxxx|
| |A| |AM| |
+------------------------------------------------------------------------------+
N Min Max Median Avg Stddev
x 64 50.476852 52.393418 51.510553 51.457622 0.41026087
+ 64 36.433496 37.326866 36.858796 36.847862 0.19545171
Difference at 95.0% confidence
-14.6098 +/- 0.111338
-28.3918% +/- 0.216368%
(Student's t, pooled s = 0.321337)
```