This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Remove O(N^2) complexity from cgraph_remove_node (fwd)
On Tue, Mar 01, 2005 at 06:35:11PM +0100, Richard Guenther wrote:
> On Tue, 1 Mar 2005, Daniel Jacobowitz wrote:
>
> > On Tue, Mar 01, 2005 at 04:44:10PM +0100, Richard Guenther wrote:
> > > Hi!
> > >
> > > This patch addresses a scalability issue with the cgraph_edge
> > > structure by changing the singly-linked chains to doubly-linked
> > > ones. This shaves off 7% of compile time from the tramp3d-v3
> > > testcase with the new inlining estimate at -O2 and 4% off a
> > > -O2 compile with leafify enabled and the old inlining estimates.
> > > With old inlining estimates and no leafify it saves 1%.
> > >
> > > Bootstrapped on i686-pc-linux-gnu for 4.0,
> > > bootstrapped and tested on x86_64-unknown-linux-gnu for mainline.
> > >
> > > Ok for mainline? Ok for branch?
> >
> > You're increasing the memory usage of these structures, which we have
> > quite a few of. I'd like to see memory results, and also timings for
> > some testcase other than the one you made the change for.
>
> I have bootstrap times to compare, which are
>
> real 17m29.042s
> user 30m28.707s
> sys 2m6.579s
>
> without the patch and
>
> real 17m27.300s
> user 30m23.081s
> sys 2m6.396s
>
> with the patch. Noise.
Thanks.
--
Daniel Jacobowitz
CodeSourcery, LLC