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

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