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)
- From: Richard Guenther <rguenth at tat dot physik dot uni-tuebingen dot de>
- To: Daniel Jacobowitz <drow at false dot org>
- Cc: gcc-patches at gcc dot gnu dot org
- Date: Tue, 1 Mar 2005 18:35:11 +0100 (CET)
- Subject: Re: [PATCH] Remove O(N^2) complexity from cgraph_remove_node (fwd)
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.
Richard.