Bug 20923 - gfortran slow for large array constructors
gfortran slow for large array constructors
Status: RESOLVED FIXED
Product: gcc
Classification: Unclassified
Component: fortran
4.1.0
: P2 minor
: ---
Assigned To: Not yet assigned to anyone
: compile-time-hog
: 31301 (view as bug list)
Depends on: 37577
Blocks:
  Show dependency treegraph
 
Reported: 2005-04-09 22:15 UTC by Andrew Pinski
Modified: 2010-01-14 03:04 UTC (History)
3 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed: 2005-12-30 19:39:09


Attachments
Preliminary patch (1.27 KB, patch)
2009-11-27 07:31 UTC, Jerry DeLisle
Details | Diff
Updated patch (1.20 KB, patch)
2009-11-28 01:46 UTC, Jerry DeLisle
Details | Diff
Third time is a charm (2.13 KB, patch)
2009-11-28 15:10 UTC, Jerry DeLisle
Details | Diff
Slightly modified charm (2.26 KB, patch)
2009-11-28 17:14 UTC, Jerry DeLisle
Details | Diff
Hopefully final patch (3.99 KB, patch)
2009-11-29 19:36 UTC, Jerry DeLisle
Details | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Andrew Pinski 2005-04-09 22:15:05 UTC
While I was looking for an ICE, I noticed that the following code causes gfortran to take a long time 
(almost a minute, this is without optimizations)


program sel
    implicit none
    integer,parameter              :: n=1000
    integer                        :: i,j
    real,dimension(n*n) :: vect
    vect(:) = (/ ((( (i+j+3)),i=1,n),j=1,n) /)
end
Comment 1 Tobias Schlüter 2005-05-19 17:41:53 UTC
Confirmed.  This is because the array constructor is expanded at compile-time. 
If the constructor were used in an initialization we would abort, IIRC.
Comment 2 Tobias Schlüter 2005-05-19 22:09:34 UTC
The time behavior is strictly linear BTW:
n = 100:
real    0m0.604s
user    0m0.485s
sys     0m0.021s
n = 1000:
real    1m0.860s
user    0m49.055s
sys     0m0.078s

(the array grows quadratically with n)

One thing that's interesting is that in the -fdump-parse-tree output the array
constructor is only expanded in the first case but not in the second, so it
looks like in the latter case we explicitly calculate the array and then throw
it away.
Comment 3 Tobias Schlüter 2005-05-19 22:14:14 UTC
ugh, it is quadratic, only the inner array constructor gets expanded. And this
is where the <= 100 restriction I alluded to above comes in.  For n = 100 the
relevant line from the -fdump-parse-tree output looks like:
      ASSIGN vect(:) __convert_i4_r4[[(((/ ((/ (+ (+ 1 j) 3) , (+ (+ 2 j) 3) ,
(+ (+ 3 j) 3) , (+ (+ 4 j) 3) , (+ (+ 5 j) 3) , (+ (+ 6 j) 3) , (+ (+ 7 j) 3) ,
(+ (+ 8 j) 3) , (+ (+ 9 j) 3) , (+ (+ 10 j) 3) , (+ (+ 11 j) 3) , (+ (+ 12 j)
3), (+ (+ 13 j) 3) , (+ (+ 14 j) 3) , (+ (+ 15 j) 3) , (+ (+ 16 j) 3) , (+ (+ 17
j) 3) , (+ (+ 18 j) 3) , (+ (+ 19 j) 3) , (+ (+ 20 j) 3) , (+ (+ 21 j) 3) , (+
(+ 22 j) 3) , (+ (+ 23 j) 3) , (+ (+ 24 j) 3) , (+ (+ 25 j) 3) , (+ (+ 26 j) 3)
,(+ (+ 27 j) 3) , (+ (+ 28 j) 3) , (+ (+ 29 j) 3) , (+ (+ 30 j) 3) , (+ (+ 31
j)3) , (+ (+ 32 j) 3) , (+ (+ 33 j) 3) , (+ (+ 34 j) 3) , (+ (+ 35 j) 3) , (+ (+
36 j) 3) , (+ (+ 37 j) 3) , (+ (+ 38 j) 3) , (+ (+ 39 j) 3) , (+ (+ 40 j) 3) ,
(+ (+ 41 j) 3) , (+ (+ 42 j) 3) , (+ (+ 43 j) 3) , (+ (+ 44 j) 3) , (+ (+ 45 j)
3) , (+ (+ 46 j) 3) , (+ (+ 47 j) 3) , (+ (+ 48 j) 3) , (+ (+ 49 j) 3) , (+ (+
50j) 3) , (+ (+ 51 j) 3) , (+ (+ 52 j) 3) , (+ (+ 53 j) 3) , (+ (+ 54 j) 3) , (+
(+ 55 j) 3) , (+ (+ 56 j) 3) , (+ (+ 57 j) 3) , (+ (+ 58 j) 3) , (+ (+ 59 j) 3)
, (+ (+ 60 j) 3) , (+ (+ 61 j) 3) , (+ (+ 62 j) 3) , (+ (+ 63 j) 3) , (+ (+ 64
j) 3) , (+ (+ 65 j) 3) , (+ (+ 66 j) 3) , (+ (+ 67 j) 3) , (+ (+ 68 j) 3) , (+
(+69 j) 3) , (+ (+ 70 j) 3) , (+ (+ 71 j) 3) , (+ (+ 72 j) 3) , (+ (+ 73 j) 3) ,
(+ (+ 74 j) 3) , (+ (+ 75 j) 3) , (+ (+ 76 j) 3) , (+ (+ 77 j) 3) , (+ (+ 78 j)
3) , (+ (+ 79 j) 3) , (+ (+ 80 j) 3) , (+ (+ 81 j) 3) , (+ (+ 82 j) 3) , (+ (+
83 j) 3) , (+ (+ 84 j) 3) , (+ (+ 85 j) 3) , (+ (+ 86 j) 3) , (+ (+ 87 j) 3) ,
(+(+ 88 j) 3) , (+ (+ 89 j) 3) , (+ (+ 90 j) 3) , (+ (+ 91 j) 3) , (+ (+ 92 j)
3), (+ (+ 93 j) 3) , (+ (+ 94 j) 3) , (+ (+ 95 j) 3) , (+ (+ 96 j) 3) , (+ (+ 97
j) 3) , (+ (+ 98 j) 3) , (+ (+ 99 j) 3) , (+ (+ 100 j) 3) /) j=1,100,1) /)))]]

