Page MenuHomePhabricator
Paste P8098

[WIP!][DomTreeUpdater] Benchmarks on Lazy UpdateStrategy
ActivePublic

Authored by NutshellySima on Aug 7 2018, 9:45 AM.
1. After applying D50300, you can see that the (forward) dominator tree recalculation takes most of the time in the DominatorTree Calculation:
$ time cset shield --exec ./opt -- -O3 -disable-output < ./oggenc.preopt.bc
cset: --> last message, executed args into cpuset "/user", new pid is: 8710
===-------------------------------------------------------------------------===
DTU timing
===-------------------------------------------------------------------------===
Total Execution Time: 0.0173 seconds (0.0175 wall clock)
---User Time--- --User+System-- ---Wall Time--- --- Name ---
0.0165 ( 95.4%) 0.0165 ( 95.4%) 0.0166 ( 95.2%) apply-updates -- DomTree
0.0004 ( 2.0%) 0.0004 ( 2.0%) 0.0004 ( 2.0%) delete-edge -- DomTree
0.0003 ( 1.5%) 0.0003 ( 1.5%) 0.0003 ( 1.8%) insert-edge -- DomTree
0.0001 ( 0.5%) 0.0001 ( 0.5%) 0.0001 ( 0.5%) apply-updates -- PostDomTree
0.0001 ( 0.3%) 0.0001 ( 0.3%) 0.0000 ( 0.3%) insert-edge -- PostDomTree
0.0000 ( 0.3%) 0.0000 ( 0.3%) 0.0000 ( 0.3%) delete-edge -- PostDomTree
0.0173 (100.0%) 0.0173 (100.0%) 0.0175 (100.0%) Total
===-------------------------------------------------------------------------===
DomTree Calculation
===-------------------------------------------------------------------------===
Total Execution Time: 0.0709 seconds (0.0723 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
0.0421 ( 60.8%) 0.0017 (100.0%) 0.0438 ( 61.7%) 0.0449 ( 62.1%) recalculate -- DomTree
0.0215 ( 31.1%) 0.0000 ( 0.0%) 0.0215 ( 30.4%) 0.0216 ( 29.9%) apply-updates -- DomTree
0.0049 ( 7.1%) 0.0000 ( 0.0%) 0.0049 ( 6.9%) 0.0050 ( 6.9%) recalculate -- PostDomTree
0.0004 ( 0.6%) 0.0000 ( 0.0%) 0.0004 ( 0.6%) 0.0004 ( 0.6%) insert-edge -- DomTree
0.0003 ( 0.4%) 0.0000 ( 0.0%) 0.0003 ( 0.4%) 0.0003 ( 0.4%) delete-edge -- DomTree
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) apply-updates -- PostDomTree
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) delete-edge -- PostDomTree
0.0692 (100.0%) 0.0017 (100.0%) 0.0709 (100.0%) 0.0723 (100.0%) Total
real 0m2.545s
user 0m2.513s
sys 0m0.032s
$ time cset shield --exec ./opt -- -O3 -disable-output < ./clang-5.0.0.4.opt.bc
cset: --> last message, executed args into cpuset "/user", new pid is: 8711
===-------------------------------------------------------------------------===
DTU timing
===-------------------------------------------------------------------------===
Total Execution Time: 10.3802 seconds (10.3997 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
10.2153 ( 98.5%) 0.0061 ( 96.4%) 10.2214 ( 98.5%) 10.2405 ( 98.5%) apply-updates -- DomTree
0.1419 ( 1.4%) 0.0000 ( 0.0%) 0.1419 ( 1.4%) 0.1419 ( 1.4%) recalculate -- DomTree
0.0069 ( 0.1%) 0.0001 ( 0.9%) 0.0070 ( 0.1%) 0.0070 ( 0.1%) delete-edge -- DomTree
0.0063 ( 0.1%) 0.0001 ( 2.1%) 0.0064 ( 0.1%) 0.0064 ( 0.1%) apply-updates -- PostDomTree
0.0027 ( 0.0%) 0.0000 ( 0.5%) 0.0028 ( 0.0%) 0.0031 ( 0.0%) insert-edge -- DomTree
0.0003 ( 0.0%) 0.0000 ( 0.0%) 0.0003 ( 0.0%) 0.0004 ( 0.0%) insert-edge -- PostDomTree
0.0004 ( 0.0%) 0.0000 ( 0.0%) 0.0004 ( 0.0%) 0.0003 ( 0.0%) delete-edge -- PostDomTree
0.0001 ( 0.0%) 0.0000 ( 0.0%) 0.0001 ( 0.0%) 0.0001 ( 0.0%) recalculate -- PostDomTree
10.3739 (100.0%) 0.0063 (100.0%) 10.3802 (100.0%) 10.3997 (100.0%) Total
===-------------------------------------------------------------------------===
DomTree Calculation
===-------------------------------------------------------------------------===
Total Execution Time: 30.7051 seconds (30.8960 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
17.9997 ( 58.9%) 0.1137 ( 89.4%) 18.1134 ( 59.0%) 18.2778 ( 59.2%) recalculate -- DomTree
10.5674 ( 34.6%) 0.0096 ( 7.6%) 10.5771 ( 34.4%) 10.5818 ( 34.2%) apply-updates -- DomTree
1.9842 ( 6.5%) 0.0037 ( 2.9%) 1.9878 ( 6.5%) 2.0096 ( 6.5%) recalculate -- PostDomTree
0.0138 ( 0.0%) 0.0001 ( 0.0%) 0.0139 ( 0.0%) 0.0139 ( 0.0%) insert-edge -- DomTree
0.0125 ( 0.0%) 0.0001 ( 0.0%) 0.0125 ( 0.0%) 0.0125 ( 0.0%) delete-edge -- DomTree
0.0003 ( 0.0%) 0.0000 ( 0.0%) 0.0003 ( 0.0%) 0.0003 ( 0.0%) apply-updates -- PostDomTree
0.0001 ( 0.0%) 0.0000 ( 0.0%) 0.0001 ( 0.0%) 0.0001 ( 0.0%) delete-edge -- PostDomTree
30.5780 (100.0%) 0.1272 (100.0%) 30.7051 (100.0%) 30.8960 (100.0%) Total
real 11m40.031s
user 11m36.660s
sys 0m3.372s
2. After applying D50313 then switching all passes to use the Lazy UpdateStrategy, you can see that the performance of Auto[3] is almost in line with the current DomTreeUpdater implementation:
$ time cset shield --exec ./opt-Lazy -- -O3 -disable-output < ./clang-5.0.0.0.preopt.bc
$ time cset shield --exec ./opt-Lazy -- -O3 -disable-output < ./clang-5.0.0.4.opt.bc
$ time cset shield --exec ./opt-Lazy -- -O3 -disable-output < ./oggenc.preopt.bc
cset: --> last message, executed args into cpuset "/user", new pid is: 28298
===-------------------------------------------------------------------------===
DTU timing
===-------------------------------------------------------------------------===
Total Execution Time: 14.7734 seconds (14.8645 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
12.9482 ( 88.3%) 0.0755 ( 67.4%) 13.0236 ( 88.2%) 13.0276 ( 87.6%) apply-updates -- DomTree
1.2977 ( 8.9%) 0.0282 ( 25.2%) 1.3259 ( 9.0%) 1.4116 ( 9.5%) Deduplicate
0.2161 ( 1.5%) 0.0071 ( 6.3%) 0.2233 ( 1.5%) 0.2237 ( 1.5%) PendPush
0.1715 ( 1.2%) 0.0006 ( 0.6%) 0.1722 ( 1.2%) 0.1722 ( 1.2%) recalculate -- DomTree
0.0111 ( 0.1%) 0.0001 ( 0.1%) 0.0112 ( 0.1%) 0.0112 ( 0.1%) delete-edge -- DomTree
0.0083 ( 0.1%) 0.0004 ( 0.3%) 0.0086 ( 0.1%) 0.0088 ( 0.1%) apply-updates -- PostDomTree
0.0067 ( 0.0%) 0.0001 ( 0.1%) 0.0067 ( 0.0%) 0.0073 ( 0.0%) insert-edge -- DomTree
0.0008 ( 0.0%) 0.0000 ( 0.0%) 0.0008 ( 0.0%) 0.0008 ( 0.0%) recalculate -- PostDomTree
0.0005 ( 0.0%) 0.0000 ( 0.0%) 0.0005 ( 0.0%) 0.0006 ( 0.0%) delete-edge -- PostDomTree
0.0006 ( 0.0%) 0.0000 ( 0.0%) 0.0006 ( 0.0%) 0.0006 ( 0.0%) insert-edge -- PostDomTree
14.6615 (100.0%) 0.1119 (100.0%) 14.7734 (100.0%) 14.8645 (100.0%) Total
===-------------------------------------------------------------------------===
DomTree Calculation
===-------------------------------------------------------------------------===
Total Execution Time: 32.5030 seconds (32.6866 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
16.6292 ( 51.5%) 0.1394 ( 58.9%) 16.7686 ( 51.6%) 16.9289 ( 51.8%) recalculate -- DomTree
13.5132 ( 41.9%) 0.0841 ( 35.5%) 13.5974 ( 41.8%) 13.6033 ( 41.6%) apply-updates -- DomTree
2.0905 ( 6.5%) 0.0130 ( 5.5%) 2.1035 ( 6.5%) 2.1210 ( 6.5%) recalculate -- PostDomTree
0.0156 ( 0.0%) 0.0001 ( 0.0%) 0.0157 ( 0.0%) 0.0156 ( 0.0%) insert-edge -- DomTree
0.0154 ( 0.0%) 0.0001 ( 0.0%) 0.0155 ( 0.0%) 0.0155 ( 0.0%) delete-edge -- DomTree
0.0012 ( 0.0%) 0.0000 ( 0.0%) 0.0012 ( 0.0%) 0.0013 ( 0.0%) apply-updates -- PostDomTree
0.0010 ( 0.0%) 0.0000 ( 0.0%) 0.0010 ( 0.0%) 0.0010 ( 0.0%) delete-edge -- PostDomTree
32.2662 (100.0%) 0.2368 (100.0%) 32.5030 (100.0%) 32.6866 (100.0%) Total
real 12m40.025s
user 12m35.589s
sys 0m4.444s
cset: --> last message, executed args into cpuset "/user", new pid is: 28307
===-------------------------------------------------------------------------===
DTU timing
===-------------------------------------------------------------------------===
Total Execution Time: 11.3560 seconds (11.4317 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
10.1005 ( 89.5%) 0.0326 ( 48.5%) 10.1331 ( 89.2%) 10.1371 ( 88.7%) apply-updates -- DomTree
0.8801 ( 7.8%) 0.0298 ( 44.3%) 0.9099 ( 8.0%) 0.9802 ( 8.6%) Deduplicate
0.1498 ( 1.3%) 0.0046 ( 6.8%) 0.1544 ( 1.4%) 0.1553 ( 1.4%) PendPush
0.1418 ( 1.3%) 0.0000 ( 0.0%) 0.1418 ( 1.2%) 0.1418 ( 1.2%) recalculate -- DomTree
0.0069 ( 0.1%) 0.0000 ( 0.0%) 0.0069 ( 0.1%) 0.0069 ( 0.1%) delete-edge -- DomTree
0.0061 ( 0.1%) 0.0003 ( 0.4%) 0.0063 ( 0.1%) 0.0064 ( 0.1%) apply-updates -- PostDomTree
0.0028 ( 0.0%) 0.0000 ( 0.0%) 0.0028 ( 0.0%) 0.0031 ( 0.0%) insert-edge -- DomTree
0.0004 ( 0.0%) 0.0000 ( 0.0%) 0.0004 ( 0.0%) 0.0004 ( 0.0%) delete-edge -- PostDomTree
0.0004 ( 0.0%) 0.0000 ( 0.0%) 0.0004 ( 0.0%) 0.0004 ( 0.0%) insert-edge -- PostDomTree
0.0001 ( 0.0%) 0.0000 ( 0.0%) 0.0001 ( 0.0%) 0.0001 ( 0.0%) recalculate -- PostDomTree
11.2887 (100.0%) 0.0673 (100.0%) 11.3560 (100.0%) 11.4317 (100.0%) Total
===-------------------------------------------------------------------------===
DomTree Calculation
===-------------------------------------------------------------------------===
Total Execution Time: 30.5087 seconds (30.6683 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
17.8911 ( 59.0%) 0.1267 ( 72.6%) 18.0178 ( 59.1%) 18.1611 ( 59.2%) recalculate -- DomTree
10.4598 ( 34.5%) 0.0392 ( 22.5%) 10.4990 ( 34.4%) 10.5017 ( 34.2%) apply-updates -- DomTree
1.9567 ( 6.5%) 0.0085 ( 4.9%) 1.9652 ( 6.4%) 1.9790 ( 6.5%) recalculate -- PostDomTree
0.0138 ( 0.0%) 0.0001 ( 0.1%) 0.0139 ( 0.0%) 0.0139 ( 0.0%) insert-edge -- DomTree
0.0123 ( 0.0%) 0.0000 ( 0.0%) 0.0124 ( 0.0%) 0.0123 ( 0.0%) delete-edge -- DomTree
0.0003 ( 0.0%) 0.0000 ( 0.0%) 0.0003 ( 0.0%) 0.0003 ( 0.0%) apply-updates -- PostDomTree
0.0001 ( 0.0%) 0.0000 ( 0.0%) 0.0001 ( 0.0%) 0.0001 ( 0.0%) delete-edge -- PostDomTree
30.3341 (100.0%) 0.1746 (100.0%) 30.5087 (100.0%) 30.6683 (100.0%) Total
real 11m31.584s
user 11m27.182s
sys 0m4.372s
cset: --> last message, executed args into cpuset "/user", new pid is: 28363
===-------------------------------------------------------------------------===
DTU timing
===-------------------------------------------------------------------------===
Total Execution Time: 0.0205 seconds (0.0208 wall clock)
---User Time--- --User+System-- ---Wall Time--- --- Name ---
0.0162 ( 78.9%) 0.0162 ( 78.9%) 0.0162 ( 77.7%) apply-updates -- DomTree
0.0027 ( 13.4%) 0.0027 ( 13.4%) 0.0031 ( 14.6%) Deduplicate
0.0008 ( 3.7%) 0.0008 ( 3.7%) 0.0007 ( 3.5%) PendPush
0.0004 ( 1.8%) 0.0004 ( 1.8%) 0.0004 ( 1.7%) delete-edge -- DomTree
0.0003 ( 1.3%) 0.0003 ( 1.3%) 0.0003 ( 1.5%) insert-edge -- DomTree
0.0001 ( 0.4%) 0.0001 ( 0.4%) 0.0001 ( 0.4%) apply-updates -- PostDomTree
0.0001 ( 0.3%) 0.0001 ( 0.3%) 0.0001 ( 0.3%) insert-edge -- PostDomTree
0.0000 ( 0.2%) 0.0000 ( 0.2%) 0.0000 ( 0.2%) delete-edge -- PostDomTree
0.0205 (100.0%) 0.0205 (100.0%) 0.0208 (100.0%) Total
===-------------------------------------------------------------------------===
DomTree Calculation
===-------------------------------------------------------------------------===
Total Execution Time: 0.0696 seconds (0.0708 wall clock)
---User Time--- --System Time-- --User+System-- ---Wall Time--- --- Name ---
0.0424 ( 61.4%) 0.0006 (100.0%) 0.0430 ( 61.7%) 0.0440 ( 62.1%) recalculate -- DomTree
0.0211 ( 30.6%) 0.0000 ( 0.0%) 0.0211 ( 30.3%) 0.0212 ( 30.0%) apply-updates -- DomTree
0.0048 ( 7.0%) 0.0000 ( 0.0%) 0.0048 ( 7.0%) 0.0049 ( 7.0%) recalculate -- PostDomTree
0.0004 ( 0.6%) 0.0000 ( 0.0%) 0.0004 ( 0.6%) 0.0004 ( 0.6%) insert-edge -- DomTree
0.0003 ( 0.4%) 0.0000 ( 0.0%) 0.0003 ( 0.4%) 0.0003 ( 0.4%) delete-edge -- DomTree
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) apply-updates -- PostDomTree
0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) 0.0000 ( 0.0%) delete-edge -- PostDomTree
0.0691 (100.0%) 0.0006 (100.0%) 0.0696 (100.0%) 0.0708 (100.0%) Total
real 0m2.555s
user 0m2.531s
sys 0m0.024s

Event Timeline

NutshellySima created this object with visibility "Public (No Login Required)".
NutshellySima created this object with edit policy "NutshellySima (Chijun Sima)".
NutshellySima edited the content of this paste. (Show Details)Aug 11 2018, 5:11 AM