Aryeh Gregor wrote:
On Fri, Jul 3, 2009 at 3:13 AM, Tim Starlingtstarling@wikimedia.org wrote:
Loops are essential for readable code. There is no problem with allowing loops in conjunction with time limits, that we don't have already with complex templates. In fact, time limits for complex templates would be an improvement over the system of expansion limits we have at the moment.
But time limits are inconsistent. Whether a template hits the limit might depend on whether it happens to be running on an Apache with a Pentium IV, an Opteron, a Xeon, . . .
That's the reason I went with expansion limits when I wrote the code. But I think it was the wrong choice, because the code is complex and there are lots of ways to run over the 30s time limit set in php.ini, or to exceed the memory limit, even with the expansion limits in place. It's hard to find all the potential performance problems during code review, especially when new parser functions are constantly added.
I didn't say either method was perfect, just that time limits are better.
Recursion can give a long running time even if the depth is limited. By calling the function multiple times from its own body, you can have exponential time order in the recursion depth.
You can also have exponential time with loops.
Without the time limit, the worst case running time for a JavaScript script is infinity with finite input, so the time order is O(∞). With the time limit, it's O(1). That's the whole point, a time limit lets you ignore algorithmic complexities.
If you measure script execution times, instead of trying to guess them in advance, then you can concentrate developer effort on quotas, access control, profiling tools, etc., which I think are more tractable problems than analysing the performance every possible thing the parser can do and limiting it in advance.
-- Tim Starling