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 17:55:45 +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.
The maximum memory usage peak for tramp3d-v3 at -O2 with leafify
enabled grows from 397326 kB to 399434 kB which is 0.5% for the
testcase that gains 4% in compile time performance.
Richard.
--
Richard Guenther <richard dot guenther at uni-tuebingen dot de>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/