From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 31122 invoked by alias); 11 Oct 2002 02:26:02 -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 31106 invoked by uid 71); 11 Oct 2002 02:26:01 -0000 Date: Thu, 10 Oct 2002 19:26:00 -0000 Message-ID: <20021011022601.31105.qmail@sources.redhat.com> To: nobody@gcc.gnu.org Cc: gcc-prs@gcc.gnu.org, From: Daniel Berlin Subject: Re: c/7344: performance regression on huge case statements Reply-To: Daniel Berlin X-SW-Source: 2002-10/txt/msg00447.txt.bz2 List-Id: The following reply was made to PR c/7344; it has been noted by GNATS. From: Daniel Berlin To: Nathanael Nerode Cc: gcc-gnats@gcc.gnu.org, gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org, rschiele@uni-mannhiem.de, jh Subject: Re: c/7344: performance regression on huge case statements Date: Thu, 10 Oct 2002 22:21:36 -0400 On Thursday, October 10, 2002, at 10:13 PM, Nathanael Nerode wrote: > Daniel Berlin wrote: >>> >> It doesn't cache the info (I think Jan said he could make it constant >> time >> in the alternative, which would also solve the problem), so it is >> constantly recomputing a value that hasn't changed. > > (...and one which is expensive to compute using the current algorithm) > This is the ironic part: It's not that expensive to compute. It's O(log n) It just used to be O(1), so it's 1-15 times slower than it used to be. You wouldn't notice in most cases, because it scales so slowly. In fact, I only cached it because on the tree-ssa-branch, because there were cases where it was called 238 million times. You start to notice at that point :). --Dan