[mercury-users] tabling

[Fergus Henderson]

On 28-Nov-2000, Peter Ross <peter.ross at miscrit.be> wrote:
> I have a question about 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.

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.

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.

You could try profiling your application's time and heap allocation
using the Mercury profiler, and seeing how much of the time and
heap allocation is spent in the table_* routines from the table_builtin
module (or formerly from the private_builtin module).
The Mercury compiler implements tabling by doing a source-to-source
(or actually HLDS to HLDS) transformation that inserts calls to those
routines.  You can use the `--dump-hlds tabling' option to show the
code that results after that transformation.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
                                    |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------