On 05/05/2018 01:29, Richard Gaskin via use-livecode wrote:
How does recursion impair performance so significantly?
In general, there's significant work involved in a function or handler
call and return - you need to establish a new context for locals, copy
or calculate, parameters, etc. My claim that recursion is slow relative
to a serial- or loop-based version is language-independent (though there
might be specific exceptions like LISP :-)
Compiler writers spend considerable effort minimizing the overhead of
function calls - but still recursion is common, and indeed recognizing
"tail-recursion" and optimizing it away is worthwhile.
I don't know enough (i.e. I know nothing) about LC's engine, so don't
know specifically what might be involved for LC.
But here's a minimal test case (code below)
1. 65 : serial
2. 288 : many function calls
3. 471 : same number of calls as 2, more paramters
4. 273 : same number of calls as 2, but recursive
Note : result for 2 and 4 are the same - caused by the number of calls,
not the fact that it's recursion.
Note : 3 (same as 2 but with extra parameters) is slower.
This does point the way towards possible improvements in recursive
solutions (and specifically in the code I used in my earlier recursive
directory walker function). I'll try those out and see if they make a
difference.
Anyway - here's the code that gave the above results:
on mouseup
local t1, t2
constant K = 1000
local x
constant KX = 100
put the millisecs into t1
repeat K times
put KX into x
repeat
if x = 0 then exit repeat
subtract 1 from x
end repeat
end repeat
put the millisecs into t2
put t2 - t1 & CR after msg
put the millisecs into t1
repeat K times
put KX into x
repeat
if x = 0 then exit repeat
put myfunc(x) into x
end repeat
end repeat
put the millisecs into t2
put t2 - t1 & CR after msg
put the millisecs into t1
repeat K times
put KX into x
repeat
if x = 0 then exit repeat
put manyParameters(x, 1, 2, "333", "444") into x
end repeat
end repeat
put the millisecs into t2
put t2 - t1 & CR after msg
put the millisecs into t1
repeat K times
put KX into x
put recursive(x) into x
end repeat
put the millisecs into t2
put t2 - t1 & CR after msg
end mouseup
function myfunc p
return p-1
end myfunc
function manyParameters p, p1, p2, p3, p4
return p-1
end manyParameters
function recursive p
if p=0 then return 0
return recursive(p-1)
end recursive
-- Alex.
_______________________________________________
use-livecode mailing list
use-livecode@lists.runrev.com
Please visit this url to subscribe, unsubscribe and manage your subscription
preferences:
http://lists.runrev.com/mailman/listinfo/use-livecode
