Re: WAM Vs. TOAM


"bart demoen" <bmd@xxxxxxxxxxxxxx> wrote in message
news:pan.2007.11.19.20.39.31.312358@xxxxxxxxxxxxxxxxx
On Thu, 11 Oct 2007 11:31:10 -0400, Neng-Fa Zhou wrote:

1. Backtracking becomes much simpler than that in the WAM because no
argument registers need be saved and restored.
and compile such disjunction in the body properly - Yap, XSB, BIM-Prolog,
hProlog (and probably some others) do that. The original WAM did not
specify how to compile disjunction. There is a tech report on this,
maybe even a CICLOPS paper.

You meant this paper:
www.cs.kuleuven.be/publicaties/rapporten/cw/CW295.ps.gz
In B-Prolog, new predicates are introduced for disjunctions. I don't see
slowdown in compilation of disjunctions. I tested your packs. It took
B-Prolog only 14 seconds on my slow notebook to compile the largest pack,
which has 1.8m bytes of giant disjunctions.

Inlining disjunctions is too complicated to me, especially when indexing is
involved. If you can achieve something in approach A effortlessly while you
need to achieve the same in approach B with plenty of effort, that means
approach A is better than B.


BTW, it is not true that garbage collection necessitates the
initialization of stack variables (on first entry and/or on
backtracking): it is simply your choice. SICStus also initializes some
stack slots because of gc (and so does XSB, and GNU-Prolog did at some
point), so you are not alone in this choice - but Yap, BIM-Prolog and
hProlog don't.

Thanks to Jan Wielemaker who told me this trick at ICLP, I made the
improvement in B-Prolog Version 7.1. This change alone helps improve the
average speed by nearly 10%.

2. The tail calls in a (non-binary) procedure can reuse both the space of
and the information in the frame for the procedure if the frame can be
reused.
The WAM approach allows to reuse arguments in the FIRST goal. This is
better than in the LAST goal, because the chances that the LAST goal
is ever executed, are smaller than that the FIRST goal is executed.
[just so that nobody gets the wrong idea: yes, the LAST goal could be
executed much more often because of backtracking, but the reuse can
only happen when the clause up to the last goal (not included) has
become deterministic]. But don't take this as (part of) my "proof"
that the WAM is better: the relative merit of reuse in first or last
goal depends on the program, and I have never found any evidence that
in practice there is a systematic advantage for the TOAM on this
point.

I know this statistics: most Prolog predicates don't fail, especially those
with tail recursion. I believe that reuse of frames does give TOAM an
advantage. We can jointly work to answer this question: which calls are more
worthwhile to reuse, the first or the last? I can help get the dynamic
statistics from B-Prolog and you help get the statistics from hProlog.

3. The delay mechanism can be implemented more efficiently.

This is exactly what we (Phuong-Lan and me) have disproved already a
few times; first in the CICLOPS06 paper (with a traditional meta-call
based delay mechanism), and recently in the rejected submission for
ICLP07 (with a frame-on-heap implementation); meaning: your 3) is
simply not true. Please note that proving that A is not better than
B, does not mean that one has proven that B is better than A: we don't
claim the WAM is better than the TOAM.

When freeze is used, a call is awakened only once in most cases. Your work
is incomplete: you need to find out how the architecture affects constraint
propagation, where a call can be suspended and awakened many times. I'll be
convinced if you also obtain similar results on constraint propagation with
the WAM.

Thirdly, having a garbage collector does not need imply a slow down of
the system, neither does having more boxed items. hProlog has bigints,
and a native string and character type - all boxed of course - and gc,
and all that doesn't seem to slow it down in a formidable way. Once
you have a few boxed items, the others come for free (performance
wise, not implementation wise).

This is certainly not true to B-Prolog. I just did a comparison and found
that B-Prolog (version 7.1, no initialization of stack variables) became 8%
faster on the Aquarius benchmark after the GC flag is turned off. The cost
paid is higher than that because there are other changes made to accommodate
GC (e.g., each frames needs to carry a type for GC). The GC algorithm
adopted in B-Prolog was originally designed by Older & Rummell, which
requires trailing of all stack slots that reference the newest heap fragment
so that old segments need not be scanned for GC. I believe that I can
easily make the CLP(FD) system run 20% faster if GC were not an obstacle.

- btw, it would be so much better
if B-Prolog's source were readable to the community, better for
B-Prolog in the first place.

I agree. This project has received not even a single penny of funding from
any US federal funding agency (all my proposals were rejected for the reason
of being incremental), and I don't have the obligation to make the source
code completely public. I may decide to make it semi-public to interested
developers once I find sponsors. I'll let you know if this plan
materializes.

having heap frames is not something I'd like to see (it's too
complicated).

Which means we failed to explain it properly - we might try again at
some point.

I wish you good luck. I have never read the paper. Has it been published as
a technical report?

Cheers,
Neng-Fa


.

Relevant Pages

  • Re: Planner, micro-planner, etc.
    ... Delay and events in the TOAM and the WAM ... B-Prolog uses the TOAM abstract machine. ... The traditional WAM approach - partly established by Prolog implementors - is to put suspension terms on the heap. ...
    (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: Planner, micro-planner, etc.
    ... TOAM) is fundamentally better than the WAM. ... attempts to use every opportunity to let the sun shine on B-Prolog. ... this is not a proof of the superiority of the TOAM over the ...
    (comp.lang.prolog)