Ah, that makes sense. It's not so much the recursion per se, but the
more general advantage of inline processing vs handler calls.
In the test case below you know how many levels deep you're going, which
seems a good fit for inline loops. But how do we handle cases like
directory traversal, where we don't know in advance how deep we'll need
to go?
It's at least comforting to see that while the overhead of handler calls
is significant, it's mostly in relative comparison: If I read that
correctly, there are 1000 iterations of 100 operations, for a total of
100k operations. If my coffee is working, that means an overhead of
just 0.00208 ms per operation when called in a separate handler, no?
(thinking 273ms total for separate handler - 65ms for inline, per 100k
operations).
With directory traversal, I'd guess the overhead of physically touching
each inode would outweigh that manyfold.
Still useful to keep in mind: when inline code can do the job clearly,
it will be more efficient.
--
Richard Gaskin
Fourth World Systems
Alex Tweedly wrote:
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
