RFC Exploratory Patch - Significant performance improvement

[Jerry DeLisle]

On 12/10/2009 03:48 AM, Richard Guenther wrote:
> On Thu, Dec 10, 2009 at 6:14 AM, Jerry DeLisle<jvdelisle@verizon.net>  wrote:
>> Hi all,
>>
>> I submit the attached patch for review and comment.
>>
>> With this patch, the test case in PR32489, fft257.f90 (attached) compiles in
>> about 2 to 3 seconds.  Without the patch, I am unable to compile this test
>> case without running out of memory and going into endless swapping.  I
>> suppose it is possible that if I wait long enough it may complete, but my
>> system starts to go unresponsive so I aborted the compile after about 5
>> minutes. ( I have 4 Gbyte system. )
>>
>> Regardless, the patch improves on this with about a thousand fold
>> improvement. Admittedly, its a rare test case, but perhaps this will help
>> others with real world applications that are compiling slowly.
>>
>> I have regression tested this with no failures. The tests for NULL in expr.c
>> I added to avoid segfaults with string_compare_3.f90.  I don't like that
>> fix, but it works.  I suspect we can further enhance the new function
>> gfc_is_expandable_expr in resolve.c to work around this.
>>
>> I also have successfully run Polyhedron 2005 tests.  I get one failure with
>> aermod which I thinks existed before the patch.
>>
>> The patch includes my previous patch for PR20923 since it is in my tree and
>> I don't want to try the rest of the patch without it.
>>
>> I invite you to explore this patch, not only to identify any other holes,
>> but also to explore the implications of what this is doing.  Are the
>> front-end results better for the middle end folks?  Do we get any better run
>> time performance or only compile time improvement?  Are there other bugs
>> lurking here and/or is the concept flawed?
>
> Can you explain what the differences will be to the middle-end?
>

Well, my question regarding the middle-end is partly rhetorical.

I ran the test case last night without the patch and this morning after 488 
minutes, compilation is not complete.

The difference is the front-end (with patch) does not expand this:

h1 = (/(sum((/(exp(-2*pi*(0,1)*mod(k*L,N)/N)*h2(L),L=0,N-1)/)),k=0,N-1)/)

into a rather large number of complex expressions, setting the array values 
element by element:

                           (*(complex(kind=8)[257] *) atmp.670.data)[0] = 
__builtin_cexp (((COMPLEX_EXPR <pi * 2.0e+0, 0.0> * __complex__ (0.0, 1.0e+0)) * 
__complex__ (0.0, 0.0)) / __complex__ (-2.57e+2, -0.0)) * h2[0];
                           (*(complex(kind=8)[257] *) atmp.670.data)[1] = 
__builtin_cexp (((COMPLEX_EXPR <pi * 2.0e+0, 0.0> * __complex__ (0.0, 1.0e+0)) * 
__complex__ (1.33e+2, 0.0)) / __complex__ (-2.57e+2, -0.0)) * h2[1];
                           (*(complex(kind=8)[257] *) atmp.670.data)[2] =
.
.
.

With the patch, the front-end generates a series of loops to do the same thing. 
  It makes sense to create the loops rather then the expansion.  Why the middle 
end does not handle the expanded case well, I cannot answer.

Regards,

Jerry