Questions from a total non-guru
pineapp...@yahoo.com
alleviate the impulse to make a snide comment or a put-down from a
certain unnamed individual. Or... at least I tried, anyway.
Okay, on with the topic at hand. This may seem like a pointless
exercise, but I am profiling this simple code in preparation for
profiling more complex code.
PC, WindowsXP, SWI-Prolog 5.6.36.
Consider this:
%%%%%%%%%%%%%%%%%%%%
do_stuff(X,X,X,X,X,A,B).
do_stuff(A,X,X,X,X,X,B).
do_stuff(A,B,X,X,X,X,X).
repeat(0,_).
repeat(I,Pred) :- call(Pred), J is I-1, repeat(J,Pred).
%%%%%%%%%%%%%%%%%%%%
Result - 10,000 repetitions:
?- garbage_collect. time(repeat(10000,do_stuff(1,1,1,1,1,1,1))).
Yes
% 40,001 inferences, 0.02 CPU in 0.03 seconds (50% CPU, 2560064 Lips)
Result - 100,000 repetitions:
?- garbage_collect. time(repeat(100000,do_stuff(1,1,1,1,1,1,1))).
Yes
% 400,001 inferences, 15.92 CPU in 16.98 seconds (94% CPU, 25123 Lips)
Question1: My suspicion is that the huge length of time for 100,000
repetitions is due to blowing out the stack. However, is repeat/2 not
tail-recursive? (As far as I know, trace/debug is turned off, stacks
are set at default).
Question2: If the problem is repeat/2, could you critique and help me
improve it?
Question3: If the problem is do_stuff, how is that possible? Seems
simple enough to me!
Question4: If the problem is something else, what is it? Perhaps
generation of a lot of garbage? Etc?
Thanks.
Chip Eastham
I think in SWI, if you run interactively, then you don't
get tail optimization. In any case, repeat/2 would be
tail recursive (allowing for the optimization) if you
put a cut in front of the final recursive call. The
point is that call(Pred) may leave a backtrack point.
do_stuff is simple; no real point in making it simpler,
though of course it is nondeterministic. At the expense
of a bit more code, you could make it deterministic, but
I don't think that's the way to go here.
regards, chip
pineapp...@yahoo.com
> I think in SWI, if you run interactively, then you don't
> get tail optimization.
Ah. First problem - running interactively.
> In any case, repeat/2 would be
> tail recursive (allowing for the optimization) if you
> put a cut in front of the final recursive call.
Ah. Second problem - I apparently don't understand enough about
Prolog, nor tail recursion. Please explain how the cut will create
tail recursion.
> The point is that call(Pred) may leave a backtrack point.
Third problem - investigate what built-ins do more thoroughly before
using them.
> do_stuff is simple; no real point in making it simpler,
> though of course it is nondeterministic. At the expense
> of a bit more code, you could make it deterministic, but
> I don't think that's the way to go here.
Explain the nondeterminism of do_stuff (what does that even mean -
that one cannot predict what do-stuff will do?).
Incidentally, is my repeat/2 (besides the non-use of your recommended
cut) the way to code up this sort of "for" loop in Prolog? How do
people generally do it (I found no "built-in" to do it, although I
could have very well missed it).
Thanks.
bart demoen
> I just said that I'm a total non-guru, okay?
Let me change your program slightly, and add some stuff ...
det.
nondet.
nondet.
nondet.
repeat(0,_) :- !.
repeat(I,Pred) :- call(Pred), J is I-1, repeat(J,Pred).
p(N,Pred) :- time(repeat(N,Pred)).
Now look at the output of the queries:
?- p(10000,det), statistics.
% 40,001 inferences, 0.02 CPU in 0.02 seconds (114% CPU, 2000050 Lips)
0.06 seconds cpu time for 49,857 inferences
2,508 atoms, 1,693 functors, 1,548 predicates, 21 modules, 36,698 VM-codes
Limit Allocated In use
Heap : 537,984 Bytes
Local stack : 16,777,216 16,384 764 Bytes
Global stack : 33,554,432 131,072 121,328 Bytes
Trail stack : 33,554,432 49,152 40,536 Bytes
1 threads, 0 finished threads used 0.00 seconds.
Yes
?- p(10000,nondet), statistics.
% 40,001 inferences, 0.02 CPU in 0.03 seconds (75% CPU, 2000050 Lips)
0.08 seconds cpu time for 90,227 inferences
2,510 atoms, 1,693 functors, 1,548 predicates, 21 modules, 36,703 VM-codes
Limit Allocated In use
Heap : 538,036 Bytes
Local stack : 16,777,216 1,409,024 764 Bytes
Global stack : 33,554,432 126,976 121,304 Bytes
Trail stack : 33,554,432 45,056 40,520 Bytes
1 threads, 0 finished threads used 0.00 seconds.
Yes
As you see, the query with nondet has a lot more Local Stack in use.
Now with 100000 instead of 10000.
?- p(100000,det), statistics.
% 400,001 inferences, 0.18 CPU in 0.19 seconds (96% CPU, 2222228 Lips)
0.22 seconds cpu time for 409,857 inferences
2,508 atoms, 1,693 functors, 1,548 predicates, 21 modules, 36,698 VM-codes
Limit Allocated In use
Heap : 537,976 Bytes
Local stack : 16,777,216 16,384 764 Bytes
Global stack : 33,554,432 106,496 104,320 Bytes
Trail stack : 33,554,432 40,960 34,764 Bytes
5 garbage collections gained 1,462,780 bytes in 0.02 seconds.
1 threads, 0 finished threads used 0.00 seconds.
Yes
?- p(100000,nondet), statistics.
% 400,001 inferences, 9.53 CPU in 9.62 seconds (99% CPU, 41973 Lips)
9.57 seconds cpu time for 409,857 inferences
2,508 atoms, 1,693 functors, 1,548 predicates, 21 modules, 36,698 VM-codes
Limit Allocated In use
Heap : 537,984 Bytes
Local stack : 16,777,216 14,008,320 764 Bytes
Global stack : 33,554,432 159,744 153,472 Bytes
Trail stack : 33,554,432 409,600 400,136 Bytes
5 garbage collections gained 1,048,256 bytes in 9.30 seconds.
1 threads, 0 finished threads used 0.00 seconds.
Yes
It's the arithmetic that causes garbage collection.
The choicepoints make gc take long.
If you use the -O option for SWI-Prolog, then arithmetic is optimized,
and less garbage collection needs to be done.
Cheers
Bart Demoen
ps. I don't think running this interactively has anything to do with the
issues.
bart demoen
> Ah. Second problem - I apparently don't understand enough about Prolog,
> nor tail recursion. Please explain how the cut will create tail
> recursion.
A cut does not create tail recursion, but can make sure that tail
recursion is possible.
> Explain the nondeterminism of do_stuff (what does that even mean - that
> one cannot predict what do-stuff will do?).
Without intending to give a very precise or complete definition ...
an example.
f(1).
f(2).
f(3).
is non-deterministic for the goal ?- f(X).
because that goal has three solutions.
The same is true for your do_stuff/n which for you goal do_stuff(1,1,...)
can succeed 3 times.
In a clause
foo :- f(X), foo.
the tail recursive call cannot be optimized because f(X) has more than
one solution - if you know about classical compilers, it would be easy to
explain that - maybe some other time.
Putting a cut after f(X) as in
foo :- f(X), !, foo.
results in only accepting the first solution of f/1, so now the tail
recursive call can be optimized.
Prolog compilers are not perfect at predicting which calls are
deterministic (have only one solution).
Prolog systems can give you the same answer multiple times, i.e. nothing
above would change if the definition of f/1 would have been
f(1).
f(1).
f(1).
Cheers
Bart Demoen
bart demoen
> A cut does not create tail recursion, but can make sure that tail
> recursion is possible.
Sorry, I meant
A cut does not create tail recursion, but can make sure that
tail recursion optimization is possible.
Cheers
Bart Demoen
pineapp...@yahoo.com
> Let me change your program slightly, and add some stuff ...
Extremely valuable analysis - I will study it in depth and try to iron
out the issues. It shows that even a "simple" and "basic" and "easily
understood" Prolog program is really none of the above. I'm guessing
that you have to be pretty much an expert with Prolog to be able to do
anything extensive in it. Now, you have to be an expert with C to do
anything in it as well, but for a different reason - the memory
management issues. Other than that though, it's just basic "plug and
chug" - no mysticism or anything that isn't easily understood by a
decent programmer, engineer, whatever. What's there to understand
about a for loop? A while statement? A switch statement?
Thanks!
Jan Wielemaker
> It's the arithmetic that causes garbage collection.
> The choicepoints make gc take long.
>
> If you use the -O option for SWI-Prolog, then arithmetic is optimized,
> and less garbage collection needs to be done.
Yip. Or use 5.7.1 :-)
Didn't check the details of Bart's analysis, but it sounds plausible.
> Cheers
>
> Bart Demoen
>
> ps. I don't think running this interactively has anything to do with the
> issues.
Indeed. last-call optimization is disabled if the system runs in
trace/debug mode. If has nothing to do with using the interactive
toplevel or not.
Cheers --- Jan
pineapp...@yahoo.com
post, I thought that the "nondeterminism" problem must mean that
Prolog was backtracking or otherwise "mucking around" on the 3 nondet/
0 facts, thus eating up stack space and wasting time. That was what
was causing the huge time differential between the two, I reasoned.
So I traced it out:
det.
nondet.
nondet.
nondet.
repeat(0,_) :- !.
repeat(I,Pred) :- call(Pred), J is I-1, repeat(J,Pred).
%%%%%%%%%%%%%%%%%%%%%%
?- trace. repeat(2, nondet).
Yes
Call: (8) repeat(2, nondet) ? [trace] 12 ?- creep
Call: (9) call(nondet) ? creep
Call: (10) nondet ? creep
Exit: (10) nondet ? creep
Exit: (9) call(nondet) ? creep
Call: (9) _L172 is 2-1 ? creep
Exit: (9) 1 is 2-1 ? creep
Call: (9) repeat(1, nondet) ? creep
Call: (10) call(nondet) ? creep
Call: (11) nondet ? creep
Exit: (11) nondet ? creep
Exit: (10) call(nondet) ? creep
Call: (10) _L221 is 1-1 ? creep
Exit: (10) 0 is 1-1 ? creep
Call: (10) repeat(0, nondet) ? creep
Exit: (10) repeat(0, nondet) ? creep
Exit: (9) repeat(1, nondet) ? creep
Exit: (8) repeat(2, nondet) ? creep
Yes
?- trace. repeat(2, det).
Yes
Call: (8) repeat(2, det) ? [trace] 13 ?- creep
Call: (9) call(det) ? creep
Call: (10) det ? creep
Exit: (10) det ? creep
Exit: (9) call(det) ? creep
Call: (9) _L172 is 2-1 ? creep
Exit: (9) 1 is 2-1 ? creep
Call: (9) repeat(1, det) ? creep
Call: (10) call(det) ? creep
Call: (11) det ? creep
Exit: (11) det ? creep
Exit: (10) call(det) ? creep
Call: (10) _L190 is 1-1 ? creep
Exit: (10) 0 is 1-1 ? creep
Call: (10) repeat(0, det) ? creep
Exit: (10) repeat(0, det) ? creep
Exit: (9) repeat(1, det) ? creep
Exit: (8) repeat(2, det) ? creep
Yes
Well, that blew that theory, as the traces are the same for both det
and nondet. In fact, they were what I originally expected, before I
started reading about all this nondeterminism. Then I read the
following:
On Sep 29, 12:01 pm, bart demoen <b...@cs.kuleuven.be> wrote:
> Prolog compilers are not perfect at predicting which calls are
> deterministic (have only one solution).
>
> Prolog systems can give you the same answer multiple times, i.e. nothing
> above would change if the definition of f/1 would have been
> f(1).
> f(1).
> f(1).
Got it. There is no more or no less "mucking around" and backtracking
with det than nondet above, as shown by the trace. However, one can
be tail call optimized, the other cannot!
Thanks!
Chip Eastham
Thanks, Jan (and Bart!) for clearing up my error about last-call
optimization in interactive mode of SWI. That's a nice feature
that differentiates SWI from some other interactive Prolog's.
regards, chip
bart demoen
> So I traced it
> out:
[..]
>
> ?- trace. repeat(2, nondet).
[..]
>
> ?- trace. repeat(2, det).
>
[..]
> Well, that blew that theory, as the traces are the same for both det and
> nondet.
Do not conclude too much from a trace: in trace more, some optimizations
might (and in fact are) switched off.
Cheers
Bart Demoen
bart demoen
> Thanks, Jan (and Bart!) for clearing up my error about last-call
> optimization in interactive mode of SWI. That's a nice feature that
> differentiates SWI from some other interactive Prolog's.
I do not like being involved in misunderstandings, so I would really
like things to be very explicit ...
What is the nice feature that differentiates SWI from other interactive
Prologs ? And which other interactive Prologs ? And as opposed to which
non-interactive Prologs ?
Cheers
Bart Demoen
Chip Eastham
> On Sep 29, 11:40 am, Chip Eastham <hardm...@gmail.com> wrote:
>
> > I think in SWI, if you run interactively, then you don't
> > get tail optimization.
>
> Ah. First problem - running interactively.
Okay, not a problem as Bart and Jan explain below (though some
other Prolog distributions do have this limitation).
> > In any case, repeat/2 would be
> > tail recursive (allowing for the optimization) if you
> > put a cut in front of the final recursive call.
>
> Ah. Second problem - I apparently don't understand enough about
> Prolog, nor tail recursion. Please explain how the cut will create
> tail recursion.
The possibility of tail recursion (aka last call) optimization
depends on there being no backtrack or "checkpoints" open when
the predicate makes its last call to itself. If there are none,
then the stack space taken up by the current invocation can be
cleverly reused, avoiding potential "blow up" of the allocated
stack. Putting a cut in front of the last call forces all the
backtrack options to be closed or "forgotten".
> > The point is that call(Pred) may leave a backtrack point.
>
> Third problem - investigate what built-ins do more thoroughly before
> using them.
>
> > do_stuff is simple; no real point in making it simpler,
> > though of course it is nondeterministic. At the expense
> > of a bit more code, you could make it deterministic, but
> > I don't think that's the way to go here.
>
> Explain the nondeterminism of do_stuff (what does that even mean -
> that one cannot predict what do-stuff will do?).
Nondeterminism means that a predicate call can succeed in more
than one way (potentially), at least as far as the Prolog engine
can tell. Maybe a clearer way to think about it is this:
determinism means the Prolog engine can tell when a predicate
call succeeds that there is no additional "search space" for
the engine to backtrack into.
> Incidentally, is my repeat/2 (besides the non-use of your recommended
> cut) the way to code up this sort of "for" loop in Prolog? How do
> people generally do it (I found no "built-in" to do it, although I
> could have very well missed it).
Yes, your repeat/2 is AFAIK the clear, concise way to code
a "for" loop in Prolog. Some Prolog's have a built-in,
for/4, that generates serial integers:
for(I,Start,End,Increment)
where I is an output and the others are input/bound variables.
But this would seem to need a "failure driven" section of
code following to cause backtracking into for/4. So for
what you were doing, I'm not aware of any "template"
built-in that handles iteration by recursion.
regards, chip
Chip Eastham
Okay, the feature is last-call optimization and whether
this is implemented for interactive queries.
I had a note from Dennis Merrit regarding Amzi! Prolog
back in January 2004 that last call optimization was effected
only in compiled code, not the interactive stuff.
Four years is a long time, so this may not be the current
state of art.
I was throwing out ideas from my stock of reasons that code
you expect is tail recursive may not take advantage of that.
Jan notes last call optimization is disabled for trace/debug
in SWI, and Dennis noted something similar about Amzi!
regards, chip