This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug c/35608] imit-structnest.c fails due to O(n^2) memory usage in record_component_alias
- From: "rguenther at suse dot de" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: 3 Nov 2009 12:21:48 -0000
- Subject: [Bug c/35608] imit-structnest.c fails due to O(n^2) memory usage in record_component_alias
- References: <bug-35608-15715@http.gcc.gnu.org/bugzilla/>
- Reply-to: gcc-bugzilla at gcc dot gnu dot org
------- Comment #9 from rguenther at suse dot de 2009-11-03 12:21 -------
Subject: Re: imit-structnest.c fails due to O(n^2) memory usage
in record_component_alias
On Tue, 3 Nov 2009, bonzini at gnu dot org wrote:
> ------- Comment #8 from bonzini at gnu dot org 2009-11-03 12:18 -------
> Memory allocation is O(n^2) in the nesting of the structures: when changing
> LIM4 from 6 to 7 invocations of the lower-level, memory goes from 583976 KB to
> 798116 KB (which is 1.366 times more, almost exactly a factor of (7/6)^2).
>
> The culprit is record_component_aliases which creates a subset relationship
> from each structure to each containing structure. Maybe we could reuse the
> et-forest here since these subset relationships form a forest (do all of them
> have this property? would we pessimize a lot by enforcing that even when it is
> conservative?)
Yes, they all form a forest. It shouldn't pessimize anything to enforce
this.
> I suppose the bug has always been there since alias.c was introduced, it's just
> that previously an unused struct did not call record_component_aliases.
Right.
Richard.
--
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=35608