[m-dev.] pprint performance

[Ralph Becket]

Kevin Glynn, Monday, 25 February 2002:
> 
> I know nearly nothing about the problem you are solving,  but looking
> at what you write below, isn't this really where laziness pays off?
> Things are only calculated by demand,  so only enough of the 
> internal data structures are calculated as needed to print each
> character?  Of course its a disaster if the whole representation needs
> to be calculated before you can print trhe first character,  but that
> can usually be avoided.
> 
> I think this is where explicit laziness doesn't work, you can't just
> make the outer call lazy, you havve to make all the internal parts
> lazy too. Too painful.

The problem is that when you pretty-print a term T you generally
do something like

	pretty_print(mark_up(T))

where mark_up converts an arbitrary term into a marked-up structure
showing where the various choice points are for the pretty_print
function.

Each part of T may well be marked up lazily, but as each part is
converted, the result becomes reachable (because it overwrites the
thunk) from the result of the call to mark_up.  Since pretty_print
has to traverse the whole marked up term, the garbage collector can't
actually collect anything of mark_up(T) until the pretty printer has
finished (it's all reachable data up to that point).  This is a disaster
if T is very large and/or contains a lot of sharing, so I'm *not*
convinced that laziness is the right answer at all (contrary to what I
thought when I hadn't thought too much about the problem!)

The next thing on my to-do list is to install GHC with Wadler's original
algorithm and see how well it handles very large terms.  I'm betting
that it's going to fall over just the same way my previous Mercury
version did.

Cheers,

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