https://gcc.gnu.org/bugzilla/show_bug.cgi?id=83309
Bug ID: 83309
Summary: Structure elements have O(n^2) compile time slowdown
Product: gcc
Version: 7.2.0
Status: UNCONFIRMED
Severity: normal
Priority: P3
Component: c
Assignee: unassigned at gcc dot gnu.org
Reporter: wsnyder at wsnyder dot org
Target Milestone: ---
Created attachment 42804
--> https://gcc.gnu.org/bugzilla/attachment.cgi?id=42804&action=edit
Example program to make programs showing the slowdown
A program with >10K structure elements was taking hours to compile. The
attached program was used to make programs with different numbers of elements,
and the following was observed with G++ 7.2 (and also 5.4 and 4.4):
0.04 seconds to compile class with total of 2000 ints
0.11 seconds to compile class with total of 4000 ints
0.22 seconds to compile class with total of 6000 ints
0.41 seconds to compile class with total of 8000 ints
0.56 seconds to compile class with total of 10000 ints
Which seems close to O(n^2).
The same is observed with a "typedef int"'ed type, but all times are
approximately 4 times longer:
0.15 seconds to compile class with total of 2000 typedef'ed ints
0.45 seconds to compile class with total of 4000 typedef'ed ints
0.90 seconds to compile class with total of 6000 typedef'ed ints
1.62 seconds to compile class with total of 8000 typedef'ed ints
2.58 seconds to compile class with total of 10000 typedef'ed ints
If instead of having 2000 integers in a class, the program instead has 20
unique structures each with 100 members (the same 2000 total declarations), the
time is goes way down, as one would expect. This does show however the problem
is not related to file or total structure size. Not surprisingly, if enough
structures are used, a similar problem arises with a O(num_structures^2)
slowdown.
0.02 seconds to compile class with total of 2000 from 20 structs of 100
typedef'ed ints
0.03 seconds to compile class with total of 4000 from 40 structs of 100
typedef'ed ints
0.04 seconds to compile class with total of 6000 from 60 structs of 100
typedef'ed ints
0.07 seconds to compile class with total of 8000 from 80 structs of 100
typedef'ed ints
0.11 seconds to compile class with total of 10000 from 100 structs of 100
typedef'ed ints
Thanks.
