CS 412/413 Project Presentation Results

CS 412/413
Introduction to Compilers
Spring 2004

BENCHMARKS
Benchmark	Lines	Description
Ackermann	33	Computes Ackermann's numbers
Constant	119	Contains an expression which adds 1000 constants
DnaAlign	272	Global alignment on DNA with a linear gap penalty
Heapsort	100	Runs heapsort on an array of integers
Matrix	139	Divide-and-conquer matrix multiply
MethCall	79	Repeatedly invokes virtual methods
Pi	91	Computes digits of pi
Primes	349	Builds 5x5 digit squares with primes on rows, columns, and diags.
TcpRouting	496	Simulates a TCP routing algorithm

The tables below show the complete results from the final project presentations. To preserve anonymity, the groups were shuffled and renamed.
The tests were performed on a 1.8 GHz Pentium machine, under the Cygwin environment.
The first table shows the running times (in seconds) for the generated executables files with no optimizations turned on. Programs were forced to terminate after a timeout period of 2 minutes. In case of error, the corresponding entry shows the reason why the program failed:

The overall performance factor was computed as the average of the ratios between the best running time for the currently tested group and the best running time for all groups (column "Best"). Benchmarks which failed were not taken into account. The closer the factor is to 1, the better the overall performance is.

RUNNING TIMES: Base Compilers
Group	A	B	C	D	E	F	G	H
Ackermann	3.76	5.00	1.30	6.06	1.26	2.43	2.92	asm
Constant	19.35	9.20	19.36	comp	18.53	10.81	10.93	10.86
DnaAlign	res	exc	0.37	0.84	0.56	0.37	0.40	asm
Heapsort	9.80	exc	5.96	11.43	8.55	6.06	6.03	6.85
Matrix	9.08	10.65	8.41	14.52	10.63	8.08	8.60	8.92
MethCall	5.58	comp	res	3.41	comp	1.98	exc	1.71
Pi	3.48	res	2.75	4.32	4.17	3.86	2.66	2.77
Primes	comp	comp	3.71	12.87	comp	4.67	5.79	asm
TcpRouting	comp	asm	exc	0.17	asm	0.10	ctime	exc
Tests Passed	6	3	7	8	6	9	7	5

The second table shows the running times optimized executables. For each benchmark, the compilers were tested in three configurations: with LIR (dataflow) optimizations (opt), with backend optimizations, i.e., instruction selection and register allocation (opt-backend), and with all optimizations turned on (opt-all).

RUNNING TIMES: Optimizations
Group		A	B	C	D	E	F	G	H	Best
Ackermann	opt-lir opt-backend opt-all	4.01 exc exc	comp comp comp	1.31 1.30 1.30	6.27 3.53 1.08	1.12 n/a n/a	2.53 1.35 1.51	2.92 0.99 0.98	comp 1.08 comp	0.98
Constant	opt-lir opt-backend opt-all	0.18 0.63 0.29	comp comp comp	20.03 20.18 19.82	comp comp comp	0.07 n/a n/a	0.07 0.64 0.11	0.15 0.84 0.07	0.10 comp 0.07	0.07
DnaAlign	opt-lir opt-backend opt-all	res asm asm	comp comp comp	res res res	ctime 0.54 ctime	comp n/a n/a	comp res comp	0.40 0.40 res	comp 0.37 comp	0.37
Heapsort	opt-lir opt-backend opt-all	time res res	comp comp comp	6.72 6.02 5.87	exc 6.57 asm	8.14 n/a n/a	res exc exc	6.46 4.30 res	comp 6.75 comp	4.30
Matrix	opt-lir opt-backend opt-all	time exc asm	comp comp comp	8.55 8.87 8.95	12.25 9.57 7.20	10.77 n/a n/a	comp exc comp	8.32 8.02 8.69	comp 8.14 comp	7.20
MethCall	opt-lir opt-backend opt-all	time res exc	comp comp comp	exc exc exc	2.76 2.18 1.21	comp n/a n/a	1.97 exc exc	exc exc exc	comp 1.94 comp	1.21
Pi	opt-lir opt-backend opt-all	res asm asm	comp comp comp	2.60 2.49 2.57	3.57 2.48 2.11	3.78 n/a n/a	res exc exc	2.73 2.51 2.66	comp 2.11 comp	2.11
Primes	opt-lir opt-backend opt-all	comp comp comp	comp comp comp	3.92 3.92 3.80	12.18 6.28 2.61	comp n/a n/a	comp exc comp	5.76 3.18 3.62	comp asm comp	2.61
TcpRouting	opt-lir opt-backend opt-all	comp comp comp	ctime comp ctime	res res res	ctime 0.10 ctime	asm n/a n/a	res exc exc	res asm asm	comp asm comp	0.10
Tests Passed		4	0	18	18	5	7	19	8
Overall Performance Factor		3.33	-	47.18	1.13	1.46	1.39	1.08	1.20

