Re: c/10675: Compile time increases quadratically with struct size

Re: c/10675: Compile time increases quadratically with struct size

[rth]

Synopsis: Compile time increases quadratically with struct size

Responsible-Changed-From-To: unassigned->rth
Responsible-Changed-By: rth
Responsible-Changed-When: Fri May  9 01:25:35 2003
Responsible-Changed-Why:
    Patch in progress.

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=10675

Re: c/10675: Compile time increases quadratically with struct size

[Richard Henderson]

The following reply was made to PR c/10675; it has been noted by GNATS.

From: Richard Henderson <rth@redhat.com>
To: Zoltan Hidvegi <hzoli@hzoli.2y.net>
Cc: rth@gcc.gnu.org, gcc-bugs@gcc.gnu.org, gcc-prs@gcc.gnu.org,
   gcc-gnats@gcc.gnu.org
Subject: Re: c/10675: Compile time increases quadratically with struct size
Date: Mon, 12 May 2003 15:14:41 -0700

 On Mon, May 12, 2003 at 05:06:29PM -0500, Zoltan Hidvegi wrote:
 > This does indeed fix the compile-time with gcc, but g++
 > still behaves quadratically. 
 
 I didn't try to fix C++ at the same time.
 
 > And even C still seems to have slow lookups, as if the hash is only used
 > to detect duplicates, but for member lookup it still uses linear
 > search.
 
 This is true.
 
 > I'd like to reopen this bug, or should I open a new bug?
 
 Open a new one please.
 
 
 r~

Re: c/10675: Compile time increases quadratically with struct size

[Zoltan Hidvegi]

The following reply was made to PR c/10675; it has been noted by GNATS.

From: Zoltan Hidvegi <hzoli@hzoli.2y.net>
To: rth@gcc.gnu.org, gcc-bugs@gcc.gnu.org, gcc-prs@gcc.gnu.org, 
 hzoli@hzoli.2y.net, gcc-gnats@gcc.gnu.org
Cc:  
Subject: Re: c/10675: Compile time increases quadratically with struct size
Date: Mon, 12 May 2003 17:06:29 -0500 (CDT)

 --ELM1052777189-18480-0_
 Content-Transfer-Encoding: 7bit
 Content-Type: text/plain; charset=US-ASCII
 
 > Synopsis: Compile time increases quadratically with struct size
 > 
 > State-Changed-From-To: analyzed->closed
 > State-Changed-By: rth
 > State-Changed-When: Mon May 12 03:32:46 2003
 > State-Changed-Why:
 >     http://gcc.gnu.org/ml/gcc-patches/2003-05/msg00989.html
 > 
 > http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=10675
 
 I've applied the patch to the gcc-3.3 and manually fixed the
 conflicts.  This does indeed fix the compile-time with gcc, but g++
 still behaves quadratically.  Also for C++ you may want to run the
 attached biggen3.sh, that will generate a struct as before, but it
 adds a constructor that zero-initializes all members.  This also have
 unusually large, although linear memory usage, e.g., the compile of a
 struct with 25000 members with constructor initializers needs 55M
 (based on the memory use showed by top on both AIX and Linux).  And
 even C still seems to have slow lookups, as if the hash is only used
 to detect duplicates, but for member lookup it still uses linear
 search.  Run the attached biggen5.sh to test this, it will create a C
 struct and a function that initializes the struct.  Because of all
 this, I'd like to reopen this bug, or should I open a new bug?
 
 Zoli
 
 --ELM1052777189-18480-0_
 Content-Transfer-Encoding: 7bit
 Content-Type: text/plain
 Content-Disposition: attachment; filename=biggen3.sh
 Content-Description: 
 
 #! /bin/sh
 let i=0
 echo 'struct foo {'
 while [ "$i" -lt "$1" ]
 do
     echo "    int i_$((i=i+1));"
 done
 echo "    int junk;"
 let i=0
 echo '    foo() :'
 while [ "$i" -lt "$1" ]
 do
     let 'i=i+1'
     echo "	i_$i(0),"
 done
 echo "	junk(0) {}"
 echo '};'
 echo 'struct foo f;'
 
 --ELM1052777189-18480-0_
 Content-Transfer-Encoding: 7bit
 Content-Type: text/plain
 Content-Disposition: attachment; filename=biggen5.sh
 Content-Description: 
 
 #! /bin/sh
 let i=0
 echo 'struct foo {'
 while [ "$i" -lt "$1" ]
 do
     echo "    int i_$((i=i+1));"
 done
 echo '};'
 #echo 'struct foo f;'
 
 let i=0
 echo 'void init_foo(struct foo *p) {'
 while [ "$i" -lt "$1" ]
 do
     echo "    p->i_$((i=i+1)) = 0;"
 done
 echo '}'
 
 --ELM1052777189-18480-0_--

Re: c/10675: Compile time increases quadratically with struct size

[rth]

Synopsis: Compile time increases quadratically with struct size

State-Changed-From-To: analyzed->closed
State-Changed-By: rth
State-Changed-When: Mon May 12 03:32:46 2003
State-Changed-Why:
    http://gcc.gnu.org/ml/gcc-patches/2003-05/msg00989.html

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=10675

Re: c/10675: Compile time increases quadratically with struct size

[ehrhardt]

Synopsis: Compile time increases quadratically with struct size

State-Changed-From-To: open->analyzed
State-Changed-By: cae
State-Changed-When: Thu May  8 22:34:46 2003
State-Changed-Why:
    Confirmed on 3.3 and 3.4. Compile time increases quadratically.

http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=10675

c/10675: Compile time increases quadratically with struct size

[hzoli]

>Number:         10675
>Category:       c
>Synopsis:       Compile time increases quadratically with struct size
>Confidential:   no
>Severity:       critical
>Priority:       medium
>Responsible:    unassigned
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Thu May 08 01:56:00 UTC 2003
>Closed-Date:
>Last-Modified:
>Originator:     Zoltan Hidvegi
>Release:        3.2.3 (Debian testing/unstable)
>Organization:
>Environment:
System: Linux hzoli 2.4.21-rc1-ac3 #1 Wed Apr 30 11:10:22 CDT 2003 i686 unknown unknown GNU/Linux
Architecture: i686

host: i386-pc-linux-gnu
build: i386-pc-linux-gnu
target: i386-pc-linux-gnu
configured with: ../src/configure -v --enable-languages=c,c++,java,f77,objc,ada --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --with-gxx-include-dir=/usr/include/c++/3.2 --enable-shared --with-system-zlib --enable-nls --without-included-gettext --enable-__cxa_atexit --enable-clocale=gnu --enable-java-gc=boehm --enable-objc-gc i386-linux
>Description:
The compile time increases quadratically (actually more than
quadratically) with the number of members in a struct.

>How-To-Repeat:
The following is a shell script that will generate a struct with a
given number of members and instantiates a global variable of that
type:

------- BEGIN biggen.sh -------------
#! /bin/sh
let i=0
echo 'struct foo {'
while [ "$i" -lt "$1" ]
do
    echo "int i_$((i=i+1));"
done
echo '};'
echo 'struct foo f;'
--------- END biggen.sh -------------

Run it like this:
./biggen.sh 10000 > big.c; cc -c big.c
Change the number from 10000 and see how the compile time is affected.
E.g. on my 1.73GHz Athlon, 5000 members take 1.66s, 10000 takes 8.5s and 20000
takes 35.91s.  Unfortunately, I need to compile a generated struct
with several hundred thousand members, which is not feasible.

>Fix:
>Release-Note:
>Audit-Trail:
>Unformatted: