Home > Archive > Prolog > February 2005 > tail recursion optimization in SWI Prolog
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
tail recursion optimization in SWI Prolog
|
|
|
| Hi,
I have a question about tail recursion.
I have some predicates that use tail recursion and I expect them to
iterate for many thousands of iterations.
I am getting stack overlfow errors, which I can mitigate to some extent
by increasing the available stack size.
However isnt it right that tail recursive procedures should use a fixed
amount of the stack?
Is there anyway to make SWI Prolog perform some optimization on tail
recursion. I dont mind if the optimized form is a compiled program.
Any ideas, pointers would be really helpful.
Thank you!
bow
-----
| |
| Bart Demoen 2005-02-24, 8:58 pm |
| bow wrote:
> However isnt it right that tail recursive procedures should use a fixed
> amount of the stack?
If there is no non-determinism (or undetected determinism).
Simple tail recursive predicates like
a :- a.
for query ?- a.
or
a(0).
a(X) :- Y is X + 1, a(Y).
for ?- a(1).
seem not to run out of stack in SWI-Prolog, so perhaps you should show
us your program (and query) ...
Cheers
Bart Demoen
| |
|
| Well here is a program that I ran in SWI prolog.
The output is shown at the bottom.
It can be seen that the Stack usage values increase over time.
I took that to mean that the stack is consumed, even though the program
uses tail iteration.
Does that make the question clearer?
out(N) :-
write('-----------------------------------------------------'),nl,
statistics,
write('-----------------------------------------------------'),nl,
rec(N),
statistics,
write('-----------------------------------------------------'),nl.
rec(0).
rec(N) :-
NewN is N-1,
rec(NewN).
Output from the program
-------------------------------------
5 ?- out(1000000).
-----------------------------------------------------
0.16 seconds cpu time for 228,966 inferences
2,024 atoms, 1,223 functors, 1,466 predicates, 23 modules, 29,800
VM-codes
Limit Allocated In use
Heap : 416,220 Bytes
Local stack : 2,097,152 12,288 764 Bytes
Global stack : 4,096,000 20,480 1,156 Bytes
Trail stack : 4,194,304 12,288 412 Bytes
5 garbage collections gained 1,392,100 bytes in 0.00 seconds.
1 threads, 0 finished threads used 0.00 seconds.
-----------------------------------------------------
0.59 seconds cpu time for 2,229,012 inferences
2,024 atoms, 1,223 functors, 1,466 predicates, 23 modules, 29,800
VM-codes
Limit Allocated In use
Heap : 416,220 Bytes
Local stack : 2,097,152 12,288 828 Bytes
Global stack : 4,096,000 102,400 99,200 Bytes
Trail stack : 4,194,304 36,864 33,088 Bytes
62 garbage collections gained 17,261,800 bytes in 0.05 seconds.
1 threads, 0 finished threads used 0.00 seconds.
-----------------------------------------------------
| |
|
| bow a écrit :
> Well here is a program that I ran in SWI prolog.
> The output is shown at the bottom.
> It can be seen that the Stack usage values increase over time.
> I took that to mean that the stack is consumed, even though the program
> uses tail iteration.
> Does that make the question clearer?
>
>
Are you refering to some kind of memory leak ?
here's the output in my swi home version ( 5.2.13, ouch an old one :) )
?- out(1000000).
-----------------------------------------------------
0.00 seconds cpu time for 2,462 inferences
1,768 atoms, 1,080 functors, 1,290 predicates, 20 modules, 26,220 VM-codes
Limit Allocated In use
Heap : 379,248 Bytes
Local stack : 2,048,000 16,384 832 Bytes
Global stack : 4,096,000 16,384 756 Bytes
Trail stack : 4,096,000 16,384 292 Bytes
1 threads, 0 finished threads used 0.00 seconds.
-----------------------------------------------------
1.96 seconds cpu time for 2,002,505 inferences
1,768 atoms, 1,080 functors, 1,290 predicates, 20 modules, 26,220 VM-codes
Limit Allocated In use
Heap : 379,248 Bytes
Local stack : 2,048,000 16,384 896 Bytes
Global stack : 4,096,000 73,728 70,468 Bytes
Trail stack : 4,096,000 24,576 23,516 Bytes
?- out(10000000).
-----------------------------------------------------
1.98 seconds cpu time for 2,002,736 inferences
1,770 atoms, 1,080 functors, 1,290 predicates, 20 modules, 26,220 VM-codes
Limit Allocated In use
Heap : 379,368 Bytes
Local stack : 2,048,000 16,384 832 Bytes
Global stack : 4,096,000 40,960 744 Bytes
Trail stack : 4,096,000 24,576 276 Bytes
54 garbage collections gained 15,907,420 bytes in 0.26 seconds.
1 threads, 0 finished threads used 0.00 seconds.
-----------------------------------------------------
21.42 seconds cpu time for 22,002,782 inferences
1,770 atoms, 1,080 functors, 1,290 predicates, 20 modules, 26,220 VM-codes
Limit Allocated In use
Heap : 379,368 Bytes
Local stack : 2,048,000 16,384 896 Bytes
Global stack : 4,096,000 172,032 171,364 Bytes
Trail stack : 4,096,000 57,344 57,148 Bytes
596 garbage collections gained 175,680,348 bytes in 2.63 seconds.
1 threads, 0 finished threads used 0.00 seconds.
and for out(10000000).
but once I ran statistics after the goal execution, I got :
statistics.
21.45 seconds cpu time for 22,011,294 inferences
2,356 atoms, 1,531 functors, 1,294 predicates, 20 modules, 30,460 VM-codes
Limit Allocated In use
Heap : 469,764 Bytes
Local stack : 2,048,000 16,384 796 Bytes
Global stack : 4,096,000 40,960 740 Bytes
Trail stack : 4,096,000 24,576 264 Bytes
596 garbage collections gained 175,680,348 bytes in 2.63 seconds.
1 threads, 0 finished threads used 0.00 seconds.
a pretty normal situation no ?
I'm not sur to understand the problem : isn't it normal to swi to keep
all the choice points in the stack if a predicate is not over ?
| |
|
| you can see from your runs that the Global stack usage increases, the
bigger the value of N in the call "out(N)".
What I know is that when you program in other languages and use a tail
recursive definition, the compiler can change it into an iterative
form.
The amount of memory used in that case is constant and does not depend
on how many iterations.
So my question is, does SWI prolog do this optimization? or am I
missing something?
bow
------
| |
| Jan Wielemaker 2005-02-25, 8:58 am |
| On 2005-02-25, bow <bharat_purohit@yahoo.com> wrote:
> you can see from your runs that the Global stack usage increases, the
> bigger the value of N in the call "out(N)".
>
> What I know is that when you program in other languages and use a tail
> recursive definition, the compiler can change it into an iterative
> form.
> The amount of memory used in that case is constant and does not depend
> on how many iterations.
> So my question is, does SWI prolog do this optimization? or am I
> missing something?
Yes, but last-call optimization only affects the local (environment-)
stack. The trouble is that A is B + 1 is by default executed totally
naive: create a term B+1 and evaluate it. This creates global stack,
but GC will nicely deal with it. If you enable optimisation using
"pl -O" or :- set_prolog_flag(optimise, true). arithmetic will be
translated to a stack engine and this goes away. The downsite is
that you cannot trace it.
Please note that if you enable debugging (?- debug. or ?- trace.),
last call optimiation is disabled and the system will indeed run out
of stack.
Cheers --- Jan
|
|
|
|
|