From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (qmail 20268 invoked by alias); 11 Oct 2002 02:56:01 -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 20254 invoked by uid 71); 11 Oct 2002 02:56:01 -0000 Date: Thu, 10 Oct 2002 19:56:00 -0000 Message-ID: <20021011025601.20253.qmail@sources.redhat.com> To: nobody@gcc.gnu.org Cc: gcc-prs@gcc.gnu.org, From: Nathanael Nerode Subject: Re: c/7344: performance regression on huge case statements Reply-To: Nathanael Nerode X-SW-Source: 2002-10/txt/msg00448.txt.bz2 List-Id: The following reply was made to PR c/7344; it has been noted by GNATS. From: Nathanael Nerode To: gcc-gnats@gcc.gnu.org, gcc-prs@gcc.gnu.org, rschiele@uni-mannheim.de, gcc-bugs@gcc.gnu.org, nobody@gcc.gnu.org Cc: Subject: Re: c/7344: performance regression on huge case statements Date: Thu, 10 Oct 2002 22:55:48 -0400 caclulate_value has n additions if n nodes require additions (and a lot seem to in the case of the switch statement). et_forest_common_ancestor has m + 2 calls to calculate_value if m nodes need to be traversed to get to the 'ancestor'. I'm no expert on what the code is doing, but it looks a lot more like n^2 in the number of nodes walked, at least in the most pathological case. How is that O(log n) ? We'd have to have some really strong guarantees on the tree layout. Maybe it's log n in the *average* case...