CS 412/413 Project Presentation Results

CS 412/413
Introduction to Compilers
Spring 2003

Project Presentation Results
Main Benchmarks

(see also Benchmarks Submitted by Groups)

Here is a short description of the benchmarks used:

BENCHMARKS
Benchmark	Lines	Description
Bignum	205	Arithmetic on arbitrary precision integers
Hash	166	Create and store elements in a hash table
Knn	493	Run a k-nearest neighbor machine learning algorithm
Listsort	207	Sort a list in-place using quicksort, with base case insertion sort
Loops	99	Deeply nested loops with break and continue statements
Objects	219	Test object inheritance and polymorphism
RSA	128	32-bit RSA cryptography and brute-force cryptanalysis
Strassen	270	Strassen matrix multiplication with iterative base case
Stringsearch	177	Boyer-Moore string search 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 the Pentium machines in the CSUG lab, under the Cygwin environment.
The first table shows the running times (in seconds) for the generated executables files. For each benchmark, the compilers were tested three configurations: without optimizations (base), with register allocation (regalloc), and with all optimizations turned on (optimized). Programs were forced to terminate after a timeout period of 100 seconds. If the compilation or the execution failed in one configuration, the next configurations were not tested. In case of error, the corresponding entry shows the reason why the program failed:

ctime - compiler timeout exceeded
comp - compiler failed to generate code
asm - incorrect generated assembly
time - progam timeout exceeded
res - incorrect result
exc - tun-time exception

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
Group		A	B	C	D	E	F	G	H	I	J	Best
Bignum	base regalloc opt	0.21 res -	1.18 exc -	asm - -	0.25 0.24 res	0.26 0.28 res	0.21 0.20 0.21	exc - -	0.21 0.22 0.21	exc - -	0.21 0.19 0.20	0.19
Hash	base regalloc opt	0.77 0.70 1.02	0.79 0.48 0.50	comp - -	0.85 res -	0.72 0.47 0.53	0.99 exc -	0.71 0.72 ctime	1.42 0.74 0.59	res - -	time time time	0.47
Knn	base regalloc opt	comp - -	ctime - -	asm - -	2.41 1.08 1.08	1.36 0.72 comp	2.63 0.95 0.80	1.51 1.44 1.47	res - -	exc - -	res - -	0.72
Listsort	base regalloc opt	time time time	1.14 0.97 0.97	comp - -	comp - -	time time res	time res -	time time time	2.05 1.16 time	time asm -	time time res	0.97
Loops	base regalloc opt	1.05 1.02 res	1.25 1.28 0.95	res - -	1.70 1.27 1.25	0.86 0.84 res	1.05 0.79 0.64	0.92 0.95 0.97	1.00 1.01 0.95	1.31 1.32 1.82	1.19 1.21 1.22	0.64
Objects	base regalloc opt	9.75 8.80 8.59	res - -	asm - -	res - -	res - -	10.77 res -	10.57 10.73 11.97	asm - -	23.47 asm -	24.19 9.62 9.60	8.59
RSA	base regalloc opt	9.41 7.45 5.88	res - -	asm - -	11.92 res -	10.09 6.89 res	9.56 7.48 exc	11.59 11.53 11.47	res - -	res - -	res - -	5.88
Strassen	base regalloc opt	1.66 1.43 1.50	1.84 0.70 1.05	res - -	2.77 2.55 2.44	1.29 0.72 0.69	1.69 1.37 1.08	2.31 2.35 2.31	9.76 1.99 1.95	res - -	5.06 1.27 1.27	0.69
Stringsearch	base regalloc opt	0.17 0.21 0.19	0.20 0.23 0.23	comp - -	0.20 0.22 0.22	0.21 0.24 0.22	0.27 0.21 0.24	0.19 0.21 exc	res - -	asm - -	0.18 0.22 0.21	0.17
Tests Passed		7	6	0	7	7	8	7	5	2	5
Overall Performance Factor		1.32	1.98	-	1.89	1.16	1.32	1.80	1.57	2.39	1.38

The second table shows the compile times (in seconds). Again, each compiler was tested without optimizations (base), with register allocation (regalloc), and with all optimizations turned on (opt). Compilers were also forced to terminate after a timeout period of 100 seconds. 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	I	J	Best
Bignum	base regalloc opt	5.54 5.70 -	9.60 15.43 -	asm - -	9.28 8.37 9.70	5.70 4.85 5.83	3.80 4.84 5.29	7.23 - -	10.42 13.12 4.41	6.50 - -	9.52 10.47 10.38	3.80
												4.41
Hash	base regalloc opt	5.44 4.59 5.55	7.48 7.83 8.22	comp - -	7.99 7.63 -	3.50 5.42 7.10	3.66 4.12 -	4.39 4.53 ctime	9.03 8.54 10.22	6.53 - -	5.24 6.32 6.17	3.50
												5.55
Knn	base regalloc opt	comp - -	ctime - -	asm - -	8.91 23.02 16.09	6.45 10.92 ctime	4.56 5.81 7.14	8.70 8.38 10.87	32.30 - -	9.33 - -	26.22 - -	4.56
												7.14
Listsort	base regalloc opt	4.58 4.97 5.63	8.40 8.63 8.34	comp - -	comp - -	9.79 5.20 5.14	3.58 4.88 -	4.70 4.63 6.18	9.88 12.14 12.70	5.77 asm -	5.10 6.41 7.53	3.58
												5.14
Loops	base regalloc opt	4.32 4.49 5.96	8.62 11.95 16.46	6.48 - -	6.76 7.11 8.64	3.79 3.79 6.57	3.79 4.43 5.88	4.60 4.27 5.43	7.66 10.33 5.47	5.29 6.28 5.13	4.93 10.80 5.05	3.79
												5.05
Objects	base regalloc opt	4.04 4.96 6.17	8.35 - -	asm - -	7.65 - -	3.74 - -	3.37 4.76 -	4.81 5.00 6.15	asm - -	5.19 asm -	5.58 11.69 4.97	3.37
												4.97
RSA	base regalloc opt	3.97 4.09 5.09	8.87 - -	asm - -	8.54 8.61 -	5.85 4.37 5.27	3.56 4.21 5.21	4.70 4.43 5.79	8.47 - -	5.33 - -	4.96 - -	3.56
												5.09
Strassen	base regalloc opt	4.98 4.76 5.87	10.01 49.09 49.11	11.02 - -	7.61 9.44 10.16	3.97 5.26 5.95	3.68 5.18 6.15	5.64 5.48 6.31	14.64 75.47 73.11	5.48 - -	5.29 10.75 11.05	3.68
												5.87
Stringsearch	base regalloc opt	4.20 4.63 6.52	8.76 8.35 8.29	comp - -	6.93 7.60 8.43	3.95 4.13 5.39	4.00 5.16 5.03	4.70 4.81 5.64	9.21 - -	asm - -	5.19 7.93 5.26	3.95
												5.03
Average Compile Time		5.05	13.78	8.75	9.42	5.50	4.67	5.72	18.17	6.08	8.12