[Bug fortran/13465] New: [gfortran] Data statement for large errors compiles verrrry slllowwwly and shows quadratic behaviour.

[Bug fortran/13465] New: [gfortran] Data statement for large errors compiles verrrry slllowwwly and shows quadratic behaviour.

[toon at moene dot indiv dot nluug dot nl]

This three line Fortran program (free format):

DIMENSION A(100000)
DATA A /100000*0.0 /
END

takes 48 minutes to compile on my 0.5 GHz G4 Powerbook.

If I reduce the extent of the array by 1/10th, it takes 30 seconds.

1. This is far too slow.
2. There's quadratic behaviour in the algorithm.

I think the integer computations to calculate offsets don't have to be done
using GMP routines, but can be expressed using variables of the ssizetype_t
type, just as in g77.

The quadratic effect is probably caused by the use of the expression stack.
I hope someone can suggest a better datastructure for this work.

-- 
           Summary: [gfortran] Data statement for large errors compiles
                    verrrry slllowwwly and shows quadratic behaviour.
           Product: gcc
           Version: tree-ssa
            Status: UNCONFIRMED
          Severity: normal
          Priority: P2
         Component: fortran
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: toon at moene dot indiv dot nluug dot nl
                CC: gcc-bugs at gcc dot gnu dot org


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

[Bug fortran/13465] [gfortran] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[toon at moene dot indiv dot nluug dot nl]

------- Additional Comments From toon at moene dot indiv dot nluug dot nl  2003-12-22 12:29 -------
Duh, fix "spelling" error in summary.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2003-12-22 12:29:11
               date|                            |
            Summary|[gfortran] Data statement   |[gfortran] Data statement
                   |for large errors compiles   |for large arrays compiles
                   |verrrry slllowwwly and shows|verrrry slllowwwly and shows
                   |quadratic behaviour.        |quadratic behaviour.


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

[Bug fortran/13465] [gfortran] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
           Keywords|                            |compile-time-hog
   Target Milestone|---                         |tree-ssa


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

[Bug fortran/13465] [gfortran] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-03-28 07:45 -------
Still a problem.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|2003-12-22 12:29:11         |2004-03-28 07:45:37
               date|                            |


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

[Bug fortran/13465] [gfortran] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|3.5.0                       |---


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

[Bug fortran/13465] [gfortran] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[tobi at gcc dot gnu dot org]

------- Additional Comments From tobi at gcc dot gnu dot org  2004-06-04 13:02 -------
The quadratic complexity comes from linearly traversing the list of data
initializers and then calling gfc_assign_data_value which in turn calls
gfc_insert_constructor. gfc_insert_constructor searches linearly through the
array until it finds the right place to insert the constructor. Hence we have
quadratic complexity.

-- 


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

[Bug fortran/13465] [gfortran] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[tobi at gcc dot gnu dot org]

------- Additional Comments From tobi at gcc dot gnu dot org  2004-06-04 13:33 -------
I meant find_con_by_offset, not gfc_insert_constructor.

-- 


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

[Bug fortran/13465] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2004-08-19 14:13 -------
*** Bug 17097 has been marked as a duplicate of this bug. ***

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rth at gcc dot gnu dot org


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

[Bug fortran/13465] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[cvs-commit at gcc dot gnu dot org]

------- Additional Comments From cvs-commit at gcc dot gnu dot org  2004-08-23 21:53 -------
Subject: Bug 13465

CVSROOT:	/cvs/gcc
Module name:	gcc
Changes by:	rth@gcc.gnu.org	2004-08-23 21:53:15

Modified files:
	gcc/fortran    : ChangeLog data.c gfortran.h match.c resolve.c 

Log message:
	PR 13465
	* data.c (find_con_by_offset): Search ordered list; handle
	elements with repeat counts.
	(gfc_assign_data_value_range): New.
	* gfortran.h (struct gfc_data_value): Make repeat unsigned.
	(gfc_assign_data_value_range): Declare.
	* match.c (top_val_list): Extract repeat count into a temporary.
	* resolve.c (values): Make left unsigned.
	(next_data_value): Don't decrement left.
	(check_data_variable): Use gfc_assign_data_value_range.

Patches:
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fortran/ChangeLog.diff?cvsroot=gcc&r1=1.161&r2=1.162
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fortran/data.c.diff?cvsroot=gcc&r1=1.6&r2=1.7
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fortran/gfortran.h.diff?cvsroot=gcc&r1=1.25&r2=1.26
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fortran/match.c.diff?cvsroot=gcc&r1=1.20&r2=1.21
http://gcc.gnu.org/cgi-bin/cvsweb.cgi/gcc/gcc/fortran/resolve.c.diff?cvsroot=gcc&r1=1.12&r2=1.13



-- 


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

[Bug fortran/13465] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[rth at gcc dot gnu dot org]

------- Additional Comments From rth at gcc dot gnu dot org  2004-08-23 22:05 -------
Fixed, sortof.  See caveats in http://gcc.gnu.org/ml/fortran/2004-08/msg00131.html

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


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

[Bug fortran/13465] Data statement for large arrays compiles verrrry slllowwwly and shows quadratic behaviour.

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|---                         |3.5.0


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