Has Anyone Got A Directory "Walker" Available

Richard Gaskin ambassador at fourthworld.com
Sun May 6 15:12:57 EDT 2018


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.




More information about the use-livecode mailing list