[MLton] callcc and space use

[Matthew Fluet]

On Thu, 14 Feb 2008, Vesa Karvonen wrote:
> On Feb 14, 2008 5:11 AM, Matthew Fluet <fluet at tti-c.org> wrote:
>> I think I agree with Dan here.  MLton's default thread shrinking policy is
>> to attempt to halve the reserved size of the stack each time a stack is
>> live at a garbage collection.  [...]
>>
>> [...] In both versions, the "myrev" function calls "copy", which is a non-tail
>> recursive function.  Hence, "myrev" grows the stack proportional to the
>> size of the input list.  However, once the "copy" is done, the used stack
>> space is quite small.  In the callcc version, "fork" uses callcc and
>> copies only the used stack. [...] In the thread version, "fork" uses switch
>> and holds a reference to the current stack (with a large reserved size). [...]
>>
>> Perhaps a more aggressive stack resizing policy should be used when the
>> used/reserved ratio is very low.
>
> Interesting...  I think that something simple like allowing the
> reserved stack size to be at most the used stack size multiplied by a
> suitable factor (e.g. 4), which is larger than the factor (e.g. 2)
> used to grow/shrink the stack, should do the trick.  This should
> maintain the amortized linear time complexity of pushing/popping the
> stack and ensure that the (total) unused stack space is at most a
> constant factor of the used stack space (after a complete GC).

There was a (short) discussion of stack resizing policy a few years ago:
   http://mlton.org/pipermail/mlton/2004-April/025297.html

I suspect that it will be difficult to have a one-size-fits-all policy. 
When shrinking is too aggressive, you pay to grow the stack when a stack 
is resumed.  When shrinking isn't aggressive enough, you pay in space and 
GC time for the wasted space.  If you have a small number of preemptively 
scheduled threads, then no thread is idle for too long, and it makes more 
sense to not resize stacks too aggressively.  If you have a large number 
of idle threads, then it makes sense to resize the stacks more 
aggressively.

On the other hand, your policy of requiring a paused stack to have have 
reserved <= 4 * used seems reasonable.  But, with that policy, does it 
matter whether there is the additional policy that we halve the reserved 
size each time a paused thread lives through a GC?

BTW, I also noticed that the stack resizing policy is only in effect for a 
copying GC (minor or major).  The mark-compact GC will not resize paused 
stacks, though I don't see why I couldn't.