Re: WAM Vs. TOAM


"bart demoen" <bmd@xxxxxxxxxxxxxx> wrote in message
news:pan.2007.11.13.20.49.48.337560@xxxxxxxxxxxxxxxxx
On Mon, 12 Nov 2007 11:29:44 -0500, Neng-Fa Zhou wrote:

Here is an attempt to make a better benchmark - inspired by yours, but
removing as much fluff as I could think of:

top :- p(1000,2,3,4,5,6,7,8,9,10,11,12,13,14,15) ; true.

p(X1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,X14,X15):-
X1=X15,
NewX1 is X1-1,
mytrue,
p(NewX1,X2,X3,X4,X5,X6,X7,X8,X9,X10,X11,X12,X13,X14,X15).

The definition of mytrue is simply:

mytrue.

but make sure to put it in a different file, otherwise systems that do
inline will just remove it (I assume that preventing inlining was your
intention with the convoluted dummy/1 predicate).

Can we agree on this new code as the benchmark to base the future
discussion on ?

A base case should be added to terminate recursion of p and "X1=X15" should
be replaced with something like "(X1=X5;X1\=X2),!". After this change,
however, you may say that some systems handle disjunctions better than
others. There is no perfect benchmark, but I agree your revised version is
better.

Ah, I see an implied meaning here: is it clear that the differences in
speed for your top benchmark are to be attributed to the design or the
implementation ? Or should we still leave open the possibility that it
could be either ?

It's always both. A good design always needs a good implementation to lead
to a good system.

This is not surprising. In the paper on TOAM Jr., the following
discussion
is made: "It is easy to find program patterns that make one machine
arbitrarily worse than the other."

It is good you have come to that conclusion. Maybe it will stop you
from saying that the TOAM is superior to the WAM.

I still believe that TOAM is better than WAM in general for CLP but not
always so. I am more convienced than before after I finished B-Prolog
Version 7.1. All the discussions were ignited by my original posting: "It
is true that the WAM played a great role in enhancing the performance of
Prolog, but we could have ended up with similar or even faster
emulator-based Prolog implementations had we followed the DEC-10
implementation or the traditional Pascal machine. You may be convinced after
comparing the latest version of B-Prolog (version 7.0) with the major
WAM-based systems." I didn't use the word "superior".

My example program is of a completely different nature, as it is not
showing a fundamental difference between abstract machines, but
between their implementors, or rather, between the choices that those
implementors have made. Let me start by showing the program:

nrev(emptylist,emptylist).
nrev([X|Rest],Ans):-
nrev(Rest,L), app(L,[X|emptylist],Ans).

app(emptylist,L,L).
app([X|L1],L2,[X|L3]):-
app(L1,L2,L3).

?- nrev([1,2,3,...,30|emptylist],L).


I expected something more interesting:-) I couldn't reproduce your benchmark
results on my Windows XP. I found that B-Prolog is half the speed of Yap and
Sicstus (not a quarter), and is faster than many other WAM-based systems on
this benchmark.


Once you realise that the TOAM has nothing to do with the bad
performance of B-Prolog on this program, you might also understand
that when WAM-based systems like SICStus, Yap ... are slower for some
benchmarks than B-Prolog, the explanation is NOT that the TOAM is
superior to the WAM, but that the implementors of those systems have
made different choices than you.

What is your conclusion? All designs are equivalent and there are only
differences in implementations?

Nevertheless, our investigation of a large number of programs shows
that last calls have more to share with the heads than first calls in
most tail recursive procedures.

Are there any details about this investigation ?
Was it static or dynamic ?

I did take a look at the programs written by myself and other people, but I
don't have the statistics. Here is one of the key predicates in the boyer
benchmark:

rewrite_args(0,_,_) :- !.
rewrite_args(N,Old,Mid) :-
arg(N,Old,OldArg),
arg(N,Mid,MidArg),
rewrite(OldArg,MidArg),
N1 is N-1,
rewrite_args(N1,Old,Mid).

The first call shares no variable and the last call shares two variables
with the head.

Cheers,
Neng-Fa


.

Relevant Pages

  • Re: WAM Vs. TOAM
    ... insisting on using the less fluffy benchmark to make B-Prolog look bad: ... This profiling is easier to do in a WAM ... the WAM implementations on this program even though, as you know, some WAM ...
    (comp.lang.prolog)
  • Re: WAM Vs. TOAM
    ... The definition of mytrue is simply: ... Can we agree on this new code as the benchmark to base the future ... insisting on using the less fluffy benchmark to make B-Prolog look bad: ... when the designs are so close ...
    (comp.lang.prolog)
  • Re: WAM Vs. TOAM
    ... insisting on using the less fluffy benchmark to make B-Prolog look bad: ... the WAM implementations on this program even though, as you know, some WAM ... tak = 328 ...
    (comp.lang.prolog)
  • Re: Commercial uses of prolog (to convince my boss its valid)
    ... I have uploaded a new package, which includes all the benchmark programs and ... also the scripts for running on B-Prolog, Gnu-Prolog, Eclipse, and Sicstus. ...
    (comp.lang.prolog)