[m-dev.] pprint performance

[Peter Schachte]

On Mon, Feb 25, 2002 at 12:31:46PM +1100, Ralph Becket wrote:
> Part of the problem is that the to_doc function keeps track of "how far"
> down a tree formatting has gone; if a given limit is reached then the
> subtree is simply formatted as "...".  "How far" is defined such that a
> right sibling is considered "further down" than a left sibling.  Memoing
> therefore keys on <Depth, Term> rather than just <Term>, hence any
> possible sharing based on <Term> alone is not going to be visible in the
> memo table.
> 
> [to_doc/1 simply calls to_doc/2 (the version with the depth limit) with
> a depth limit parameter of int__max_int.]

Maybe instead of using an integer depth you could use

	:- type depth_limit ---> none ; limit(int).

and write new predicates to decrement a depth limit and to check if
the limit has been reached.  Then when the depth is unlimited, the
depth limit argument is identical, so memoing should work.

Actually, you could probably be more efficient by making use of
information you can't tell mercury, so it can't use for optimization:
depth limits are non-negative.  So you can use -1 to mean 'none', and
use an int for depth limit.  This costs you an extra test every time
you decrement the limit, and every time you check if the limit has
been reached, but if it makes memoing work it'd probably be worth it.

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

Disaster!  If so, then forget memoing for this.


-- 
Peter Schachte              America may be unique in being a country which
schachte at cs.mu.OZ.AU        has leapt from barbarism to decadence without
www.cs.mu.oz.au/~schachte/  touching civilization.
Phone: +61 3 8344 9166          -- John O'Hara 
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------