[mercury-users] tabling

[Dominique de Waleffe]

> From: owner-mercury-users at cs.mu.OZ.AU
> [mailto:owner-mercury-users at cs.mu.OZ.AU]On Behalf Of Fergus Henderson
> Sent: Tuesday, November 28, 2000 1:04 PM
> To: mercury-users at cs.mu.OZ.AU
> Subject: Re: [mercury-users] tabling
> > If we have a predicate with the following declaration,
> >
> > :- pragma memo(is_some_condition/3).
> > :- pred is_some_condition(int::in, string::in, map(int,
> string)::in) is semidet.
> >
> > We observe a dramatic slow down when adding the memo pragma, I assume
> > that this is because the map argument is quite large and the same in
> > each call leading to a lot of very expensive comparisons.  Is this
> > correct?
>
> Possibly.

Is it not possible to have the tabling code do simple pointer comparisons in
some cases?
In the case at hand, the map() argument is something computed at the time
the service starts and remains constant throughout the run (we are talking
about weeks...). On the contents of the map, we have several functions/pred
which compute derived properties, sometimes not immediate and with those
computations often repeated....

My reasoning was that since those are constant over time, I might as well
memoise them;
A table lookup which does not do deep comparisons is going to be cheaper
than computing the properties.... And I'll only have to store the
effectively used key attributes....

Looks like I am wrong....

Would it be possible to hint at the compiler that, for a given predicate to
be memoised, one or several arguments are to be considered as constant?

> However, you might get a dramatic slow down even if the maps are
> all empty.
> For example, if the memo table becomes large, because you insert lots of
> different values into it, and your locality is otherwise small, then
> the memo table could drastically worsen your locality, and thus lead to
> dramatic slowdowns.

The slow down was so dramatic that the following theorem could almost be
proven :-)

    In theory, memoisation makes some non-terminating programs terminate;
    In practice, memoisation makes some terminating programs
non-terminating.

> In general memoization will only pay off if the amount of work done
> in constructing and checking the memo table is greater than the
> cost of the procedure calls that it saves.

Which means that such a pragma, which is very appealing because it allows
programming some aspects of your applications in a very declarative manner
(by expressing some computable relationship) and still having the
performance of not recomputing those relations over and over, is not of
practical use as it currently stands.  The alternative it to explicitely do
the tabling of the 'to be memoised' function in an application, this is more
complex to write and has got to be re-written every time (well, maybe
not...)

So for me, 'pragma memo' that is very efficient, is a need for developing
Mercury applications.

D.





--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------