Find limit of recursion: Difference between revisions
jq
(→{{header|Go}}: Update with runtime/debug.SetMaxStack added in Go 1.2) |
(jq) |
||
Line 891:
Sample output (IE6):
<pre>Recursion depth on this system is 2552.</pre>
=={{header|jq}}==
Recent versions of jq (after July 1, 2014, i.e. after version 1.4) include some "Tail Call Optimizations" (TCO). As a result, tail-recursive functions of arity 0 will run indefinitely in these later versions. The TCO optimizations also speed up other recursive functions.
Accordingly we present two test functions and show the results using jq 1.4 and using a version of jq with TCO optimizations.
'''Arity-0 Function'''
<lang jq>def zero_arity:
if (. % 1000000 == 0) then . else empty end, ((.+1)| zero_arity);
with_arity(0)</lang>
'''Arity-1 Function'''
<lang jq>def with_arity(n):
if (n % 1000 == 0) then n else empty end, with_arity(n+1);
with_arity(1)</lang>
'''Results using jq 1.4'''
<lang sh>
# Arity 0 - without TCO:
...
23000000 # 1.62 GB
25000000
*** error: can't allocate region
user 0m54.558s
sys 0m2.773s
# Arity 1 - without TCO:
...
77000 # 23.4 MB
...
85000 # 23.7 MB
90000 # 25.4 MB
237000 # 47.4 MB (5h:08)
242000 # 50.0 MB (5h:14m)
# [job cancelled manually after over 5 hours]
</lang>
'''Results using jq with TCO'''
The arity-0 test was stopped after the recursive function had been called 100,000,000 (10^8) times. The memory required did not grow beyond 360 KB (sic).
<lang sh>
$ time jq -n -f Find_limit_of_recursions.jq
...
10000000 # 360 KB
...
100000000 # 360 KB
# [job cancelled to get a timing]
user 2m0.534s
sys 0m0.329s
</lang>
The arity-1 test process was terminated simply because it had become too slow; at that point it had only consumed about 74.6K MB.
<lang sh>
...
56000 # 9.9MB
...
95000 # 14.8 MB
98000 # 15.2 MB
99000 # 15.4 MB
100000 # 15.5 MB
127000 # 37.4 MB
142000 # 37.4 MB
254000 # 74.6 MB
287000 # 74.6 MB
406000 # 74.6 MB (8h:50m)
412000 # 74.6 MB (9h:05m)
# [job cancelled manually after over 9 hours]</lang>
'''Discussion'''
Even without the TCO optimizations, the effective limits for recursive jq functions are relatively high:
# the arity-0 function presented here proceeded normally beyond 25,000,000 (25 million) iterations;
# the arity-1 function is more effectively constrained by performance than by memory: the test process was manually terminated after 242,000 iterations.
With the TCO optimizations:
# the arity-0 function is not only unconstrained by memory but is fast and remains fast; it requires only 360 KB (that is KB).
# the arity-1 function is, once again, more effectively constrained by performance than by memory: the test process process was terminated after 412,000 iterations simply because it had become too slow; at that point it had only consumed about 74.6 MB.
=={{header|Liberty BASIC}}==
| |||