Re: c/7344: performance regression on huge case statements

[Jan Hubicka <jh@suse.cz>]

The following reply was made to PR c/7344; it has been noted by GNATS.

From: Jan Hubicka <jh@suse.cz>
To: Daniel Berlin <dberlin@dberlin.org>
Cc: Nathanael Nerode <neroden@twcny.rr.com>, gcc-gnats@gcc.gnu.org,
	rschiele@uni-mannheim.de, gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org,
	jh@suse.cz
Subject: Re: c/7344: performance regression on huge case statements
Date: Fri, 11 Oct 2002 11:23:40 +0200

 > 
 > 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
 > >
 > >