c/7344: performance regression on huge case statements

[Nathanael Nerode]

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

From: Nathanael Nerode <neroden@twcny.rr.com>
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...