[mercury-users] tabling

[Zoltan Somogyi]

On 28-Nov-2000, Peter Ross <peter.ross at miscrit.be> wrote:
> :- 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?

Yes. Entering the map in the table is O(n); the work that is_some_condition
is doing is probably O(log(n)). This is why you get a dramatic slowdown.
Even if is_some_condition had complexity O(n) to begin with, on each call
you traverse many trie nodes and create others, and so (depending precisely
is_some_condition works) its complexity with tabling may be O(n log(n)),
and the constant factor would almost certainly be much higher.

Tabling at the moment is only useful if the complexity of the procedure
being tabled grows significantly more quickly than the total sizes of its
arguments.

To remove this limitation, you need hash consing. I intend to work on that
during the Christman holidays.

Zoltan.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------