This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Speeding up ggc-simple on stage1
- To: law at cygnus dot com
- Subject: Re: Speeding up ggc-simple on stage1
- From: Alexandre Oliva <oliva at lsd dot ic dot unicamp dot br>
- Date: 14 Jan 2000 18:14:31 -0200
- Cc: gcc-patches at gcc dot gnu dot org
- References: <6396.947878485@upchuck>
On Jan 14, 2000, Jeffrey A Law <law@cygnus.com> wrote:
> I'd still be rather surprised. Even at 1k levels deep in the
> collector you're probably burning less than 256k of stack space
> unless the rs6000 port is particularly wasteful of stack space.
It's not. In one of these functions, just 64 bytes per invocation,
and I've never got recursion deeper than a hundred or so invocations
:-(
The following tests are the output of:
time ./cc1 reload.i -O2 -g -quiet -o /dev/null
On a K6-II 450 MHz with GNU/Linux RH6.1:
cc1 built with -O0, before patch:
30.45user 0.17system 0:30.67elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (789major+4214minor)pagefaults 0swaps
cc1 built with -O0, after patch:
29.28user 0.21system 0:29.48elapsed 100%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (642major+4213minor)pagefaults 0swaps
cc1 built with -O2, before patch:
27.20user 0.18system 0:27.50elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (509major+4208minor)pagefaults 0swaps
cc1 built with -O2, after patch:
25.64user 0.19system 0:25.83elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (595major+4209minor)pagefaults 0swaps
On a Sparc Ultra 450 (?) with Solaris7
cc1 built with -O0, before patch:
87.57user 0.32system 1:27.99elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
cc1 built with -O0, after patch:
85.61user 0.35system 1:26.21elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
cc1 built with -O2, before patch:
52.33user 0.32system 0:52.74elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
cc1 built with -O2, after patch:
49.89user 0.20system 0:50.34elapsed 99%CPU (0avgtext+0avgdata 0maxresident)k
0inputs+0outputs (0major+0minor)pagefaults 0swaps
It appears that the problem is not that recursion is taking too long;
maybe it's just that it's garbage collecting too much? Or it's just
thrashing too much :-(
In any case, here's the revised patch, now with a ChangeLog entry (I
don't know how it got lost in the first version, I'm pretty sure I
wrote it up :-(
Do you think it's worth installing, given that it makes the code quite
uglier, and not that much faster, and that a better implementation of
tail recursion would probably obtain the same small speed gain in
these functions?
Index: gcc/ChangeLog
from Alexandre Oliva <oliva@lsd.ic.unicamp.br>
ggc-simple.c (clear_marks, ggc_pop_context_1, tally_leaves):
Use a loop instead of tail recursion.
Index: gcc/ggc-simple.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/ggc-simple.c,v
retrieving revision 1.28
diff -u -p -r1.28 ggc-simple.c
--- gcc/ggc-simple.c 1999/12/26 23:06:54 1.28
+++ gcc/ggc-simple.c 2000/01/14 19:32:25
@@ -1,5 +1,5 @@
/* Simple garbage collection for the GNU compiler.
- Copyright (C) 1998, 1999 Free Software Foundation, Inc.
+ Copyright (C) 1998, 1999, 2000 Free Software Foundation, Inc.
This file is part of GNU CC.
@@ -277,11 +277,21 @@ static void
clear_marks (x)
struct ggc_mem *x;
{
- x->mark = 0;
- if (x->sub[0])
- clear_marks (x->sub[0]);
- if (x->sub[1])
- clear_marks (x->sub[1]);
+ for (;;)
+ {
+ x->mark = 0;
+ if (x->sub[1] && x->sub[0])
+ {
+ clear_marks (x->sub[0]);
+ x = x->sub[1];
+ }
+ else if (x->sub[1])
+ x = x->sub[1];
+ else if (x->sub[0])
+ x = x->sub[0];
+ else
+ break;
+ }
}
/* Free all objects in the current context that are not marked. */
@@ -420,12 +430,22 @@ ggc_pop_context_1 (x, c)
struct ggc_mem *x;
int c;
{
- if (x->context > c)
- x->context = c;
- if (x->sub[0])
- ggc_pop_context_1 (x->sub[0], c);
- if (x->sub[1])
- ggc_pop_context_1 (x->sub[1], c);
+ for (;;)
+ {
+ if (x->context > c)
+ x->context = c;
+ if (x->sub[1] && x->sub[0])
+ {
+ ggc_pop_context_1 (x->sub[0], c);
+ x = x->sub[1];
+ }
+ else if (x->sub[1])
+ x = x->sub[1];
+ else if (x->sub[0])
+ x = x->sub[0];
+ else
+ break;
+ }
}
/* Dump a tree. */
@@ -482,17 +502,25 @@ tally_leaves (x, depth, nleaf, sumdepth)
size_t *nleaf;
size_t *sumdepth;
{
- if (! x->sub[0] && !x->sub[1])
+ for (;;)
{
- *nleaf += 1;
- *sumdepth += depth;
- }
- else
- {
- if (x->sub[0])
- tally_leaves (x->sub[0], depth + 1, nleaf, sumdepth);
- if (x->sub[1])
- tally_leaves (x->sub[1], depth + 1, nleaf, sumdepth);
+ depth++;
+ if (x->sub[1] && x->sub[0])
+ {
+ tally_leaves (x->sub[0], depth, nleaf, sumdepth);
+ x = x->sub[1];
+ }
+ else if (x->sub[1])
+ x = x->sub[1];
+ else if (x->sub[0])
+ x = x->sub[0];
+ else
+ {
+ *nleaf += 1;
+ depth--;
+ *sumdepth += depth;
+ break;
+ }
}
}
#endif
--
Alexandre Oliva http://www.ic.unicamp.br/~oliva IC-Unicamp, Bra[sz]il
oliva@{lsd.ic.unicamp.br,guarana.{org,com}} aoliva@{acm,computer}.org
oliva@{gnu.org,kaffe.org,{egcs,sourceware}.cygnus.com,samba.org}
** I may forward mail about projects to mailing lists; please use them