This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
Re: c/7344: performance regression on huge case statements
- From: Nathanael Nerode <neroden at twcny dot rr dot com>
- To: gcc-gnats at gcc dot gnu dot org, gcc-prs at gcc dot gnu dot org, rschiele at uni-mannheim dot de, gcc-bugs at gcc dot gnu dot org, nobody at gcc dot gnu dot org
- Date: Thu, 10 Oct 2002 22:55:48 -0400
- Subject: Re: c/7344: performance regression on huge case statements
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...