22 Sep
2011
22 Sep
'11
9:40 p.m.
Dave Abrahams <dave@boostpro.com> writes:
In general, all algorithms in a compiler should be linear, or worst case n*log(n). Any quadratic or worse algorithm is pretty much a bug.
I'd like to think so, too, but I'm not sure all implementors would agree with you.
The problem complexities are not linear or n*log(n) so why should you expect the algorithms to be? The heuristic algorithms to achieve acceptable results could be limited to n*log(n) but like everything else, it's a tradeoff. Dependence analysis, for example, can get very expensive in some situations if you want reasonable accuracy. Customers always say they don't care about compile time as long as the code is fast. Until, of course, they do. :) -Dave