Re: needless deep recursion in gt-c-decl.h

[Geoff Keating <geoffk at geoffk dot org>]

> Date: Tue, 23 Jul 2002 22:02:46 -0700
> From: Per Bothner <per@bothner.com>

> Geoff Keating wrote:
> >>From: Per Bothner <per@bothner.com>
> >>Specifically, we should iterate, not recurse, on the
> >>field that is most likely to be a long list, the TREE_CHAIN.
> 
> > It's not as simple as that, because there'll often be a reference to
> > the TREE_CHAIN from inside the node.
> 
> I don't know what this sentence means.  If you mean that some node
> referenced by one of the other (non-chain) fields (possibly indirectly)
> is the same node as the chain, I don't see how that's complicates it.

It means you need a more complicated design than the one you
presented, because in

while (! x is marked)
{
  mark x;
  recursively mark objects pointed to by x, but don't look at TREE_CHAIN(x);
  x = TREE_CHAIN (x);
}

the loop rarely iterates more than once, since very often TREE_CHAIN(x)
will be marked indirectly in the body of the loop.  You need something
like

x_limit = x;
while (! x_limit is marked)
{
  mark x_limit;
  x_limit = TREE_CHAIN (x_limit);
}
while (x != x_limit)
{
  mark objects pointed to by x;
  x = TREE_CHAIN (x);
}

> > However, yes, you can do
> > something like this.  In fact, I tried it in the hope that it would
> > make GC faster; it didn't (but it didn't make it much slower either).
> 
> Did it make it slower at all?  It would be strange if iteration is
> slower than recursion (unless that just happens to hit the cache better,
> which would surprise me).  If interation is the same speed or faster,
> we should use it, to reduce running out of stack space.

They were about the same speed, but I don't remember exactly.

One reason this might be more expensive is because of the extra
variable.  Most of the time cost of the high-level marking is in
function calls, and extra variables make the prologue/epilogue longer.

-- 
- Geoffrey Keating <geoffk@geoffk.org> <geoffk@redhat.com>