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

[Geoff Keating <geoffk at geoffk dot org>]

> Date: Tue, 23 Jul 2002 20:11:54 -0700
> From: Per Bothner <per@bothner.com>

> The gt_ggc_mx_lang_tree_node routine in the generated
> gt-c-decl.h file causes a stack overflow when I tried
> it under Darwin.  Perhaps I need to increase the stack
> limit, but the deep recursion is a performance problem
> that needlessly increases the working set.
> 
> Specifically, we should iterate, not recurse, on the
> field that is most likely to be a long list, the TREE_CHAIN.
> I don't understand how gengtype works, but the generated
> code should be something like this:
> 
> void
> gt_ggc_mx_lang_tree_node (x_p)
>        void *x_p;
> {
>    union lang_tree_node * const x = (union lang_tree_node *)x_p;
>    for (;;) {
>      if (! ggc_test_and_set_mark (x))
>        return;
>    {
>      ...
>      gt_ggc_m_tree_node ((*x).generic.common.type);
>      x = (*x).generic.common.chain;
>      if (x != NULL_TREE)
>        continue;
>      return;
>    }
> }

It's not as simple as that, because there'll often be a reference to
the TREE_CHAIN from inside the node.  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).

> All the comparisons against tag1 and tag2 may also be a performance
> problem.  I don't know if the compiler is smart enough to convert
>    if (tag2 == (TS_REAL_CST) ...;
>    if (tag2 == (TS_VECTOR)) ...;
> to:
>    if (tag2 == (TS_REAL_CST) ...;
>    else if (tag2 == (TS_VECTOR)) ...;
> Assuming it is, it would still be an advantage if we could
> order the type tests by frequency, unless the compiler is
> smart enough to compile all the tests into a switch.  Is it?

Doesn't matter, the branch now generates a switch in the same situation.

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