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

------------------------------------------------------------