Bug 10760 - Compile time increases quadratically with struct size
Summary: Compile time increases quadratically with struct size
Status: RESOLVED FIXED
Alias: None
Product: gcc
Classification: Unclassified
Component: c++ (show other bugs)
Version: 3.3
: P2 normal
Target Milestone: 3.4.0
Assignee: Not yet assigned to anyone
URL:
Keywords: compile-time-hog
Depends on:
Blocks:
 
Reported: 2003-05-12 22:46 UTC by hzoli
Modified: 2004-06-07 23:51 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail: 3.4.0
Last reconfirmed: 2004-02-20 16:56:13


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description hzoli 2003-05-12 22:46:01 UTC
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.

Release:
gcc version 3.3 20030512 (prerelease)

Environment:
System: x86/Linux & PowerPC/AIX

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.
Comment 1 Andrew Pinski 2003-05-23 04:37:38 UTC
C++ is almost as fast as C in 3.4 already for this testcase.
[zhivago2:~/src/gccPRs/10760] pinskia% time g++  -S  big.c
6.890u 0.260s 0:07.29 98.0%     0+0k 0+7io 0pf+0w
[zhivago2:~/src/gccPRs/10760] pinskia% time gcc -S big.c
6.340u 0.290s 0:06.75 98.2%     0+0k 0+0io 0pf+0w
where big.c is generated by sh biggen.sh 10000 > big.c

1020:
[zhivago2:~/src/gccPRs/10760] pinskia% time g++ -S big.c
8.060u 0.330s 0:08.61 97.4%     0+0k 0+0io 0pf+0w
[zhivago2:~/src/gccPRs/10760] pinskia% time gcc -S big.c
7.510u 0.350s 0:08.02 98.0%     0+0k 0+2io 0pf+0w
Comment 2 Andrew Pinski 2003-05-24 01:07:45 UTC
Could some on confirm this on 3.3, since I found out that 3.4 did not have this problem 
and as I do not have 3.3 on my computer.  But since this is not a regression should this 
be closed?
Comment 3 Wolfgang Bangerth 2003-05-24 01:27:24 UTC
I can confirm this with the C compiler:

g/x> bash big.sh 5000 > x.c
g/x> time /home/bangerth/bin/gcc-3.4-pre/bin/gcc -c x.c

real    0m5.777s
user    0m5.470s
sys     0m0.070s

g/x> bash big.sh 10000 > x.c
g/x> time /home/bangerth/bin/gcc-3.4-pre/bin/gcc -c x.c

real    0m22.423s
user    0m21.170s
sys     0m0.130s

g/x> bash big.sh 20000 > x.c
g/x> time /home/bangerth/bin/gcc-3.4-pre/bin/gcc -c x.c

real    1m32.867s
user    1m22.020s
sys     0m0.210s

g/x> /home/bangerth/bin/gcc-3.4-pre/bin/gcc -v
Reading specs from
/home/bangerth/bin/gcc-3.4-pre/lib/gcc-lib/i686-pc-linux-gnu/3.4/specs
Configured with: ../gcc-3.4-CVS/configure --enable-languages=c,c++,f77
--enable-checking --prefix=/home/bangerth/bin/gcc-3.4-pre
Thread model: posix
gcc version 3.4 20030520 (experimental)


W.
Comment 4 Andrew Pinski 2003-05-24 02:08:28 UTC
Ok I can confirm this on both C and C++ still:
[zhivago2:~/src/gccPRs/10760] pinskia% sh biggen.sh 10000 > big.c
[zhivago2:~/src/gccPRs/10760] pinskia% time g++ -S big.c
6.980u 0.270s 0:07.46 97.1%     0+0k 0+0io 0pf+0w
[zhivago2:~/src/gccPRs/10760] pinskia% sh biggen.sh 20000 > big.c
[zhivago2:~/src/gccPRs/10760] pinskia% time g++ -S big.c
29.950u 0.620s 0:32.47 94.1%    0+0k 0+2io 0pf+0w
[zhivago2:~/src/gccPRs/10760] pinskia% time gcc -S big.c
29.270u 0.550s 0:31.55 94.5%    0+0k 0+4io 0pf+0w
[zhivago2:~/src/gccPRs/10760] pinskia% sh biggen.sh 10000 > big.c
[zhivago2:~/src/gccPRs/10760] pinskia% time gcc -S big.c
6.530u 0.220s 0:06.95 97.1%     0+0k 0+0io 0pf+0w
[zhivago2:~/src/gccPRs/10760] pinskia% gcc -v 
Reading specs from /Users/pinskia/fsf-nocheck/lib/gcc-lib/powerpc-apple-darwin6.6/3.4/
specs
Configured with: /Volumes/UFS_Partition/pinskia/src/fsf/gcc/src/configure --enable-
threads=posix --disable-nls --disable-multilib --disable-checking --enable-libjaava --
prefix=/Users/pinskia/fsf-nocheck
Thread model: posix
gcc version 3.4 20030523 (experimental)
[zhivago2:~/src/gccPRs/10760] pinskia% g++ -v
Reading specs from /Users/pinskia/fsf-nocheck/lib/gcc-lib/powerpc-apple-darwin6.6/3.4/
specs
Configured with: /Volumes/UFS_Partition/pinskia/src/fsf/gcc/src/configure --enable-
threads=posix --disable-nls --disable-multilib --disable-checking --enable-libjaava --
prefix=/Users/pinskia/fsf-nocheck
Thread model: posix
gcc version 3.4 20030523 (experimental)
[zhivago2:~/src/gccPRs/10760] pinskia% 
Comment 5 Andrew Pinski 2003-05-24 02:17:48 UTC
C++ is quadratically in delete_duplicate_fields/delete_duplicate_fields_1 in cp/class.c, 
this could be fixed by using a hashtable like C does in detect_field_duplicates  in c-decl.c 
.
Comment 6 Andrew Pinski 2003-07-21 02:35:20 UTC
The C problem has been fixed on the mainline see PR 10962 so only a C++ problem is 
left.
Comment 7 Dara Hazeghi 2003-08-23 00:03:06 UTC
Not a regression.
Comment 8 Andrew Pinski 2003-11-21 16:44:10 UTC
Lets try to have this fixed for 3.5.
Comment 9 Andrew Pinski 2004-06-07 03:19:20 UTC
I will try to look into this next week.
Comment 10 Andrew Pinski 2004-06-07 23:51:22 UTC
Actually this was fixed by:
        PR c++/14086
        * class.c (delete_duplicate_fields_1): Remove.
        (delete_duplicate_fields): Likewise.
        (finish_struct_anon): Remove check for members with the same name
        as their enclosing class.
        (check_field_decls): Do not call duplicate_fields.
        * decl.c (grokdeclarator): Remove check for static data members
        with the same name as their enclosing class.
        * name-lookup.c (push_class_level_binding): Check for members with
        the same name as their enclosing class.