Measuring gcc optimizations: are they well balanced?

[root at jacob dot remcomp dot fr (root)]

Dear friends:

We recently discussed a bug in the gcc code generation. What left me wondering
was that intuitively, it looked like the "optimizations" done by gcc, (where
the bug was) were suspect, in the sense that it looked like slower code than
the straightforward code generated by lcc-win32.

So, I decided to measure the speed of the generated code, to see if it was
really faster.

Methods:
-------
I changed the size of the table from 8 to 100.000 elements, to make the results
stand out. I made a test program that called the generated code 10.000 times,
making the generated test program go to more than 10 seconds, what makes the
measurements reliable.

Context:
-------
The C code is
	i=0
	while (i < TOP-1)
		table[i] = table[i+1];
gcc transforms this into
	i=1;
	while (i <= TOP-1)
		table[i-1] = table[i];

I pasted into the test procedure "gcc", the code generated by gcc.
I pasted into the test procedure "lcc", the code generated by lcc-win32.
I wrote a hand optimized assembly procedure called "optim" to see what would
be the limit of optimization even with the best compiler around.
I include the source for the assembly procedures and the corresponding test
program in the notes attached to this message.

Results:
--------
lcc: 12.9 seconds
gcc: 20.0 seconds
optimized assembly: 12.9 seconds

This means that in this "optimization", gcc's optimizer is SLOWING DOWN THE
GENERATED CODE BY ALMOST 50%!!!!

Intrigued by this result, I started measuring the overall efficiency of gcc's
optimizer. I compiled the source code of egcs-2.7.1 with differnet compilers
and with gcc.

Methods:
--------
The source of egcs-2.7.1 (approximately 1-12 MB of C) was compiled with the 
current version of gcc under windows: 2.95.2. 

To measure the speed of the resulting compiler the same file
was presented to gcc1: a preprocessed file of approx 300K where the is a HUGE
case statement that takes the compiler a long time to figure out so that the
measurements are significative. The results of the first run were discarded
to eliminate cache effects.


Results:
-------
Gcc: no optimizations	15.662 seconds
Gcc -O1                 12.548
Gcc -O2                 12.347
Gcc -O9                 12.217

lcc-win32 -O            13.619
MSVC++ 4.2 -Ox          11.526
Intel icl -Ox           12.107


What is obvious here is:
	1) The difference between gcc fully optimized and lcc-win32 (the slowest
           compiler of all) is approx 10%.
	2) The difference between gcc -O1 and gcc -O9 is approx 1% only!

This confirms my suspicion that the poor results of gcc's optimizer are due
to many optimizations SLOWING DOWN THE CODE INSTEAD OF IMPROVING IT!!!

Analysis:
---------
many people have worked with the source code of gcc. Most of them, will want 
to be remembered for what they added to it, rather for what they erased from it.
The consequence is that the compiler has grown without anyone doing the obviously
needed job of erasing bad optimizations, cleaning up the code, SIMPLIFYING IT,
and looking that the additions really improve the code.

Now the compiler has grown so complex that the maintainers are very afraid of
taking anything out of it for fear of introducing new bugs. This makes the
problem even worse: additions continue to go in, and nobody ever takes a
single line out...

I present this thesis here for discussion.

thanks for your time.


NOTES:
-----
Here is the code of the  assembler procedures "lcc" "gcc" and "optim" as 
described above
-----------------------------------------------------------------tgcc.s
	.text
	.globl	lcc
lcc:
	pushl	%ebp
	movl	%esp,%ebp
	pushl	%ebx
	pushl	%esi
	pushl	%edi
OuterLoop:
	xorl	%edi,%edi
_$10:
	movl	_Table+4(,%edi,4),%ebx
	movl	%ebx,_Table(,%edi,4)
	incl	%edi
	cmpl	$99999,%edi
	jl	_$10
	decl	counter
	ja	OuterLoop
	xor	%eax,%eax
	popl	%edi
	popl	%esi
	popl	%ebx
	leave
	ret
	.align	4
	.globl	gcc
gcc:
        pushl   %ebp
        movl    %esp,%ebp
        pushl   %ebx
        pushl   %esi
        pushl   %edi
OuterLoopGcc:
        xorl %ecx,%ecx
        movl $_Table,%esi
L10:
        leal 1(%ecx),%edx
        leal 0(,%edx,4),%ebx
        movl (%ebx,%esi),%eax
        movl %eax,(%esi,%ecx,4)
        movl %edx,%ecx
        cmpl $100000,%ecx
        jle L10
	decl counter
	ja   OuterLoopGcc
        xor     %eax,%eax
        popl    %edi
        popl    %esi
        popl    %ebx
        leave
        ret
	.align 4
	.globl optim
optim:
	movl %esi,%eax
	movl %edi,%edx
OuterLoopOptim:
	movl $99999,%ecx
	movl $_Table,%edi
	movl %edi,%esi
	addl $4,%esi
	rep
	movsl
	decl counter
	ja OuterLoopOptim
	movl %eax,%esi
	movl %edx,%edi
	ret

	.extern	Table
	.extern counter
--------------------------------------------------------------end of tgcc.s
Here is the test file test.c
#include <stdio.h>
#include <time.h>
char Table[1000000];
int counter;
int main()
{
        int start,end;
        double duration;

        counter = 10000;
        start = clock();
        lcc();
        end = clock();
        duration = (double)(end - start) / CLOCKS_PER_SEC;
        printf( "lcc: %2.1f seconds\n", duration );
        counter = 10000;
        start = clock();
        gcc();
        end = clock();
        duration = (double)(end - start) / CLOCKS_PER_SEC;
        printf( "gcc: %2.1f seconds\n", duration );
        counter = 10000;
        start = clock();
        optim();
        end = clock();
        duration = (double)(end - start) / CLOCKS_PER_SEC;
    printf( "optimized assembly: %2.1f seconds\n", duration );
}
----------------------------------------------------------------------

-- 
Jacob Navia	Logiciels/Informatique
41 rue Maurice Ravel			Tel 01 48.23.51.44
93430 Villetaneuse 			Fax 01 48.23.95.39
France
-- 
Jacob Navia	Logiciels/Informatique
41 rue Maurice Ravel			Tel 01 48.23.51.44
93430 Villetaneuse 			Fax 01 48.23.95.39
France