[Bug fortran/97571] New: long parsing phase for simple array constructor

[Bug fortran/97571] New: long parsing phase for simple array constructor

[rimvydas.jas at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

            Bug ID: 97571
           Summary: long parsing phase for simple array constructor
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: fortran
          Assignee: unassigned at gcc dot gnu.org
          Reporter: rimvydas.jas at gmail dot com
  Target Milestone: ---

gcc version 11.0.0 20201025 (experimental) [master revision
d7ddd287c:9f8172cd7:47d13acbda9a5d8eb57ff169ba74857cd54108e4] (GCC)

x86_64-unknown-linux 

$ cat init.f90
subroutine bpr_init
implicit none
integer :: i
real :: tacos2( 0:35250)
tacos2 = acos( (/ (i, i=64000,99250) /) / 100000.0)
end subroutine bpr_init

$ gfortran -O1 -Wall -Wextra -c init.f90 -ftime-report
init.f90:4:24:

    4 | real :: tacos2( 0:35250)
      |                        1
Warning: Array 'tacos2' at (1) is larger than limit set by
'-fmax-stack-var-size=', moved from stack to static storage. This makes the
procedure unsafe when called recursively, or concurrently from multiple
threads. Consider using '-frecursive', or increase the '-fmax-stack-var-size='
limit, or change the code to use an ALLOCATABLE array. [-Wsurprising]

Time variable                                   usr           sys          wall
          GGC
 phase parsing                      :1923.03 (100%)   0.21 (100%)1923.67 (100%)
 7500k ( 97%)
 phase opt and generate             :   0.01 (  0%)   0.00 (  0%)   0.02 (  0%)
   69k (  1%)
 callgraph functions expansion      :   0.01 (  0%)   0.00 (  0%)   0.01 (  0%)
   48k (  1%)
 parser (global)                    :1923.02 (100%)   0.21 (100%)1923.67 (100%)
 7500k ( 97%)
 tree gimplify                      :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
 1752  (  0%)
 tree STMT verifier                 :   0.00 (  0%)   0.00 (  0%)   0.01 (  0%)
    0  (  0%)
 varconst                           :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
    0  (  0%)
 initialize rtl                     :   0.01 (  0%)   0.00 (  0%)   0.00 (  0%)
   12k (  0%)
 TOTAL                              :1923.04          0.21       1923.69       
 7756k
Extra diagnostic checks enabled; compiler may run slowly.
Configure with --enable-checking=release to disable checks.

Configuring with checking=release or different -O levels have no impact on time
taken, previous gfortran 10.2 did not exhibit such long parsing times.

[Bug fortran/97571] long parsing phase for simple array constructor

[anlauf at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

anlauf at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |anlauf at gcc dot gnu.org

--- Comment #1 from anlauf at gcc dot gnu.org ---
Looking at the dump-tree of a reduced case reveals that simplification
of the line with the ACOS of the array constructor causes the difference:

subroutine bpr_init
  implicit none
  integer :: i
  real :: tacos2(2)
  tacos2 = acos( (/ (i, i=1,size(tacos2)) /) / 2.0)
end subroutine bpr_init


11-master:

bpr_init ()
{
  integer(kind=4) i;
  real(kind=4) tacos2[2];

  {
    static real(kind=4) A.0[2] = {1.0471975803375244140625e+0, 0.0};

    (void) __builtin_memcpy ((void *) &tacos2, (void *) &A.0, 8);
  }
}


older versions:

bpr_init ()
{
  integer(kind=4) i;
  real(kind=4) tacos2[2];

  {
    static real(kind=4) A.0[2] = {5.0e-1, 1.0e+0};

    {
      integer(kind=8) S.1;

      S.1 = 0;
      while (1)
        {
          if (S.1 > 1) goto L.1;
          tacos2[S.1] = __builtin_acosf (A.0[S.1]);
          S.1 = S.1 + 1;
        }
      L.1:;
    }
  }
}


So the new compiler does compile-time simplification already at -O0, while
older versions maybe not.

[Bug fortran/97571] long parsing phase for simple array constructor

[dominiq at lps dot ens.fr]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

Dominique d'Humieres <dominiq at lps dot ens.fr> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
     Ever confirmed|0                           |1
             Status|UNCONFIRMED                 |WAITING
   Last reconfirmed|                            |2020-12-02
           Priority|P3                          |P4

--- Comment #2 from Dominique d'Humieres <dominiq at lps dot ens.fr> ---
> So the new compiler does compile-time simplification already at -O0,
> while older versions maybe not.

Is this expected?

[Bug fortran/97571] long parsing phase for simple array constructor

[anlauf at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

--- Comment #3 from anlauf at gcc dot gnu.org ---
(In reply to Dominique d'Humieres from comment #2)
> > So the new compiler does compile-time simplification already at -O0,
> > while older versions maybe not.
> 
> Is this expected?

Depends.  I'd expect constant expressions like this to be simplified.
There could be (artificial) limits when to give up.

The tree dump does not really give me the impression nor enough information to
know that this happens with previous version of the compiler at this stage.

[Bug fortran/97571] long parsing phase for simple array constructor

[dominiq at lps dot ens.fr]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

Dominique d'Humieres <dominiq at lps dot ens.fr> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |molah at ucar dot edu

--- Comment #4 from Dominique d'Humieres <dominiq at lps dot ens.fr> ---
*** Bug 100235 has been marked as a duplicate of this bug. ***

[Bug fortran/97571] long parsing phase for simple array constructor

[molah at ucar dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

--- Comment #5 from Mark J Olah <molah at ucar dot edu> ---
I reported this in bug #100235, where it was suggested this would be treated as
WONTFIX.  

It seems this bug is reporting on the same issue arising from rttov:
https://nwp-saf.eumetsat.int/site/software/rttov/

Whatever is happening inside the AST evaluation in this case is not only
extraordinarily inefficient, but also apparently exponential with the size of
the fixed array.  This can be demonstrated by adjusting N in the test case I
added to bug #100235.

IMHO, 2000sec is not a reasonable compile time for *any* code, especially
something this simple (and arguably correct code that is used in production
packages).  

A quick test shows I can compute ACOS of 10^8 elements in less than a second on
any reasonable hardware.  We are talking about only 32k elements here, which
should be trivial.

In any case is there a flag I can add to the compiler to disable this new
behavior?

[Bug fortran/97571] long parsing phase for simple array constructor

[anlauf at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

--- Comment #6 from anlauf at gcc dot gnu.org ---
(In reply to Mark J Olah from comment #5)
> Whatever is happening inside the AST evaluation in this case is not only
> extraordinarily inefficient, but also apparently exponential with the size
> of the fixed array.  This can be demonstrated by adjusting N in the test
> case I added to bug #100235.

You are asking for the evaluation of a constant expression, and the compiler
does it.

> A quick test shows I can compute ACOS of 10^8 elements in less than a second
> on any reasonable hardware.  We are talking about only 32k elements here,
> which should be trivial.

If you want run-time evaluation of acos, you get it when you write your code
this way.  If not, e.g. change it so that it looks to the compiler that one
of the bounds is non-constant.  The code in comment#0 e.g. could read:

subroutine bpr_init
  implicit none
  integer :: i
  real :: tacos2( 0:35250)
  integer :: n = 99250
  tacos2 = acos( (/ (i, i=64000,n) /) / 100000.0)
end subroutine bpr_init

You'll then get even more compact and probably efficient code than in older
versions of gfortran, because it will no longer generate the unused data
array as explained by Steve.

> In any case is there a flag I can add to the compiler to disable this new
> behavior?

Currently no.  The gfortran change was done to allow the r.h.s. expression to
evaluate at compile time so that it can be used e.g. in parameter statements,
which is required by the standard.

One could envision checking the l.h.s. and decide to not do the simplification
of the r.h.s. in case of assignments.  Somebody would need to implement that.

To me it looks like: doctor, it hurts when I do ...

As a workaround, see my suggestion above.

[Bug fortran/97571] long parsing phase for simple array constructor

[kargl at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

kargl at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kargl at gcc dot gnu.org

--- Comment #7 from kargl at gcc dot gnu.org ---
(In reply to Mark J Olah from comment #5)
>
> A quick test shows I can compute ACOS of 10^8 elements in less than a second
> on any reasonable hardware.  We are talking about only 32k elements here,
> which should be trivial.
> 

Without see your code for your quick test, I'll proffer that
you were doing floating point math with hardware FPU support.

gfortran's internal representation of an integer is a GMP
mpz_t type.  For a real type, gfortran uses an MPFR mpfr_t type.
Your array constructor [(i, i=0, i=100000)] creates an array
of 100001 gfc_expr nodes, which contain GMP types.  Each of
these are then converted to an mpfr_t type and divided by a
gfc_expr node containing an mpfr_t type for 100000.0, so that
you now have an array of 100001 gfc_expr nodes with mpfr_t entities.
Each of these mpfr_t entities is then used as an actual argument
to mpfr_acos() from the MPFR library.  IOW, gfortran is doing
floating point arithmetic with a software implementation, which
guarantees correctly rounded values (in round-to-nearest mode).

Yes, it is slow.  But, at least, you get the correct result.

[Bug fortran/97571] long parsing phase for simple array constructor

[jvdelisle at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

Jerry DeLisle <jvdelisle at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jvdelisle at gcc dot gnu.org

--- Comment #8 from Jerry DeLisle <jvdelisle at gcc dot gnu.org> ---
Is it technically possible to do this differently in the compiler? yes

Are there resources to actually do so? no

Are putting resouces into it worth it (cost/benefit)? no

Is there an easy work around? yes

solution: do the workaround.

subroutine bpr_init
  implicit none
  integer :: i
  real :: tacos2( 0:35250)
  do i=0,35250
    tacos2(i) = acos((i + 64000.0)/100000.0)
  end do
end subroutine bpr_init

[aside: I realize the example is a simplified/contrived example. Regardless it
is horrible software practices using hard coded un-named real constants, etc
etc etc.]

[Bug fortran/97571] long parsing phase for simple array constructor

[molah at ucar dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

--- Comment #9 from Mark J Olah <molah at ucar dot edu> ---
Thank you Karl and Jerry for the suggestions on transforming the code.  It is
not my own code, and I cannot modify it.  It is however correct Fortran code,
that currently builds fine with GCC 10.2.0, and all other Fortran compilers I
have access to.  I would like to be able to continue to compile this code with
modern GCC-10.3.0+, but that is not practically possible without resolving this
severe performance issue.

I have read the explanation of the code generation, but this fails to explain
why GCC is implementing an *exponential* algorithm to compute what should be a
*linear  complexity* operation.

Moreover, testing shows the expense cannot be a result of MPFR.  I can compute
32k acos() computations with MPFR to 53 bits of precision in about 3 sec.  Also
MPFR shows a perfectly linear scaling with N.

Therefore the remaining ~1920 sec of compilation time representing 99.8% of the
runtime must be spent doing something wasteful, and the exponential dependence
on N is a result of a poor internal algorithm that is implemented by GCC.  

I would expect a compiler must do a reasonable job to compile correct Fortran
code in a reasonable amount of time.  The response for reporting significant
algorithmic internal deficiencies of a compiler cannot be "change your code",
otherwise the solution of your users will have to be "change the compiler".

[Bug fortran/97571] long parsing phase for simple array constructor

[sgk at troutmask dot apl.washington.edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

--- Comment #10 from Steve Kargl <sgk at troutmask dot apl.washington.edu> ---
On Tue, Apr 27, 2021 at 06:03:16PM +0000, molah at ucar dot edu wrote:

> I would expect a compiler must do a reasonable job to compile correct Fortran
> code in a reasonable amount of time.  The response for reporting significant
> algorithmic internal deficiencies of a compiler cannot be "change your code",
> otherwise the solution of your users will have to be "change the compiler".

gfortran is mostly maintained by volunteers.  I started fixing
bugs 2 decades ago, because gfortran was the only Fortran compiler
available for FreeBSD.  I no longer contribute patches back to
gcc due to a few reasons.  gfortran could use a new volunteer
to step up.

[Bug fortran/97571] long parsing phase for simple array constructor

[molah at ucar dot edu]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

--- Comment #11 from Mark J Olah <molah at ucar dot edu> ---
(In reply to Steve Kargl from comment #10)

> gfortran is mostly maintained by volunteers.  I started fixing
> bugs 2 decades ago, because gfortran was the only Fortran compiler
> available for FreeBSD.  I no longer contribute patches back to
> gcc due to a few reasons.  gfortran could use a new volunteer
> to step up.

Steve, thanks for your years of effort.  I understand that all fixes are
community contributed.  If I knew how to fix this myself, I would.

I would be satisfied with acknowledgment that there is an issue, and it effects
the usability of the compiler for actual real-world use cases.

It also is a clear regression between versions, arising from a deliberate and
arguably inefficiently implemented change in the way the compiler is generating
the code.

A simple revision to previous behavior, or a flag to disable the new behavior
would be sufficient to enable the new compiler to continue to work with
existing codebases.

Also, on further timing analysis the behavior appears to be approximately
quadratic in N (not exponential), but with a big enough constant that it
becomes problematic at reasonable sizes of N.

[Bug fortran/97571] long parsing phase for simple array constructor

[anlauf at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

anlauf at gcc dot gnu.org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog

--- Comment #12 from anlauf at gcc dot gnu.org ---
You are throwing an elemental function on a array constructor.

Rewriting the constant expression as

  tacos2 = (/ (acos (i / 100000.0), i=64000,99250) /)

makes the simplifications much more efficient.

[Bug fortran/97571] long parsing phase for simple array constructor

[rimvydas.jas at gmail dot com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

--- Comment #13 from Rimvydas (RJ) <rimvydas.jas at gmail dot com> ---
I agree that it is preferred to rewrite such look up table initialization,
however it is not always possible due to licensing restrictions preventing
making local modifications to the source code provided.  From user perspective
user requested to create consecutive integer array constructor that should be
called to ACOS() intrinsic and not vise versa create real (possibly double or
even quad precision) array constructor containing acos() values.

Something like a runtime limit variable to prevent compile time hogging would
be acceptable provided if user would get warned under say -Wsurprising that
intrinsic evaluation on array constructor was skipped due to excessive use of
MPFR library function calls or was considered not beneficial.

[Bug fortran/97571] long parsing phase for simple array constructor

[anlauf at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=97571

--- Comment #14 from anlauf at gcc dot gnu.org ---
(In reply to Rimvydas (RJ) from comment #13)
> I agree that it is preferred to rewrite such look up table initialization,
> however it is not always possible due to licensing restrictions preventing
> making local modifications to the source code provided.

AFAICS there is no such restriction for RTTOV.

> Something like a runtime limit variable to prevent compile time hogging
> would be acceptable provided if user would get warned under say -Wsurprising
> that intrinsic evaluation on array constructor was skipped due to excessive
> use of MPFR library function calls or was considered not beneficial.

So far no patch has been developed and submitted for review.