Re: GNAT compiler switches and optimization

[Jeffrey Creem <jeff@thecreems.com>]

Dr. Adrian Wrigley wrote:
> On Mon, 23 Oct 2006 21:52:59 +0200, Wiljan Derks wrote:
> 
> 
>>>Jeffrey R. Carter wrote:
>>>I looked at the gcc FORTRAN matmul. Unless there some additional trickery 
>>>going on behind the scenes, it is not anything magical. It looks like a 
>>>matmul implemented in C with manual array subscripting logic (i.e. uses a 
>>>single dimensional array overlay)..
>>
>>When going for a faster algorithm this might be usefull information.
>>Notice that this matmul uses an O(n^3) algorithm and it is possible to do 
>>this faster.
>>I am not sure, but maybe O(n^2 log(n)) is reachable, which is much faster.
>>It is easy to see that from the loops that the basic multiplications are 
>>done n times for the same pairs of numbers.
> 
> 
> I know you're quite correct that there is a faster algorithm for
> large n.  But looking at the loops, I don't see where the same
> number pairs are multiplied at different points in the calculation.
> Doesn't A(1,1)*B(1,1) only appear in C(1,1)?  Where else?
> 
> 
>>In a similar way, the same additions are done multiple times.
>>That means that there is real potential to improve things.
> 
> 
> Aren't they only the same additions if the same products are summed?
> 
> I may be being particularly stupid today, but if the redundancy
> is obvious from the loops, can you help me see where!  Thanks.
> --
> Adrian
> 

I have not looked at algorithms in this area in a few years but I do 
recall that you need very very large N before any of them start being 
worthwhile.

There are some speedups possibly that stay N**3 but optimize fetches and 
stores for cache performance and do hand vectorization of portions of 
the inner loop that can achieve speedup.

I would guess that even the library level matmul (which still has the 
best overall time) could be made about 2x faster on a recent intel 
platform with those changes.


Back to the original discussion, there are quite a few interesting 
things going on.

1) I have confirmed what another poster wrote that 4.2.0 is 
substantially slower than 4.0.3 on the original Ada example (thus, this 
performance is a regression)
2) Small changes to the original code that still meet the original 
structure and intent of the original code can move the run time up and 
down by at least 50%
3) The two task based version of the code is running more than 2x faster 
than the single task version on a 2 processor machine. Some of this is 
from the two tasks but looking at the assembly, another portion of it is 
  related to #2 above in that the re-arrangement of the math allows the 
compiler to get less brain dead.


If I get a chance tonight, I'll post some update results and analysis of 
the generated code.