[m-dev.] pprint performance

[Peter Schachte]

On Sat, Feb 23, 2002 at 11:49:11AM +1100, Ralph Becket wrote:
> The real problem now is that converting a term to a doc form suitable
> for pprint__write expands the size of the term significantly (every pair
> of brackets costs about eight words of storage and every comma six or
> seven words of storage.)  One would expect that in most very large terms
> there will be a significant amount of sharing; unfortunately all this
> sharing is lost in the conversion process.  This can lead to an
> exponential blow-up in the memory footprint of formatted terms.
> 
> I've tried some experiments making judicious use of pragma memo, but
> this is not a solution (it actually makes matters much worse.)

Do you have any insight into why memoing doesn't work?  Do your test
cases have high degrees of fan-in that would benefit from memoing?

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.  When a large
subterm is revisited, all of its subterms will be, too, so even if the
root of the revisited subterm has been flushed from the cache, chances
are some of its subterms or subsubterms won't be, so you'll still get
much of the benefit with a fixed space overhead and a time overhead
linear in the size of the term.  (Though for it to be a linear time
overhead, you have to use pointer hashing and equivalence checking on
subterms.)

> A reasonable solution is probably to use some form of lazy evaluation,
> whereby the term conversion is done on-demand by the write procedure.

I don't see how this would help if the whole term is to be printed; I
would think it would just add an extra data structure to be built for
each subterm.  The only benefit I would expect would be the automatic
caching of already computed values, which is why I would expect
caching to be better.

Maybe the biggest improvement would be had by deforesting.  How far is
the Mercury deforestation facility from being able to handle 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
--------------------------------------------------------------------------