[Bug fortran/24519] New: gfortran slow because of incomplete dependency checking

[Bug fortran/24519] New: gfortran slow because of incomplete dependency checking

[paul dot richard dot thomas at cea dot fr]

This PR is concerned with 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 -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 dumping the code.

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?).


-- 
           Summary: gfortran slow because of incomplete dependency checking
           Product: gcc
           Version: 4.1.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: fortran
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: paul dot richard dot thomas at cea dot fr


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519

[Bug fortran/24519] gfortran slow because of incomplete dependency checking

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2005-10-25 13:47 -------
Confirmed, I saw this while working on another bug.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |pinskia at gcc dot gnu dot
                   |                            |org
         AssignedTo|unassigned at gcc dot gnu   |pinskia at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
           Keywords|                            |missed-optimization
   Last reconfirmed|0000-00-00 00:00:00         |2005-10-25 13:47:31
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519

[Bug fortran/24519] gfortran slow because of incomplete dependency checking

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2005-10-25 13:55 -------
Woops wrong button.

One more testcase which looks like will show up in SPEC 2k5:
   temp = #####
   c = #####
   DO j = 1, n
      b(array) = b(array)-temp*c
   END DO


We have a couple of temps here, two for array and then one for the assignment.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|pinskia at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519

[Bug fortran/24519] gfortran slow because of incomplete dependency checking

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2005-10-25 18:14 -------
Another issue is that we should be able to reverse the loop too, see PR 24524
for a testcase for that (which I got the idea from Tobias in the email about my
patch which fixes a related bug to temporary arrays).


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519

[Bug fortran/24519] gfortran slow because of incomplete dependency checking

[pault at gcc dot gnu dot org]

------- Comment #4 from pault at gcc dot gnu dot org  2006-02-18 17:52 -------
A patch is on its way for the immediate problem; however, the more complicated
cases of loop reversal and of dependecy involving expressions will have to
wait.

Paul


-- 

pault at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pault at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519

[Bug fortran/24519] gfortran slow because of incomplete dependency checking

[pault at gcc dot gnu dot org]

------- Comment #5 from pault at gcc dot gnu dot org  2006-02-24 10:51 -------
Subject: Bug 24519

Author: pault
Date: Fri Feb 24 10:51:42 2006
New Revision: 111416

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=111416
Log:
2006-02-24  Paul Thomas  <pault@gcc.gnu.org>

        PR fortran/24519
        * dependency.c (gfc_is_same_range): Correct typo.
        (gfc_check_section_vs_section): Call gfc_is_same_range.

        PR fortran/25395
        * trans-common.c (add_equivalences): Add a new flag that is set when
        an equivalence is seen that prevents more from being reset until the
        start of a new traversal of the list, thus ensuring completion of
        all the equivalences.

2006-02-24  Paul Thomas  <pault@gcc.gnu.org>

        PR fortran/24519
        * gfortran.dg/dependency_3.f90: New test.
        * gfortran.fortran-torture/execute/vect-3.f90: Remove two of the
        XFAILs.

        PR fortran/25395
        * gfortran.dg/equiv_6.f90: New test.


Added:
    trunk/gcc/testsuite/gfortran.dg/dependency_3.f90
    trunk/gcc/testsuite/gfortran.dg/equiv_6.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/dependency.c
    trunk/gcc/fortran/trans-common.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gfortran.dg/vect/vect-3.f90


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519

[Bug fortran/24519] gfortran slow because of incomplete dependency checking

[pault at gcc dot gnu dot org]

------- Comment #6 from pault at gcc dot gnu dot org  2006-02-24 10:53 -------
Fixed on trunk.

As soon as 4.1 is reopened, it will be fixed there too.

Paul


-- 

pault at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519

[Bug fortran/24519] gfortran slow because of incomplete dependency checking

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |4.2.0


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519

[Bug fortran/24519] gfortran slow because of incomplete dependency checking

[pault at gcc dot gnu dot org]

------- Comment #7 from pault at gcc dot gnu dot org  2006-03-07 00:06 -------
Subject: Bug 24519

