Has Anyone Got A Directory "Walker" Available

Alex Tweedly alex at tweedly.net
Sat May 5 18:31:25 EDT 2018


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.




More information about the Use-livecode mailing list