From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 29442 invoked by alias); 11 Oct 2002 09:26:08 -0000 Mailing-List: contact gcc-prs-help@gcc.gnu.org; run by ezmlm Precedence: bulk List-Archive: List-Post: List-Help: Sender: gcc-prs-owner@gcc.gnu.org Received: (qmail 29428 invoked by uid 71); 11 Oct 2002 09:26:07 -0000 Date: Fri, 11 Oct 2002 02:26:00 -0000 Message-ID: <20021011092607.29427.qmail@sources.redhat.com> To: nobody@gcc.gnu.org Cc: gcc-prs@gcc.gnu.org, From: Jan Hubicka Subject: Re: c/7344: performance regression on huge case statements Reply-To: Jan Hubicka X-SW-Source: 2002-10/txt/msg00451.txt.bz2 List-Id: The following reply was made to PR c/7344; it has been noted by GNATS. From: Jan Hubicka To: Daniel Berlin Cc: Nathanael Nerode , 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 > > > >