while for n = 101 it loks like:
     ASSIGN vect(:) __convert_i4_r4[[(((/ ((/ ((/ (+ (+ i j) 3) /) i=1,101,1) /)
j=1,101,1) /)))]]

IOW the array constructor is not expanded any longer, but still the compilation
takes longer :-(
Comment 4 Tobias Schlüter 2005-05-19 22:19:30 UTC
One more thing I forgot to mention: for n = 100 the .original dump looks like this:
    int4 offset.1;
    struct array1_int4 atmp.0;

    atmp.0.dtype = 265;
    atmp.0.dim[0].stride = 1;
    atmp.0.dim[0].lbound = 0;
    atmp.0.dim[0].ubound = 9999;
    atmp.0.data = (int4[0:] *) _gfortran_internal_malloc (40000);
    atmp.0.offset = 0;
    offset.1 = 0;
    j = 1;
    while (1)
      {
        if (j > 100) goto L.1; else (void) 0;
        (*atmp.0.data)[offset.1] = j + 4;
        offset.1 = offset.1 + 1;
        (*atmp.0.data)[offset.1] = j + 5;
        offset.1 = offset.1 + 1;
        (*atmp.0.data)[offset.1] = j + 6;
        offset.1 = offset.1 + 1;
        (*atmp.0.data)[offset.1] = j + 7;
        ...
        offset.1 = offset.1 + 1;
        (*atmp.0.data)[offset.1] = j + 102;
        offset.1 = offset.1 + 1;
        (*atmp.0.data)[offset.1] = j + 103;
        offset.1 = offset.1 + 1;
        j = j + 1;
 etc.

which is probably not what we want.  The optimizers can't reduce this to the
original form either.
Comment 5 Jerry DeLisle 2006-09-10 05:05:32 UTC
This bug is related to slow compile found in test case for PR28914 with large array size.  Constructor related.
Comment 6 Tobias Burnus 2007-03-21 21:56:05 UTC
*** Bug 31301 has been marked as a duplicate of this bug. ***
Comment 7 Tobias Burnus 2007-06-25 08:02:46 UTC
*** Bug 32489 has been marked as a duplicate of this bug. ***
Comment 8 Tobias Schlüter 2007-10-06 14:08:49 UTC
There's no related bug field, but it's worth mentioning that PR19925 and this should probably be attacked at the same time.
Comment 9 Tobias Schlüter 2007-10-06 14:43:00 UTC
And this looks like the right place for an attack:
/* Given an array constructor, determine if the constructor is
   constant or not by expanding it and making sure that all elements
   are constants.  This is a bit of a hack since something like (/ (i,
   i=1,100000000) /) will take a while as* opposed to a more clever
   function that traverses the expression tree. FIXME.  */

int
gfc_constant_ac (gfc_expr *e)
{
Comment 10 Tobias Burnus 2008-01-13 23:00:47 UTC
See also notes/patch attempt in PR 32489.
Comment 11 Jerry DeLisle 2009-11-22 18:56:49 UTC
Also see PR 41807 for related info.
Comment 12 Jerry DeLisle 2009-11-27 07:31:44 UTC
Created attachment 19161 [details]
Preliminary patch

This patch cuts the compilation time of the original test case in half.  It passes all regression tests except initialization_20.f90.  I think this is an example of case that relies on a side effect to work.  If we can resilve this one regression we will make substantial progress.  The failing test case needs expansion/reduction.  I just need to find the spot, which I suspect is in expr.c (gfc_reduce_init_expr)
Comment 13 Jerry DeLisle 2009-11-28 01:46:01 UTC
Created attachment 19168 [details]
Updated patch

This exploratory patch passes all regression tests.  I have also successfully compiled and run the polyhedron benchmarks.

I have not tested higher order arrays to see if there is a compile time improvement yet.  Feel free to test.  What I hope to eventually do is move the expansion functions higher up the calling chain away from gfc_is_constant_expr.

Regardless, this is gives a fairly good improvement.
Comment 14 Jerry DeLisle 2009-11-28 05:04:25 UTC
I missed one regression from the patch in comment #13. Stay tuned.
Comment 15 Jerry DeLisle 2009-11-28 15:10:49 UTC
Created attachment 19170 [details]
Third time is a charm

This patch resolves the last remaining regression.  Removing the "didn't reduce" error allows things to proceed to the exceeds maximum size error message expected by initialization_20.f90.  It also triggers at the correct limit.  I reworked one of the test conditions to assure that both gfc_check_constructor_type and gfc_expand_constructor (expr) are executed.  I was not sure that was strictly neccessary, but I was suspicious of that logic that could eliminate one of the two in the OR.
Comment 16 Jerry DeLisle 2009-11-28 15:16:14 UTC
With this simply modified case:

program sel
    implicit none
    integer,parameter              :: n=10
    integer                        :: i,j,k,l
    real,dimension(n*n*n*n) :: vect
    vect(:) = (/ ((((( (i+j+k+l+3)),i=1,n),j=1,n),k=1,n),l=1,n) /)
    print *, vect
end

Compilation time is reduced by 1/2 with the patch. Other more complex examples need to be tested of course.
Comment 17 Dominique d'Humieres 2009-11-28 16:30:41 UTC
With the patch in comment #15 (gfc, gfc_c without), I see the following for the test

[macbook] f90/bug% cat pr19925_1_db.f90
INTEGER, PARAMETER :: N=100000
INTEGER, PARAMETER :: I(N)=(/(MOD(K,2),K=1,N)/)
INTEGER, PARAMETER :: M(N)=I(N:1:-1)
print *, I(1), M(1), I(N), M(N)
END

without (pr19925_1.f90)/with (pr19925_1_db.f90) the print line:

[macbook] f90/bug% time gfc_c pr19925_1.f90
pr19925_1.f90:3.36:

INTEGER, PARAMETER :: M(N)=I(N:1:-1)
                                    1
Error: Initialization expression didn't reduce (1)
368.554u 0.801s 6:09.49 99.9%	0+0k 0+5io 0pf+0w
[macbook] f90/bug% time gfc pr19925_1.f90
369.495u 0.629s 6:10.22 99.9%	0+0k 0+19io 0pf+0w
[macbook] f90/bug% a.out 
[macbook] f90/bug% time gfc_c pr19925_1_db.f90
pr19925_1_db.f90:3.36:

INTEGER, PARAMETER :: M(N)=I(N:1:-1)
                                    1
Error: Initialization expression didn't reduce (1)
367.576u 0.591s 6:08.25 99.9%	0+0k 0+5io 0pf+0w
[macbook] f90/bug% time gfc pr19925_1_db.f90
pr19925_1_db.f90:2.27:

INTEGER, PARAMETER :: I(N)=(/(MOD(K,2),K=1,N)/)
                           1
Error: The number of elements in the array constructor at (1) requires an increase of the allowed 65535 upper limit.   See -fmax-array-constructor option
pr19925_1_db.f90: In function 'MAIN__':
pr19925_1_db.f90:4:0: internal compiler error: in gfc_conv_array_constructor_expr, at fortran/trans-expr.c:3710
Please submit a full bug report,
with preprocessed source if appropriate.
See <http://gcc.gnu.org/bugs.html> for instructions.
369.184u 0.620s 6:09.87 99.9%	0+0k 0+5io 0pf+0w
Comment 18 Jerry DeLisle 2009-11-28 17:14:08 UTC
Created attachment 19172 [details]
Slightly modified charm

This version handles Dominique's test case in comment #17.
Comment 19 Jerry DeLisle 2009-11-28 17:52:28 UTC
The patch in comment #18 passes all regression tests as well.  I hope we are honing in on this.  It does make me wonder why at this point the BT type is unknown.
Comment 20 Jerry DeLisle 2009-11-29 19:36:33 UTC
Created attachment 19180 [details]
Hopefully final patch

This patch moves the number of elements patch up front so that the error is given almost immediately. Previously, with one of Dominique's test cases, it would take over 15 minutes on my machine here before one find's out there is a problem.  I use gfc_fatal_error because compilation at that this early stage continues on happily before quitting.  Can be very annoying for programs with large array constructors.  Testing continues.
Comment 21 Dominique d'Humieres 2009-11-29 22:10:27 UTC
With the patch in comment #20, I get several new failures:

gcc/testsuite/gfortran.dg/actual_array_constructor_3.f90
pr20923 and friends
pr34554        "

IIRC when the constructors are used as initialization or in statements, they are expanded at compile time when possible if the length is less than 2^16, otherwise they are computed at run time. I think this behavior should be kept. The only cases for which the fatal error should be triggered is for PARAMETERS as in pr19925 that must be computed at compile time.

Comment 22 Jerry DeLisle 2009-11-30 03:59:52 UTC
Ok, if I back up one step and leave the error message in trans-array.c and use gfc_fatal_error we get a usable patch.  One thing this is showing is that the expansion is being done in the parsing/matching phase of compilation and also in the resolution phase.  I do not yet understand why the ICE is triggered after the error: (with the changes I have made elsewhere.)

          if (c->iterator)
            {
              /* Problems occur when we get something like
                 integer :: a(lots) = (/(i, i=1, lots)/)  */
              gfc_error_now ("The number of elements in the array constructor "
			      "at %L requires an increase of the allowed %d "
			      "upper limit.  See -fmax-array-constructor "
			      "option", &expr->where,
			      gfc_option.flag_max_array_constructor);
	      return NULL_TREE;
	    }
Comment 23 Jerry DeLisle 2010-01-09 17:47:16 UTC
Subject: Bug 20923

Author: jvdelisle
Date: Sat Jan  9 17:47:04 2010
New Revision: 155769

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155769
Log:
2010-01-09 Jerry DeLisle <jvdelisle@gcc.gnu.org>

	PR fortran/20923
	PR fortran/32489
	* trans-array.c (gfc_conv_array_initializer): Change call to
	gfc_error_now to call to gfc_fatal_error.
	* array.c (count_elements): Whitespace. (extract_element): Whitespace.
	(is_constant_element): Changed name from constant_element.
	(gfc_constant_ac): Only use expand_construuctor for expression
	types of EXPR_ARRAY.  If expression type is EXPR_CONSTANT, no need to
	call gfc_is_constant_expr.
	* expr.c (gfc_reduce_init_expr): Adjust conditionals and delete error
	message.
	* resolve.c (gfc_is_expandable_expr): New function that determiners if
	array expressions should have their constructors expanded.
	(gfc_resolve_expr): Use new function to determine whether or not to call
	gfc_expand_constructor.

Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/array.c
    trunk/gcc/fortran/expr.c
    trunk/gcc/fortran/resolve.c
    trunk/gcc/fortran/trans-array.c

Comment 24 Jerry DeLisle 2010-01-09 19:01:58 UTC
Subject: Bug 20923

Author: jvdelisle
Date: Sat Jan  9 19:01:41 2010
New Revision: 155773

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=155773
Log:
2010-01-09 Jerry DeLisle <jvdelisle@gcc.gnu.org>

	PR fortran/32489
	* gfortran.dg/array_constructor_33.f90: New test.

	PR fortran/20923
	Fix ChangeLog entry.

Added:
    trunk/gcc/testsuite/gfortran.dg/array_constructor_34.f90
Modified:
    trunk/gcc/testsuite/ChangeLog

Comment 25 Jerry DeLisle 2010-01-14 03:04:26 UTC
Fixed on trunk.  New constructor code on fortran-exp will probably take a whole new approach on this.

Closing.