From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <gcc-prs-return-35296-listarch-gcc-prs=gcc.gnu.org@gcc.gnu.org>
Received: (qmail 5328 invoked by alias); 12 May 2003 22:46:02 -0000
Mailing-List: contact gcc-prs-help@gcc.gnu.org; run by ezmlm
Precedence: bulk
List-Archive: <http://gcc.gnu.org/ml/gcc-prs/>
List-Post: <mailto:gcc-prs@gcc.gnu.org>
List-Help: <mailto:gcc-prs-help@gcc.gnu.org>
Sender: gcc-prs-owner@gcc.gnu.org
Received: (qmail 5216 invoked by uid 71); 12 May 2003 22:46:01 -0000
Resent-Date: 12 May 2003 22:46:01 -0000
Resent-Message-ID: <20030512224601.5215.qmail@sources.redhat.com>
Resent-From: gcc-gnats@gcc.gnu.org (GNATS Filer)
Resent-Cc: gcc-prs@gcc.gnu.org, gcc-bugs@gcc.gnu.org
Resent-Reply-To: gcc-gnats@gcc.gnu.org, hzoli@hzoli.2y.net
Received: (qmail 9191 invoked from network); 12 May 2003 22:41:39 -0000
Received: from unknown (HELO hzoli.austin.ibm.com) (208.180.20.158)
  by sources.redhat.com with SMTP; 12 May 2003 22:41:39 -0000
Received: from hzoli by hzoli.austin.ibm.com with local (Exim 3.36 #1 (Debian))
	id 19FLzH-0005mr-00; Mon, 12 May 2003 17:41:39 -0500
Message-Id: <E19FLzH-0005mr-00@hzoli.austin.ibm.com>
Date: Mon, 12 May 2003 22:46:00 -0000
From: hzoli@hzoli.2y.net
To: gcc-gnats@gcc.gnu.org, debian-gcc@lists.debian.org
Cc: rth@gcc.gnu.org
References: <20030512033246.21455.qmail@sources.redhat.com> <E19FLRF-0005HF-00@hzoli.austin.ibm.com>
X-Send-Pr-Version: 3.113
Subject: c++/10760: Compile time increases quadratically with struct size
X-SW-Source: 2003-05/txt/msg01384.txt.bz2
List-Id: <gcc-prs.sourceware.org>


>Number:         10760
>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:   Mon May 12 22:46:01 UTC 2003
>Closed-Date:
>Last-Modified:
>Originator:     Zoltan Hidvegi
>Release:        gcc version 3.3 20030512 (prerelease)
>Organization:
>Environment:
System: x86/Linux & PowerPC/AIX

>Description:
Name lookups for struct members use linear search, which can result in
quadratic compile time increase.  See also c/10675:
http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-trail&database=gcc&pr=10675
http://gcc.gnu.org/ml/gcc-bugs/2003-05/msg01072.html

This happens in both c and c++, but I can only specify one category.

>How-To-Repeat:
The following is a shell script that will generate a struct with a
given number of members and a functions that assings zero to all
members.

------- 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;'

let i=0
echo 'void init_foo(struct foo *p) {'
while [ "$i" -lt "$1" ]
do
    echo "    p->i_$((i=i+1)) = 0;"
done
echo '}'
--------- END biggen.sh -------------

Run it like this:
./biggen.sh 10000 > big.C; time g++ -c big.c
Change the number from 10000 and see how the compile time is
affected.  Also watch the memory usage, e.g. with 25000 members it
needs 55M, but the memory usage scales linearly.

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