[m-dev.] pprint performance

[Zoltan Somogyi]

On 25-Feb-2002, Ralph Becket <rafe at cs.mu.OZ.AU> wrote:
> The other problem is that (I suspect that) memoing is currently hash
> table based rather than trie based, so every subterm of the term being
> marked up will be recursively hashed...

No, it is trie based. We only use hashing for the builtin types: int, float,
string, since for these the trie is infeasible.

> > Maybe what is needed in this cas is a kind of partial memoing --
> > caching, really.  Dedicate a fixed amount of space to caching
> > previously computed values, and when a new cache entry is to be added,
> > just overwrite the old one with the same hash value.

Though we have talked about probabilistic tabling in the past, nothing
has been implemented. "Same hash value" doesn't make sense in the absence
of hashing.

What I think you need for this test is hash-consing, which would allow
terms to be tabled by address (which is constant time) rather than by value
(whose cost is linear in the size of the term).

In the meantime, have you tried putting the depth argument after the term
argument in your experiments with tabling? If the depth is first, then tabling
will make a copy of the term for every distinct value of the depth, which is
expensive. If the term is first, then tabling will make a copy of the depth
for every distinct value of the term, which is cheap.

Zoltan.
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------