This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
Re: c/7344: performance regression on huge case statements
- From: Jan Hubicka <jh at suse dot cz>
- To: Daniel Berlin <dberlin at dberlin dot org>
- Cc: Nathanael Nerode <neroden at twcny dot rr dot com>, gcc-gnats at gcc dot gnu dot org,rschiele at uni-mannheim dot de, gcc-bugs at gcc dot gnu dot org, nobody at gcc dot gnu dot org,jh at suse dot cz
- Date: Fri, 11 Oct 2002 11:23:40 +0200
- Subject: Re: c/7344: performance regression on huge case statements
- References: <3DA631C4.1050900@twcny.rr.com> <6057C9B2-DCBE-11D6-86E9-000393575BCC@dberlin.org>
>
> On Thursday, October 10, 2002, at 10:04 PM, Nathanael Nerode wrote:
>
> >http://gcc.gnu.org/cgi-bin/gnatsweb.pl?cmd=view%20audit-
> >trail&database=gcc&pr=7344
> >
> >I'm tired of investigating this, but it seems likely that the problem
> >was introduced with the introduction of et-forest.c, since that's
> >where the loop is. This was introduced by Pavel Nejedly and committed
> >to mainline by Jan Hubicka (along with most of the surrounding code).
> >
> >(So that's why I'm ccing you; it looks like you caused it, so maybe
> >you can figure out how to fix it. :-/)
> >
> As I mentioned, this is likely a known problem, with a known fix.
>
> Jan, if you don't have plans to make it constant time soon, i suggest
> we cache the info using the patch that is on the tree-ssa branch.
I will send patch to predict.c to avoid so many queries of dominance
tree (in this testcase they are compltely useless as the information is
just thrown away later).
The et-forest can be slightly reorganized to always keep the reference
to the predecesor together with the node, but I think it should not be
needed for release branch then.
It is log(n) complexity, so it is fast and if we run into problem with
it, we do quadratic work somewhere else and run into problem with 5
times bigger testcase again.
Honza
>
> >--Nathanael
> >
> >