From: Geoff Keating <geoffk@geoffk.org>
To: per@bothner.com
Cc: gcc@gcc.gnu.org
Subject: Re: needless deep recursion in gt-c-decl.h
Date: Wed, 24 Jul 2002 05:17:00 -0000 [thread overview]
Message-ID: <200207240443.g6O4hx418758@desire.geoffk.org> (raw)
In-Reply-To: <3D3E1AFA.2010707@bothner.com> (message from Per Bothner on Tue, 23 Jul 2002 20:11:54 -0700)
> 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>
next prev parent reply other threads:[~2002-07-24 4:44 UTC|newest]
Thread overview: 117+ messages / expand[flat|nested] mbox.gz Atom feed top
2002-07-24 4:53 Per Bothner
2002-07-24 5:17 ` Geoff Keating [this message]
2002-07-24 7:09 ` Per Bothner
2002-07-24 7:17 ` Geoff Keating
2002-07-24 7:52 ` Per Bothner
2002-07-25 2:32 ` Geoff Keating
2002-07-25 11:33 ` Per Bothner
2002-07-25 14:20 ` Geoff Keating
2002-07-26 8:37 ` Per Bothner
2002-07-30 21:41 ` Geoff Keating
2002-07-31 1:40 ` Per Bothner
2002-08-01 12:32 ` Geoff Keating
2002-08-01 14:00 ` Mike Stump
2002-08-01 16:00 ` Geoff Keating
2002-08-01 19:17 ` Richard Henderson
2002-08-05 10:06 ` Per Bothner
2002-08-05 10:21 ` Geoff Keating
2002-08-05 10:44 ` Per Bothner
2002-08-05 11:14 ` Geoff Keating
2002-08-05 11:36 ` Per Bothner
2002-08-05 11:39 ` David Edelsohn
2002-08-05 11:56 ` Per Bothner
2002-08-05 12:08 ` Geoff Keating
2002-08-05 12:08 ` Geoff Keating
2002-08-05 13:23 ` David Edelsohn
2002-08-05 14:28 ` Per Bothner
2002-08-05 15:04 ` Geoff Keating
2002-08-05 15:37 ` Per Bothner
2002-08-05 16:15 ` Geoff Keating
2002-08-05 15:26 ` Zack Weinberg
2002-08-05 15:42 ` Per Bothner
-- strict thread matches above, loose matches on Subject: below --
2004-01-20 2:19 switch statement performance Paul Vixie
2004-01-20 22:13 ` Geoff Keating
2004-01-20 22:26 ` Paul Vixie
2004-01-21 0:07 ` Geoff Keating
2004-01-21 0:29 ` Paul Vixie
2004-01-21 4:13 ` Ian Lance Taylor
2004-01-21 5:15 ` Paul Vixie
2004-01-21 21:54 ` tm_gccmail
[not found] <geoffk@geoffk.org>
2002-06-10 10:31 ` whither specs? Geoff Keating
2002-06-10 10:55 ` David Edelsohn
2002-06-10 10:56 ` Geoff Keating
2002-06-10 11:01 ` H . J . Lu
2002-06-10 11:18 ` David Edelsohn
2002-06-10 11:47 ` Mumit Khan
2002-06-11 16:48 ` Jason R Thorpe
2002-06-12 1:20 ` Theodore Papadopoulo
2002-06-12 11:01 ` Richard Henderson
2002-06-12 11:36 ` Theodore Papadopoulo
2002-06-12 15:48 ` Richard Henderson
2002-06-12 16:54 ` H . J . Lu
2002-11-24 6:52 ` Jason R Thorpe
2002-11-24 7:07 ` H. J. Lu
2002-11-25 10:01 ` Theodore Papadopoulo
2002-11-25 10:05 ` Jason R Thorpe
2002-11-25 14:40 ` Theodore Papadopoulo
2002-11-25 10:37 ` H. J. Lu
2002-06-10 15:01 ` Matthias Benkmann
2002-06-10 12:17 ` Tom Tromey
2002-06-10 15:37 ` Zack Weinberg
2002-06-10 19:25 ` Mark Mitchell
2002-06-05 12:28 PCH merge bootstrap failure on systems without flex Kaveh R. Ghazi
2002-06-05 19:37 ` Geoff Keating
2002-06-05 19:59 ` David Edelsohn
2002-06-05 20:22 ` Kaveh R. Ghazi
2002-06-10 0:01 ` Mark Mitchell
2002-06-10 3:17 ` Gerald Pfeifer
2002-06-10 7:48 ` Kaveh R. Ghazi
[not found] ` <Pine.BSF.4.44.0206101202120.46487-100000@naos.dbai.tuwien. ac.at>
2002-06-10 5:41 ` Andrea 'Fyre Wyzard' Bocci
2002-06-05 20:37 ` Geoff Keating
2002-05-12 12:50 Dumb register allocation (PPC) Zack Weinberg
2002-05-12 16:59 ` law
2002-05-12 21:38 ` David Edelsohn
2002-05-12 22:44 ` Zack Weinberg
2002-05-13 18:20 ` Richard Henderson
2002-05-14 13:15 ` Dale Johannesen
2002-05-14 13:15 ` David Edelsohn
2002-05-15 0:00 ` Richard Henderson
2002-05-15 8:27 ` David Edelsohn
2002-05-15 11:47 ` Geoff Keating
2002-05-15 12:08 ` law
2002-05-15 11:50 ` David Edelsohn
2002-05-15 12:38 ` law
2002-05-15 12:43 ` Geoff Keating
2002-05-15 12:55 ` David Edelsohn
2002-04-29 14:36 PR 6394 Mark Mitchell
2002-04-29 21:38 ` John David Anglin
2002-04-30 10:31 ` David Edelsohn
2002-04-30 10:48 ` John David Anglin
2002-04-30 18:48 ` law
2002-04-30 19:55 ` John David Anglin
2002-04-30 20:43 ` law
2002-04-30 21:06 ` John David Anglin
2002-04-30 12:56 ` Geoff Keating
2002-04-30 13:07 ` David Edelsohn
2002-04-30 13:12 ` John David Anglin
2002-04-30 13:37 ` Geoff Keating
2002-04-30 13:41 ` David Edelsohn
2002-04-30 14:07 ` law
2002-04-30 14:28 ` John David Anglin
2002-04-30 13:59 ` John David Anglin
2002-04-30 14:04 ` law
2002-04-30 14:39 ` John David Anglin
2002-04-30 14:54 ` law
2002-04-30 15:04 ` John David Anglin
2002-04-30 15:23 ` law
2002-04-30 15:29 ` John David Anglin
2002-04-30 15:52 ` law
2002-04-30 16:11 ` law
2002-04-30 16:27 ` John David Anglin
2002-04-30 16:41 ` law
2002-04-30 18:46 ` law
2002-04-30 20:18 ` John David Anglin
2002-05-01 7:17 ` Peter Barada
2002-04-30 16:34 ` Geoff Keating
2002-04-30 17:04 ` law
2002-04-30 18:48 ` law
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=200207240443.g6O4hx418758@desire.geoffk.org \
--to=geoffk@geoffk.org \
--cc=gcc@gcc.gnu.org \
--cc=geoffk@redhat.com \
--cc=per@bothner.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).