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