c/7344: performance regression on huge case statements
Nathanael Nerode
neroden@twcny.rr.com
Thu Oct 10 19:55:00 GMT 2002
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...
More information about the Gcc-bugs
mailing list