[MLton] callcc and space use

[Daniel Spoonhower]

Vesa Karvonen wrote:
> On Feb 6, 2008 8:49 PM, Daniel Spoonhower <spoons at cs.cmu.edu> wrote:
>> After some investigation, I think I have an answer to my problem.  In
>> the end, it seems the problem had nothing to do with callcc, but with
>> part of the analysis used in the reference flattening optimization
>> (http://mlton.org/RefFlatten).
> [...]
> 
> Interestingly, the patch eliminates the space leak from the two test
> cases you gave earlier, but does not remove it from a modified version
> of your second test case.  The modified version uses threads rather
> than continuations.  I wrote it (back when you sent the test cases) to
> see whether or not continuations make it simpler or not (IMO, they do
> not; the version using threads is simpler, IMO).  (The modified
> version has been intentionally kept close to the original to reduce
> diffs.)  See the attachment.  At any rate, the space leak definitely
> seems to be caused by a bug in MLton.  I do not know enough about
> RefFlatten to comment on your patch.  Perhaps RefFlatten is still not
> conservative enough.

I took a closer look at Vesa's version of the code (the one using 
threads).  The leak here goes away if I add the explicit GC at each 
iteration.  I can't find any difference in the output of RefFlatten 
between the version with the GC and the one without, so I don't think 
the problem is there.  In fact, there isn't anything in the generated 
code that would lead me to expect the version with an explicit GC to use 
less space (in terms of the maximum size of live objects).

Most (>99%) of the heap at the high-water mark is tied up with stack 
objects.  I think the difference in performance is caused by the fact 
that when a GC occurs, it shrinks non-active stacks (i.e. it only 
reserves space for the portion of the stack that is in use).  When there 
are many threads and GCs are infrequent, much of the heap is tied up 
with the unused portions of these stacks.  If I disable the thread 
shrinking (by setting thread-shrink-ratio to 1.0), the performance of 
the two thread-based versions is about the same.  (The version with 
explicit GCs reports slightly higher "max live" as I would expect since 
the version without GCs may not sample at the high-water mark.)

Though it doesn't affect any of the cases we've been discussing, I 
should point out that I don't think my patch to ref-flatten.fun from 
last week is conservative enough.  If my reasoning for recursive 
datatypes is correct, then mutually recursive datatypes should also be 
considered "large" types (since a pointer to a mutually recursive 
datatype constructor may reach an unbounded portion of the heap).


--djs

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 252 bytes
Desc: OpenPGP digital signature
Url : http://mlton.org/pipermail/mlton/attachments/20080211/2788d0a6/signature.pgp