[MLton] callcc and space use

[Matthew Fluet]

On Wed, 20 Feb 2008, Vesa Karvonen wrote:
> On Thu, Feb 14, 2008 at 5:09 PM, Matthew Fluet <fluet at tti-c.org> wrote:
> [...]
>>  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.
>
> Sounds reasonable, but, even if it might not be optimal for all cases,
> I think that it would be least surprising to have a default resizing
> policy that ensures that the reserved stack space is not more than a
> constant factor of the used space.  Otherwise it would not be
> difficult to construct programs that appear to have a space leak.

True.  That has the nice property that successive GCs can't free up more 
than a constant factor of space used by stacks.  ('Course, if there are 
O(n) stacks (rather than O(1)), then successive GC's will appear to free 
up O(n) space, but still a constant factor per stack.)

>>  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?
>
> I think that just a hard limit of 4*used wouldn't be enough, because
> then long lived paused threads would never be minimized.

O.k.  But, that is a stronger property than simply ensuring that the 
reserved stack space is not more than a constant factor of the used 
space.

I sketched out the following as a possible resizing policy, which gives 
some more controls while trying to maintain the current behavior of 
single-threaded programs:

size_t sizeofStackGrow (GC_state s, GC_stack stack) {
   size_t res;

   res = max ((size_t)(s->controls.ratios.stackCurrentGrow * stack->reserved),
              sizeofStackMinimumReserved (s, stack));
   return res;
}
size_t sizeofStackShrink (GC_state s, GC_stack stack, bool current) {
       size_t reservedMax, reservedShrink, reservedMin, reservedNew;

       if (current) {
         /* Shrink current stacks. */
         reservedMax =
           (size_t)(s->controls.ratios.stackCurrentMaxReserved * stack->used);
         size_t reservedPermit =
           (size_t)(s->controls.ratios.stackCurrentPermitReserved * stack->used);
         reservedShrink =
           (stackReserved <= reservedPermit)
           ? stack->reserved
           : (size_t)(s->controls.ratios.stackCurrentShrink * stack->used);
         reservedMin = sizeofStackMinimumReserved (s, stack);
       } else {
         /* Shrink paused stacks. */
         reservedMax =
           (size_t)(s->controls.ratios.stackMaxReserved * stack->used);
         reservedShrink =
           (size_t)(s->controls.ratios.stackShrink * stack->reserved);
         reservedMin = stack->used;
       }
       reservedNew =
         alignStackReserved
         (s, max(min(reservedMax,reservedShrink),reservedMin));
       /* It's possible that reservedNew > stack->reserved for the
        * current stack if the stack invariant is violated.  In that
        * case, we want to leave the stack alone, because some other
        * part of the gc will grow the stack.  We cannot do any growing
        * here because we may run out of to space.
        */
       assert (current or reservedNew <= stack->reserved);
       reservedNew = min (stack->reserved, reservedNew);
       return reservedNew;
}

with the following defaults:

   s->controls.ratios.stackCurrentGrow = 2.0;
   s->controls.ratios.stackCurrentMaxReserved = 32.0;
   s->controls.ratios.stackCurrentPermitReserved = 4.0;
   s->controls.ratios.stackCurrentShrink = 0.5;
   s->controls.ratios.stackMaxReserved = 8.0;
   s->controls.ratios.stackShrink = 0.5;

The difference from the current policy is that both the current and paused 
stacks have a maximum reserved size that is a ratio of the used size.
The other difference is that a lot more ratios can be set by runtime 
options.