The third table shows the compile times (in seconds). Each compiler was tested without optimizations (base), with LIR optimizations (opt-lir), and with backend optimizations (opt-backend). Compilers were also forced to terminate after a timeout period of 2 minutes. In case of error, the corresponding entry shows the reason why the compiler failed.

COMPILE TIMES
Group Number		A	B	C	D	E	F	G	H
Ackermann	base opt-lir opt-backend	0.81 1.03 n/a	0.72 n/a n/a	0.61 0.72 0.77	3.48 6.65 4.47	0.58 0.61 n/a	0.61 0.71 0.88	0.68 0.83 0.98	n/a n/a 0.70
Constant	base opt-lir opt-backend	5.42 1.77 1:55.81	1.40 n/a n/a	1.02 1.22 1.40	n/a n/a n/a	2.00 2.13 n/a	0.93 4.11 16.80	6.41 1.71 30.61	0.84 2.86 n/a
DnaAlign	base opt-lir opt-backend	n/a n/a n/a	n/a n/a n/a	0.88 n/a n/a	8.42 n/a 22.51	0.84 n/a n/a	0.87 n/a 50.47	1.24 4.30 8.32	n/a n/a 3.61
Heapsort	base opt-lir opt-backend	0.86 n/a n/a	n/a n/a n/a	0.99 0.99 1.03	4.19 n/a 6.25	0.68 0.83 n/a	0.72 n/a n/a	0.85 1.39 1.49	0.73 n/a 1.27
Matrix	base opt-lir opt-backend	1.53 n/a n/a	0.94 n/a n/a	0.90 1.21 1.31	5.54 1:18.68 9.91	0.74 1.00 n/a	0.78 n/a n/a	0.94 2.10 4.15	0.77 n/a 2.05
MethCall	base opt-lir opt-backend	0.79 n/a n/a	n/a n/a n/a	n/a n/a n/a	3.53 6.55 4.71	n/a n/a n/a	0.67 1.01 n/a	n/a n/a n/a	0.68 n/a 1.09
Pi	base opt-lir opt-backend	0.99 n/a n/a	n/a n/a n/a	0.78 0.96 1.00	3.87 11.45 5.49	0.68 0.80 n/a	0.67 n/a n/a	0.80 1.92 1.79	0.73 n/a 1.16
Primes	base opt-lir opt-backend	n/a n/a n/a	n/a n/a n/a	0.89 1.35 1.31	8.37 37.87 13.63	n/a n/a n/a	0.88 n/a n/a	1.16 2.43 2.73	n/a n/a n/a
TcpRouting	base opt-lir opt-backend	n/a n/a n/a	n/a n/a n/a	n/a n/a n/a	12.67 n/a 56.73	n/a n/a n/a	0.99 n/a n/a	n/a n/a n/a	n/a n/a n/a
Average Compile Time (max time excluded)		1.65	1.02	0.99	11.81	0.87	1.18	2.31	1.23

The table below shows the complete running times (in seconds) for benchmark programs submitted by several groups. Compilers were run with and without optimizations. The entry "base" shows the result when all optimizations were turned off; and "opt" shows the best result for the three optimized runs (-opt, -opt-backend, and both). If all optimized runs failed for the same reason, that is shown in the entry; an "err" entry shows that they all failed, but for different reasons.

RUNNING TIMES: Base and Optimized Compilers
Benchmark		A	B	C	D	E	F	G	H
BigNum	base opt	1:09.58 err	asm comp	53.95 53.82	1:59.15 20.06	comp comp	1:22.21 1:22.41	1:03.86 err	asm err
Graph	base opt	comp comp	comp comp	10.15 err	23.33 8.17	res res	13.15 13.14	14.22 8.46	asm err
ICQuine	base opt	0.05 err	exc comp	0.06 res	0.05 0.05	0.04 0.04	0.06 0.05	0.05 0.04	0.05 0.05
Queens	base opt	7.55 err	exc comp	5.84 5.77	11.76 5.00	9.61 8.38	6.20 err	7.02 5.55	7.43 err
Sorting	base opt	3.75 err	exc comp	1.06 res	5.62 3.52	2.52 2.53	1.28 err	1.26 0.86	1.50 0.91