Author: pault
Date: Tue Mar  7 00:06:37 2006
New Revision: 111796

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=111796
Log:
2006-03-07  Paul Thomas  <pault@gcc.gnu.org>

        PR fortran/26107
        * resolve.c (resolve_function): Add name after test for pureness.

        * iresolve.c (gfc_resolve_dot_product):  Remove any difference in
        treatment of logical types.
        * trans-intrinsic.c (gfc_conv_intrinsic_dot_product):  New function. 

        PR fortran/26393
        * trans-decl.c (gfc_get_symbol_decl): Extend condition that symbols
        must be referenced to include unreferenced symbols in an interface
        body. 

        PR fortran/20938
        * trans-array.c (gfc_conv_resolve_dependencies): Add call to
        gfc_are_equivalenced_arrays.
        * symbol.c (gfc_free_equiv_infos, gfc_free_equiv_lists): New
        functions. (gfc_free_namespace): Call them.
        * trans-common.c (copy_equiv_list_to_ns): New function.
        (add_equivalences): Call it.
        * gfortran.h: Add equiv_lists to gfc_namespace and define
        gfc_equiv_list and gfc_equiv_info.
        * dependency.c (gfc_are_equivalenced_arrays): New function.
        (gfc_check_dependency): Call it.
        * dependency.h: Prototype for gfc_are_equivalenced_arrays.

        PR fortran/24519
        * dependency.c (gfc_is_same_range): Correct typo.
        (gfc_check_section_vs_section): Call gfc_is_same_range.

        PR fortran/25395
        * trans-common.c (add_equivalences): Add a new flag that is set when
        an equivalence is seen that prevents more from being reset until the
        start of a new traversal of the list, thus ensuring completion of
        all the equivalences.

        PR fortran/25054
        * resolve.c (is_non_constant_shape_array): New function.
        (resolve_fl_variable): Remove code for the new function and call it.
        (resolve_fl_namelist): New function.  Add test for namelist array
        with non-constant shape, using is_non_constant_shape_array.
        (resolve_symbol): Remove code for resolve_fl_namelist and call it.

        PR fortran/25089
        * match.c (match_namelist): Increment the refs field of an accepted
        namelist object symbol.
        * resolve.c (resolve_fl_namelist): Test namelist objects for a conflict
        with contained or module procedures.

        PR fortran/24557
        * trans-expr.c (gfc_add_interface_mapping): Use the actual argument
        for character(*) arrays, rather than casting to the type and kind
        parameters of the formal argument.

2006-03-07  Paul Thomas  <pault@gcc.gnu.org>

        PR fortran/26107
        * resolve.c (resolve_function): Add name after test for pureness.

        * gfortran.dg/logical_dot_product.f90: New test. 

        PR fortran/26393
        * gfortran.dg/used_interface_ref.f90: New test.

        PR fortran/20938
        * gfortran.dg/dependency_2.f90: New test.
        * gfortran.fortran-torture/execute/where17.f90: New test.
        * gfortran.fortran-torture/execute/where18.f90: New test.
        * gfortran.fortran-torture/execute/where19.f90: New test.
        * gfortran.fortran-torture/execute/where20.f90: New test.

        PR fortran/24519
        * gfortran.dg/dependency_3.f90: New test.
        * gfortran.fortran-torture/execute/vect-3.f90: Remove two of the
        XFAILs.

        PR fortran/25395
        * gfortran.dg/equiv_6.f90: New test.

        PR fortran/25054
        * gfortran.dg/namelist_5.f90: New test.

        PR fortran/25089
        * gfortran.dg/namelist_4.f90: New test.

        PR fortran/24557
        * gfortran.dg/assumed_charlen_needed_1.f90: New test.

Added:
   
branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/assumed_charlen_needed_1.f90
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/dependency_2.f90
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/dependency_3.f90
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/equiv_6.f90
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/logical_dot_product.f90
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/namelist_4.f90
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/namelist_5.f90
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/pure_dummy_length_1.f90
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/used_interface_ref.f90
   
branches/gcc-4_1-branch/gcc/testsuite/gfortran.fortran-torture/execute/where17.f90
   
branches/gcc-4_1-branch/gcc/testsuite/gfortran.fortran-torture/execute/where18.f90
   
branches/gcc-4_1-branch/gcc/testsuite/gfortran.fortran-torture/execute/where19.f90
   
branches/gcc-4_1-branch/gcc/testsuite/gfortran.fortran-torture/execute/where20.f90
Modified:
    branches/gcc-4_1-branch/MAINTAINERS
    branches/gcc-4_1-branch/gcc/fortran/ChangeLog
    branches/gcc-4_1-branch/gcc/fortran/dependency.c
    branches/gcc-4_1-branch/gcc/fortran/dependency.h
    branches/gcc-4_1-branch/gcc/fortran/dump-parse-tree.c
    branches/gcc-4_1-branch/gcc/fortran/gfortran.h
    branches/gcc-4_1-branch/gcc/fortran/iresolve.c
    branches/gcc-4_1-branch/gcc/fortran/match.c
    branches/gcc-4_1-branch/gcc/fortran/resolve.c
    branches/gcc-4_1-branch/gcc/fortran/symbol.c
    branches/gcc-4_1-branch/gcc/fortran/trans-array.c
    branches/gcc-4_1-branch/gcc/fortran/trans-common.c
    branches/gcc-4_1-branch/gcc/fortran/trans-decl.c
    branches/gcc-4_1-branch/gcc/fortran/trans-expr.c
    branches/gcc-4_1-branch/gcc/fortran/trans-intrinsic.c
    branches/gcc-4_1-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_1-branch/gcc/testsuite/gfortran.dg/vect/vect-3.f90


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519

[Bug fortran/24519] gfortran slow because of incomplete dependency checking

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.0                       |4.1.1


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=24519