[MLton] callcc and space use

[Vesa Karvonen]

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

-Vesa Karvonen