My test code {F48005714} 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 2133236893 1168871752 1793069670
```
I timed 64 instances of each test. The results show considerable speedup. Here are the results:
```
x lip3.plain.new.res
+ lip3.plain.old.res
+------------------------------------------------------------------------------+
| x + |
| x + |
| x + |
| x + |
| x + |
| x x ++ |
| x x ++ |
| x x ++ |
| x x ++ +|
| x x +++ +|
| x x x +++ +|
| xx x x ++++ +|
| xxxx x ++++ +|
| xxxx x ++++ ++|
| xxxxxx ++++ ++|
| xxxxxx ++++ ++|
|x xxxxxx ++++ ++|
|xxxxxxxx ++ ++++ ++|
| |MA_| |_A_| |
+------------------------------------------------------------------------------+
N Min Max Median Avg Stddev
x 64 56.578127 58.412674 57.440191 57.611106 0.47861202
+ 64 74.196758 76.450848 75.310989 75.472311 0.55441925
Difference at 95.0% confidence
17.8612 +/- 0.179445
31.0031% +/- 0.311476%
(Student's t, pooled s = 0.517905)
x lip3.ins.new.res
+ lip3.ins.old.res
+------------------------------------------------------------------------------+
| x + |
| xx ++ |
| xx ++ |
| xxx ++ + |
| xxxx +++ + |
| xxxx +++ + |
| xxxx xx +++ + + |
| xxxxxx xx +++ + + |
| xxxxxx xx + ++++++ ++++ |
| x xxxxxx xx + +++++++ ++++ |
|xx xxxxxxx xxx + ++++++++++++++|
| |_MA__| |__MA__| |
+------------------------------------------------------------------------------+
N Min Max Median Avg Stddev
x 64 38.697547 40.069195 39.342128 39.424654 0.30856729
+ 64 45.445969 47.082288 46.188003 46.277409 0.39019746
Difference at 95.0% confidence
6.85275 +/- 0.121878
17.3819% +/- 0.309142%
(Student's t, pooled s = 0.351758)
x lip3.rem.new.res
+ lip3.rem.old.res
+------------------------------------------------------------------------------+
| x + |
| x ++ |
| x ++ |
| x ++ |
| xxx ++ |
| xxx ++ |
| xxx ++ |
| xxx ++ |
| xxx +++ |
| xxx +++ |
| xxx ++++ |
|xxxx ++++ |
|xxxx ++++ |
|xxxx ++++ |
|xxxx +++++ |
|xxxx ++++++ |
|xxxx ++++++++|
|xxxx ++++++++|
| MA |A_| |
+------------------------------------------------------------------------------+
N Min Max Median Avg Stddev
x 64 31.070099 31.940323 31.451435 31.494973 0.23935193
+ 64 50.423019 52.494157 51.451802 51.421523 0.43900505
Difference at 95.0% confidence
19.9265 +/- 0.122504
63.269% +/- 0.388962%
(Student's t, pooled s = 0.353564)
```