Find limit of recursion: Difference between revisions
Content added Content deleted
(→{{header|Go}}: Update with runtime/debug.SetMaxStack added in Go 1.2) |
(jq) |
||
Line 891: | Line 891: | ||
Sample output (IE6): |
Sample output (IE6): |
||
<pre>Recursion depth on this system is 2552.</pre> |
<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}}== |
=={{header|Liberty BASIC}}== |