Code optimization - temporaries in the scalarizer

[THOMAS Paul Richard 169137]

This discussion of the equivalence problem reminded me of a puzzle that I
had about gfortran's performance relative to commercial compilers in respect
of Polyhedron's TEST_FPU.F90.

Baseline(test_fpu.f90 out of the box):

gfortran 20050903 (code uses equivalences) -fmax-stack-var-size=1000000 -O2

  Benchmark running, hopefully as only ACTIVE task
Test1 - Gauss 2000 (101x101) inverts 34.6 sec  Err= 0.000000000000002
Test2 - Crout 2000 (101x101) inverts  8.4 sec  Err= 0.000000000000001
Test3 - Crout  2 (1001x1001) inverts 11.0 sec  Err= 0.000000000000001
Test4 - Lapack 2 (1001x1001) inverts  8.1 sec  Err= 0.000000000000273
                             total = 62.1 sec

Digital DF6.0 using /fast

  Benchmark running, hopefully as only ACTIVE task
Test1 - Gauss 2000 (101x101) inverts  5.1 sec  Err= 0.000000000000003
Test2 - Crout 2000 (101x101) inverts  5.4 sec  Err= 0.000000000000012
Test3 - Crout  2 (1001x1001) inverts 10.6 sec  Err= 0.000000000000063
Test4 - Lapack 2 (1001x1001) inverts  7.5 sec  Err= 0.000000000000297
                             total = 28.6 sec

gfortran is doing OK but for Test1, where there is a factor of nearly 7
between them.

The offending lines in the source are:

lines 115-120

   temp = b(:,k)
   DO j = 1, n
      c = b(k,j)*d
      b(:,j) = b(:,j)-temp*c
      b(k,j) = c
   END DO

Repeating these nearly doubles the execution time of Test1.

Modifying the code to:

   zb = b                           ! A copy of b..
   temp = b(:,k)
   DO j = 1, n
      c = b(k,j)*d
      b(:,j) = zb(:,j)-temp*c       ! ..to be used here.
      b(k,j) = c
   END DO

Test1 - Gauss 2000 (101x101) inverts 12.0 sec  Err= 0.000000000000003
Test2 - Crout 2000 (101x101) inverts  8.4 sec  Err= 0.000000000000001
Test3 - Crout  2 (1001x1001) inverts 11.0 sec  Err= 0.000000000000001
Test4 - Lapack 2 (1001x1001) inverts  8.3 sec  Err= 0.000000000000273
                             total = 39.7 sec

which gains us nearly a factor of three and looks much more respectable.

The reason is evident from the snippets of code in the attached file:

This bit of code is converted into (loosely):

   temp = b(:,k)
   DO j = 1, n
      c = b(k,j)*d
      allocate (atmp6(size(b,1)))
      atmp6(:) = b(:,j)-temp*c
      b(:,j) = atmp6(:)
      deallocate(atmp6)
      b(k,j) = c
   END DO

If I reproduce this with an already allocated temporary, the time for Test1
drops to 11.6s.  It seems to me that it is the repeated calls to
_gfc_internal_malloc and _gfc_internal_free that are responsible for 23s of
execution time in the original version of the test. This is confirmed by
making this previous explicitly so, whereupon the execution time for Test1
goes up to 35.7s.

Finally, the best performance of all is obtained if the vector expression is
made F77-like

   temp = b(:,k)
   DO j = 1, n
      c = b(k,j)*d
      do p = 1, n
        b(p,j) = b(p,j)-temp(p)*c
      end do
      b(k,j) = c
   END DO

whereupon gfortran turns in a very healthy 6.7s.

My conclusion of all this is that there is some room for some optimization
of the scalarizer (by having gfc_conv_resolve_dependencies recognise that
this is an element by element replacement?). 

Paul T



-------------- next part --------------
A non-text attachment was scrubbed...
Name: gaus_code.c
Type: application/octet-stream
Size: 5364 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/fortran/attachments/20051018/6f4b23d7/attachment.obj>