23 Sep
2011
23 Sep
'11
11:52 a.m.
On 22.09.2011 23:40, David A. Greene wrote:
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.
I was thinking only of the frontend, not the optimizers or code generation. Sebastian