Change Details

Running validity checks continuously. This code {F45802586} simulates the iommu_gas tree map activity. With and without these changes, running on lip3, -O2 compiled: old new 1m21.755s 1m19.769s 1m20.466s 1m19.713s 1m20.450s 1m20.041s 1m20.894s 1m20.095s Diff 108751 reduces the size of iommu_gas.o by 208 bytes. Ran 48 trials on original and Diff 108751 versions of tree.h with the test code here: {F45900390}, then ministat: ``` x times.orig + times +-------------------------------------------------------------------------------------+ | + x | | + x x | | + + ++ ++ + xx**xx x x xxxx x + + x | |++ ++++++++ ++ ++x +**+****xx*** x+ x xxxx x+*xx x+ + + + + +x +x xx x x xx| | |_______________M_|__A_________M_____A___|______________| | +-------------------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 48 80.415631 82.14444 80.879816 81.041191 0.49556651 + 48 79.987447 81.767432 80.508747 80.617606 0.51668018 Difference at 95.0% confidence -0.423585 +/- 0.205222 -0.522678% +/- 0.253232% (Student's t, pooled s = 0.506233) ```

This shrinks iommu_gas.o by 208 bytes. On lip3, for a test program ({F46132450}) that uses no augmentation, this does not change the test binary: $ sum rb_toy rb_toy.orig 13209 19 rb_toy 13209 19 rb_toy.orig Unsurprisingly, they produce similar performance: ``` x times.orig + times +-------------------------------------------------------------------------------------+ | x + | | x + x + | | + x x ++ + *+x +x x + x + + + + | |+++* + ** x*x+**x*x* *** ++ xx*x+*x +x+x x + x + xx+* x +++* *x*xx x x x| | |__|______________M__M_A__A____________________|_| | +-------------------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 48 61.469533 63.283309 62.139805 62.249214 0.51279665 + 48 61.39718 63.025671 62.064204 62.193492 0.52476965 No difference proven at 95.0% confidence ``` For a test program that maintains augmentation (compiled with -DTEST_AUGMENTATION), but (as in the first example) picks random values to insert in the tree, this change shrinks the code size: $ size rb_toy rb_toy.orig text data bss dec hex filename 6014 472 24 6510 0x196e rb_toy 6358 472 24 6854 0x1ac6 rb_toy.orig and ministat reports a small performance improvement: ``` x times.orig + times +-------------------------------------------------------------------------------------+ | + | | x + ++ x + x x | |++ x x ++++ +++x xx +* + xx xxx + + x xxx | |++ xx xx + ++++ + ++** *xx x* **++*x* xxxxxxx + + ++ ++ + ++xx xxxx| | |________|___M________A________MA___________|__________| | +-------------------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 48 87.376449 89.539418 88.406093 88.438795 0.66567261 + 48 87.096947 89.33828 87.893474 88.139996 0.63203003 Difference at 95.0% confidence -0.298799 +/- 0.263127 -0.337859% +/- 0.297524% (Student's t, pooled s = 0.649069) ``` With augmentation, and with inserting the first free block (-DTEST_AUGMENTATION -DINSERT_FIRST_FREE), this patch reduces the executable size: text data bss dec hex filename 6695 480 24 7199 0x1c1f rb_toy.orig 6351 480 24 6855 0x1ac7 rb_toy and performance stats, processed by ministat show: ``` x times.orig + times +-------------------------------------------------------------------------------------+ | + + | | + + | | x + x + + | | + x x +x++*+ x * + +* x ++x+ x | |++ + *xxx xxx xx++**+** +*x*x x+ x *****x*** + x xx ++*+ xx x x| | |_______________M_M_A_A_________________|__| | +-------------------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 48 79.861774 81.958606 80.555018 80.719996 0.61400222 + 48 79.565552 81.681703 80.606281 80.678374 0.56207507 No difference proven at 95.0% confidence ``` So, improvement, sort of.

Running validity checks continuouslyThis shrinks iommu_gas.o by 208 bytes. This code {F45802586} simulates the iommu_gas tree map activity. With and without these changesOn lip3, for a test program ({F46132450}) that uses no augmentation, running on lip3,this does not change the test binary: -O2 compiled:$ sum rb_toy rb_toy.orig 13209 19 rb_toy 13209 19 rb_toy.orig old newUnsurprisingly, they produce similar performance: ``` 1m21.755s 1m19.769sx times.orig 1m20.466s 1m19.713s+ times 1m20.450s 1m20.041s+-------------------------------------------------------------------------------------+ 1m20.894s 1m20.095s| x + | | x + x + | | + x x ++ + *+x +x x + x + + + + | |+++* + ** x*x+**x*x* *** ++ xx*x+*x +x+x x + x + xx+* x +++* *x*xx x x x| | |__|______________M__M_A__A____________________|_| | +-------------------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 48 61.469533 63.283309 62.139805 62.249214 0.51279665 + 48 61.39718 63.025671 62.064204 62.193492 0.52476965 No difference proven at 95.0% confidence Diff 108751 reduces the size of iommu_gas.o by 208 bytes.``` For a test program that maintains augmentation (compiled with -DTEST_AUGMENTATION), but (as in the first example) picks random values to insert in the tree, this change shrinks the code size: $ size rb_toy rb_toy.orig text data bss dec hex filename 6014 472 24 6510 0x196e rb_toy 6358 472 24 6854 0x1ac6 rb_toy.orig Ran 48 trials on original and Diff 108751 versions of tree.h with the test code here: {F45900390}, then ministat:and ministat reports a small performance improvement: ``` x times.orig + times +-------------------------------------------------------------------------------------+ | + x+ | | + x + x x++ x + x |x | | |++ + + ++ ++ + xx**xx x x x x ++++ +++x xx +* xx+ xx xxxx + + + + x |xxx | |++ ++++++++ ++ ++x +**+****xx*** x+ x xx xx + ++++ + ++** *xx x* **++*x* xxxx x+*xx x+xxx + + + + + +x +x + + ++xx x x xx|xxx| | |_______________M_|__A_|___M________A________M_A____A___|___________|__________| | +-------------------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 48 80.415631 7.376449 82.144449.539418 80.8798168.406093 81.0411918.438795 0.4955665166567261 + 48 79.98744787.096947 81.7674329.33828 80.5087477.893474 80.617608.139996 0.5166801863203003 Difference at 95.0% confidence -0.423585298799 +/- 0.20522263127 -0.522678337859% +/- 0.253232%97524% (Student's t, pooled s = 0.506233649069) ``` With augmentation, and with inserting the first free block (-DTEST_AUGMENTATION -DINSERT_FIRST_FREE), this patch reduces the executable size: text data bss dec hex filename 6695 480 24 7199 0x1c1f rb_toy.orig 6351 480 24 6855 0x1ac7 rb_toy and performance stats, processed by ministat show: ``` x times.orig + times +-------------------------------------------------------------------------------------+ | + + | | + + | | x + x + + | | + x x +x++*+ x * + +* x ++x+ x | |++ + *xxx xxx xx++**+** +*x*x x+ x *****x*** + x xx ++*+ xx x x| | |_______________M_M_A_A_________________|__| | +-------------------------------------------------------------------------------------+ N Min Max Median Avg Stddev x 48 79.861774 81.958606 80.555018 80.719996 0.61400222 + 48 79.565552 81.681703 80.606281 80.678374 0.56207507 No difference proven at 95.0% confidence ``` So, improvement, sort of.