correct inlining times
Stephen Weeks
sweeks@research.nj.nec.com
Wed, 17 Feb 1999 12:43:00 -0500
I reran the experiments last night.
Here's a reminder of the setup.
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 produce almost identical results
* nonRecursive always produces smaller times than the others
* 3 rounds is necessary (in some benchmarks) for the leaf inliners
to produce their best results, but 4 rounds never improves over 3
* 1 round is enough for nonRecursive to produce its best result
(with some minor exceptions)
* threshold 100 is necessary, and 500 never helps
threshold
10 50 100 500
------------------------------------------------------------
barnes-hut
1 round
nonRecursive 31.49 25.18 15.16 15.03
leaf 31.05 31.11 31.12 31.12
leafNoLoop 31.02 31.12 31.11 31.12
2 rounds
nonRecursive 30.75 25.32 15.08 15.01
leaf 30.67 26.02 20.59 16.22
leafNoLoop 30.69 26.04 20.68 16.19
3 rounds
nonRecursive 31.47 25.27 15.15 15.02
leaf 30.76 26.02 20.53 15.83
leafNoLoop 30.77 25.65 20.06 15.83
4 rounds
nonRecursive 30.77 25.31 15.09 15.0
leaf 30.67 25.84 19.8 15.04
leafNoLoop 30.67 25.64 19.84 14.97
------------------------------------------------------------
count-graphs
1 round
nonRecursive 44.76 12.66 18.24 18.06
leaf 48.16 45.34 45.33 45.34
leafNoLoop 48.15 46.63 46.63 46.63
2 rounds
nonRecursive 43.68 12.75 11.2 18.06
leaf 47.28 30.26 30.04 30.03
leafNoLoop 47.3 31.36 31.37 31.37
3 rounds
nonRecursive 44.78 12.66 11.44 18.07
leaf 48.26 18.37 18.07 18.19
leafNoLoop 48.24 19.3 19.31 19.27
4 rounds
nonRecursive 43.68 12.84 11.2 18.06
leaf 47.32 18.57 18.14 17.9
leafNoLoop 47.37 19.24 19.23 19.26
------------------------------------------------------------
fft
1 round
nonRecursive 129.3 43.58 41.9 41.38
leaf 129.72 116.99 116.99 116.9
leafNoLoop 129.66 116.7 116.91 116.96
2 rounds
nonRecursive 127.14 43.46 41.87 41.48
leaf 128.28 43.16 40.98 40.39
leafNoLoop 128.22 43.42 40.89 40.5
3 rounds
nonRecursive 129.2 43.72 42.1 41.66
leaf 142.07 43.4 40.98 40.93
leafNoLoop 142.2 43.36 40.55 40.15
4 rounds
nonRecursive 127.15 43.55 41.84 41.5
leaf 128.42 43.05 41.01 40.75
leafNoLoop 128.37 43.26 40.71 40.76
------------------------------------------------------------
knuth-bendix
1 round
nonRecursive 39.93 40.15 23.46 23.64
leaf 47.58 43.41 44.18 44.14
leafNoLoop 47.73 43.69 43.6 43.73
2 rounds
nonRecursive 40.40 40.04 23.58 23.59
leaf 43.51 43.96 43.77 43.76
leafNoLoop 43.58 44.19 43.19 43.27
3 rounds
nonRecursive 40.0 40.11 23.48 23.62
leaf 43.4 43.25 43.16 43.19
leafNoLoop 43.43 43.16 43.07 43.07
4 rounds
nonRecursive 40.34 39.98 23.57 23.61
leaf 43.48 43.54 43.23 43.26
leafNoLoop 43.48 44.08 43.2 43.12
------------------------------------------------------------
lexgen
1 round
nonRecursive 125.49 50.34 31.87 32.01
leaf 131.56 126.64 126.59 126.57
leafNoLoop 131.55 126.67 126.64 126.69
2 rounds
nonRecursive 124.25 49.21 31.25 31.29
leaf 128.03 51.99 50.77 50.76
leafNoLoop 127.93 51.57 50.88 50.95
3 rounds
nonRecursive 125.49 50.37 31.93 31.98
leaf 125.98 50.82 47.54 47.61
leafNoLoop 126.02 51.88 49.81 49.74
4 rounds
nonRecursive 124.22 49.16 31.15 31.18
leaf 127.96 51.19 47.4 47.37
leafNoLoop 127.89 50.78 50.58 50.71
------------------------------------------------------------
life
1 round
nonRecursive 69.81 67.92 70.02 70.03
leaf 66.47 78.30 78.20 78.26
leafNoLoop 66.56 66.72 66.56 66.68
2 rounds
nonRecursive 67.28 68.65 68.38 68.14
leaf 71.03 68.92 68.64 68.63
leafNoLoop 70.98 66.15 65.77 65.75
3 rounds
nonRecursive 69.81 67.94 70.00 70.0
leaf 70.68 68.0 68.08 68.05
leafNoLoop 70.61 65.95 61.46 61.47
4 rounds
nonRecursive 67.01 68.55 68.02 68.15
leaf 70.86 68.81 68.14 70.19
leafNoLoop 71.0 66.24 65.73 65.67
------------------------------------------------------------
logic
1 round
nonRecursive 61.33 60.49 60.65 58.9
leaf 58.98 59.12 58.99 58.97
leafNoLoop 59.11 58.94 58.98 59.0
2 rounds
nonRecursive 59.48 60.2 62.11 61.98
leaf 59.91 59.87 59.91 59.87
leafNoLoop 59.90 60.01 59.91 59.85
3 rounds
nonRecursive 60.2 60.53 60.62 61.08
leaf 59.0 58.99 59.04 58.94
leafNoLoop 59.02 58.96 59.0 59.15
4 rounds
nonRecursive 59.33 60.15 61.95 62.15
leaf 59.89 59.84 59.9 59.85
leafNoLoop 59.88 59.87 59.88 59.8
------------------------------------------------------------
mandelbrot
1 round
nonRecursive 15.96 15.96 15.96 15.96
leaf 15.96 15.95 15.94 15.95
leafNoLoop 15.95 15.97 15.95 15.96
2 rounds
nonRecursive 15.95 15.96 15.95 15.96
leaf 15.96 15.96 15.96 15.96
leafNoLoop 15.96 15.96 15.96 15.97
3 rounds
nonRecursive 15.95 15.97 15.96 15.96
leaf 15.96 15.96 15.95 15.96
leafNoLoop 15.96 15.91 15.96 15.95
4 rounds
nonRecursive 15.97 15.97 15.95 15.96
leaf 15.96 15.95 15.93 15.95
leafNoLoop 15.97 15.96 15.96 15.96
------------------------------------------------------------
matrix-multiply
1 round
nonRecursive 68.82 14.1 13.74 13.33
leaf 68.78 68.74 68.72 68.77
leafNoLoop 68.92 68.63 68.84 68.83
2 rounds
nonRecursive 67.94 14.1 13.89 13.9
leaf 67.92 41.72 41.75 41.71
leafNoLoop 67.93 41.73 41.81 41.85
3 rounds
nonRecursive 68.67 14.34 13.61 13.68
leaf 69.01 14.22 13.61 13.33
leafNoLoop 69.16 14.27 14.27 14.37
4 rounds
nonRecursive 68.12 14.06 13.87 14.0
leaf 68.11 14.29 14.37 13.88
leafNoLoop 68.36 14.13 14.09 14.32
------------------------------------------------------------
nucleic
1 round
nonRecursive 35.1 32.61 32.62 32.27
leaf 35.63 34.89 34.97 34.95
leafNoLoop 35.62 34.78 34.79 34.77
2 rounds
nonRecursive 35.36 32.88 32.86 32.12
leaf 35.37 34.61 34.52 34.95
leafNoLoop 35.35 35.04 35.06 35.68
3 rounds
nonRecursive 35.14 32.64 32.56 32.28
leaf 35.57 34.7 34.68 33.45
leafNoLoop 35.62 34.77 34.83 33.72
4 rounds
nonRecursive 35.32 32.86 32.8 32.19
leaf 35.38 34.59 34.59 32.96
leafNoLoop 35.36 35.06 35.02 34.12
------------------------------------------------------------
simple
1 round
nonRecursive 36.59 17.02 17.61 16.87
leaf 39.97 38.77 39.22 39.24
leafNoLoop 39.96 38.66 39.21 39.23
2 rounds
nonRecursive 36.61 16.91 17.54 16.77
leaf 37.13 32.35 24.71 24.7
leafNoLoop 37.13 32.98 24.94 24.94
3 rounds
nonRecursive 36.28 17.02 17.47 16.78
leaf 36.57 31.93 17.84 17.75
leafNoLoop 36.57 32.01 17.99 17.71
4 rounds
nonRecursive 36.74 16.92 17.55 16.77
leaf 37.1 32.05 17.4 17.63
leafNoLoop 37.2 32.46 18.12 18.89
------------------------------------------------------------
tsp
1 round
nonRecursive 60.46 48.93 47.68 33.29
leaf 59.82 60.32 60.6 60.63
leafNoLoop 59.84 60.26 60.31 60.27
2 rounds
nonRecursive 60.74 49.97 49.23 32.87
leaf 60.78 49.73 49.09 35.32
leafNoLoop 60.69 49.73 49.17 35.31
3 rounds
nonRecursive 60.47 48.93 47.69 32.88
leaf 60.47 50.89 49.46 34.54
leafNoLoop 60.46 49.68 50.96 34.72
4 rounds
nonRecursive 60.77 49.98 49.26 32.87
leaf 60.78 51.98 47.94 34.98
leafNoLoop 60.75 49.74 49.27 34.76
------------------------------------------------------------