[m-dev.] pprint performance

[Ralph Becket]

Ralph Becket, Monday, 25 February 2002:
> 
> Success!  The combination of mark-up on demand and direct output means
> the pretty printer now runs with a very small footprint.  The
> performance cost is relatively small, but does mean that it scales to
> truly enormous structures.

Printing balanced binary trees to /dev/null we get the following from
ceres (1.6GHz P4, 256 KByte cache, 512 MByte RAM):

2047 node tree (branching factor 2, depth 10)
[Time: +0.139s, 0.139s, C Stack: 0.230k,
#GCs: 51, Heap used since last GC: 9.203k, Total used: 128.000k]

8191 node tree (branching factor 2, depth 12)
[Time: +0.499s, 0.499s, C Stack: 0.230k,
#GCs: 194, Heap used since last GC: 56.875k, Total used: 128.000k]

32767 node tree (branching factor 2, depth 14)
[Time: +1.959s, 1.959s, C Stack: 0.230k,
#GCs: 565, Heap used since last GC: 113.742k, Total used: 192.000k]

131071 node tree (branching factor 2, depth 16)
[Time: +7.269s, 7.269s, C Stack: 0.230k,
#GCs: 1754, Heap used since last GC: 16.914k, Total used: 192.000k]

524287 node tree (branching factor 2, depth 18)
[Time: +25.699s, 25.699s, C Stack: 0.230k,
#GCs: 6007, Heap used since last GC: 19.312k, Total used: 192.000k]

2097151 node tree (branching factor 2, depth 20)
[Time: +105.250s, 105.250s, C Stack: 0.230k,
#GCs: 24508, Heap used since last GC: 6.094k, Total used: 192.000k]

8388607 node tree (branching factor 2, depth 22)
[Time: +379.070s, 379.070s, C Stack: 0.230k,
#GCs: 82943, Heap used since last GC: 19.016k, Total used: 192.000k]

33554431 node tree (branching factor 2, depth 24)
[Time: +1401.359s, 1401.359s, C Stack: 0.230k,
#GCs: 203312, Heap used since last GC: 166.656k, Total used: 260.000k]

Hopefully pretty printing a 34 million node structure in under 25mins is
enough to satisfy most users.

(N.B. while the number of GCs used in each case may be large, the amount
of tracing a generational collector will have to do after the first is
small.  Printing smaller terms is cheap: sub-millisecond for terms with
less than 64 nodes, under 10 ms for terms with 512 nodes.)

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