inlining experiments
Stephen Weeks
sweeks@research.nj.nec.com
Tue, 16 Feb 1999 14:11:04 -0500
Here are the results of the inlining experiments that I ran over the
last couple of days. There are four dimensions:
* benchmark
* inline strategy
- nonRecursive: inline small procedures that aren't part of a
loop in the call graph (where the call graph
excludes edges for calls to large procedures)
- leaf : inline small procedures that contain no calls (syntactically)
- leafNoLoop : same as leaf but procedure must also be loop free
* inline threshold (10, 50, 100, 500)
* number of rounds (1-4)
The data are grouped by benchmark, then round.
I give the running time in seconds for each possibility.
Executive summary:
* leaf and leafNoLoop are almost equivalent
* nonRecursive beats them in every case except for one, often
by a significant amount (2X-4X)
Code sizes will follow shortly.
--------------------------------------------------------------------------------
threshold
10 50 100 500
------------------------------------------------------------
barnes-hut
1 round
nonRecursive 31.5 25.19 15.17 15.01
leaf 31.03 31.12 31.13 31.14
leafNoLoop 31.04 31.14 31.13 31.14
2 rounds
nonRecursive 31.46 25.2 15.17 15.03
leaf 30.95 31.15 31.14 31.12
leafNoLoop 31.03 31.12 31.14 31.14
3 rounds
nonRecursive 31.5 25.17 15.17 15.02
leaf 30.94 31.12 31.15 31.13
leafNoLoop 30.91 31.13 31.14 31.14
4 rounds
nonRecursive 31.52 25.2 15.16 15.03
leaf 31.05 31.14 31.15 31.11
leafNoLoop 31.01 31.14 31.15 31.14
------------------------------------------------------------
count-graphs
1 round
nonRecursive 44.67 12.66 18.23 18.05
leaf 48.19 45.33 45.35 45.34
leafNoLoop 48.17 46.64 46.6 46.62
2 rounds
nonRecursive 44.78 12.66 18.23 18.07
leaf 48.15 45.33 45.35 45.36
leafNoLoop 48.18 46.67 46.63 46.51
3 rounds
nonRecursive 44.76 12.66 18.27 18.07
leaf 48.11 45.35 45.35 45.36
leafNoLoop 48.15 46.64 46.63 46.63
4 rounds
nonRecursive 44.77 12.64 18.24 18.06
leaf 48.19 45.25 45.33 45.33
leafNoLoop 48.18 46.62 46.62 46.61
------------------------------------------------------------
fft
1 round
nonRecursive 128.98 43.38 41.3 40.99
leaf 129.47 116.61 116.55 116.56
leafNoLoop 129.21 116.58 116.62 116.6
2 rounds
nonRecursive 128.94 43.06 41.47 40.97
leaf 129.55 116.58 116.57 116.43
leafNoLoop 129.36 116.65 116.55 116.64
3 rounds
nonRecursive 128.92 43.39 41.69 41.25
leaf 129.64 116.78 116.64 116.28
leafNoLoop 129.58 116.74 116.68 116.67
4 rounds
nonRecursive 128.97 43.36 41.61 41.22
leaf 129.59 116.69 116.63 116.57
leafNoLoop 129.57 116.69 116.78 116.53
------------------------------------------------------------
knuth-bendix
1 round
nonRecursive 39.73 40.01 23.48 23.6
leaf 47.52 43.3 43.99 44.03
leafNoLoop 47.51 43.63 43.51 43.59
2 rounds
nonRecursive 39.8 40.06 23.48 23.63
leaf 47.51 43.32 44.02 43.99
leafNoLoop 47.54 43.66 43.48 43.55
3 rounds
nonRecursive 39.72 40.04 23.49 23.62
leaf 47.52 43.32 44.03 44.02
leafNoLoop 47.51 43.65 43.49 43.56
4 rounds
nonRecursive 39.78 39.99 23.49 23.62
leaf 47.54 43.27 43.99 44.02
leafNoLoop 47.53 43.64 43.52 43.56
------------------------------------------------------------
lexgen
1 round
nonRecursive 125.54 50.29 31.96 32.0
leaf 131.86 126.52 126.6 126.58
leafNoLoop 131.8 126.57 126.54 126.66
2 rounds
nonRecursive 125.66 50.25 31.9 31.98
leaf 131.86 126.6 126.42 126.55
leafNoLoop 131.86 126.65 126.72 126.65
3 rounds
nonRecursive 125.62 50.25 31.93 32.11
leaf 131.74 126.53 126.58 126.42
leafNoLoop 131.77 126.62 126.73 126.55
4 rounds
nonRecursive 125.62 50.34 32.06 32.0
leaf 131.78 126.53 126.53 126.52
leafNoLoop 131.78 126.66 126.57 126.65
------------------------------------------------------------
life
1 round
nonRecursive 69.84 67.83 70.0 70.02
leaf 66.53 78.31 78.3 78.23
leafNoLoop 66.54 66.47 66.52 66.53
2 rounds
nonRecursive 69.84 67.84 70.01 70.02
leaf 66.51 78.25 78.29 78.27
leafNoLoop 66.51 66.56 66.53 66.53
3 rounds
nonRecursive 69.79 67.78 70.01 69.99
leaf 66.53 78.3 78.27 78.29
leafNoLoop 66.45 66.53 66.39 66.51
4 rounds
nonRecursive 69.83 67.86 70.0 70.0
leaf 66.46 78.26 78.17 78.29
leafNoLoop 66.52 66.54 66.53 66.55
------------------------------------------------------------
logic
1 round
nonRecursive 61.29 60.65 60.76 58.8
leaf 58.99 59.03 59.04 58.95
leafNoLoop 59.01 58.97 59.05 59.09
2 rounds
nonRecursive 61.45 60.68 60.74 58.79
leaf 58.89 59.0 58.89 59.0
leafNoLoop 58.95 59.07 59.0 58.98
3 rounds
nonRecursive 61.31 60.59 60.73 58.76
leaf 58.95 58.96 59.08 59.04
leafNoLoop 59.02 58.93 58.97 58.96
4 rounds
nonRecursive 61.4 60.74 60.74 58.79
leaf 59.03 58.86 59.05 58.87
leafNoLoop 58.93 59.23 58.96 58.94
------------------------------------------------------------
mandelbrot
1 round
nonRecursive 15.96 15.96 15.97 15.96
leaf 15.96 15.96 15.96 15.94
leafNoLoop 15.95 15.97 15.96 15.95
2 rounds
nonRecursive 15.97 15.96 15.96 15.95
leaf 15.93 15.96 15.96 15.96
leafNoLoop 15.95 15.96 15.96 15.95
3 rounds
nonRecursive 15.96 15.96 15.96 15.96
leaf 15.96 15.96 15.96 15.96
leafNoLoop 15.95 15.95 15.96 15.96
4 rounds
nonRecursive 15.96 15.96 15.96 15.97
leaf 15.97 15.96 15.93 15.96
leafNoLoop 15.95 15.96 15.96 15.96
------------------------------------------------------------
matrix-multiply
1 round
nonRecursive 68.93 14.37 13.39 13.66
leaf 68.88 69.07 69.16 69.05
leafNoLoop 69.24 68.91 68.79 68.98
2 rounds
nonRecursive 69.02 14.56 13.66 13.43
leaf 69.02 69.15 68.76 68.98
leafNoLoop 69.02 68.93 69.04 69.01
3 rounds
nonRecursive 68.89 14.4 13.97 13.4
leaf 69.17 68.89 68.86 68.89
leafNoLoop 68.90 69.17 68.91 68.95
4 rounds
nonRecursive 68.91 14.44 13.58 13.68
leaf 68.86 68.78 69.07 69.10
leafNoLoop 69.27 68.90 69.13 69.08
------------------------------------------------------------
nucleic
1 round
nonRecursive 35.12 32.64 32.65 32.3
leaf 35.68 35.01 34.94 35.01
leafNoLoop 35.67 34.82 34.8 34.83
2 rounds
nonRecursive 35.13 32.65 32.66 32.29
leaf 35.72 34.99 35.02 35.01
leafNoLoop 35.67 34.99 34.81 34.81
3 rounds
nonRecursive 35.12 32.65 32.65 32.29
leaf 35.69 35.0 34.99 35.02
leafNoLoop 35.71 34.81 34.8 34.77
4 rounds
nonRecursive 35.13 32.67 32.64 32.3
leaf 35.67 35.0 35.01 34.99
leafNoLoop 35.66 34.75 34.82 34.8
------------------------------------------------------------
simple
1 round
nonRecursive 36.66 17.03 17.63 16.89
leaf 39.95 38.84 39.23 39.25
leafNoLoop 39.96 38.67 39.14 39.15
2 rounds
nonRecursive 36.68 17.06 17.61 16.88
leaf 39.95 38.86 39.24 39.25
leafNoLoop 39.96 38.68 39.16 39.14
3 rounds
nonRecursive 36.69 16.98 17.63 16.88
leaf 39.94 38.84 39.25 39.24
leafNoLoop 39.94 38.64 39.15 39.14
4 rounds
nonRecursive 36.68 17.03 17.63 16.88
leaf 39.95 38.85 39.23 39.23
leafNoLoop 39.89 38.68 39.13 39.13
------------------------------------------------------------
tsp
1 round
nonRecursive 60.48 48.94 47.69 33.28
leaf 59.86 60.32 60.55 60.63
leafNoLoop 59.78 60.3 60.3 60.31
2 rounds
nonRecursive 60.47 48.93 47.7 33.32
leaf 59.84 60.31 60.56 60.63
leafNoLoop 59.82 60.3 60.32 60.34
3 rounds
nonRecursive 60.46 48.90 47.67 33.33
leaf 59.79 60.28 60.65 60.63
leafNoLoop 59.85 60.32 60.32 60.29
4 rounds
nonRecursive 60.47 48.92 47.62 33.32
leaf 59.84 60.32 60.63 60.62
leafNoLoop 59.85 60.3 60.34 60.22
------------------------------------------------------------