[MLton] callcc and space use

[Vesa Karvonen]

On Jan 23, 2008 10:37 AM, Florian Weimer <fweimer at bfk.de> wrote:
> * Vesa Karvonen:
>
> > Just curious, since you specifically mention using callcc to suspend
> > and resume computation (rather than to fork computation), I wonder
> > whether there is a reason to use MLton's callcc
> > (http://mlton.org/MLtonCont) rather than MLton's threads
> > (http://mlton.org/MLtonThread), which are expressive enough for
> > suspending and resuming computation.  I ask about this, because,
> > AFAIK, MLton's callcc and throw are implemented on top of MLton's
> > threads by copying the stack and performing thread switches.  IOW,
> > using just MLton's threads (i.e. switch) for suspend and resume would
> > likely be considerably more efficient.
>
> I think it's the other way round.

I'm not sure what you are referring to here (efficiency or the way
things are implemented or something else).

My statement above about the way continuations are implemented is
somewhat inaccurate.  Both threads and continuations are implemented
on top of primitive threads.  Both callcc and throw copy the primitive
thread (time proportional to stack size) and then perform a primitive
thread switch (I assume constant time).  Thread switch does not
require copying primitive threads, except in the special case of a
newly created thread.

> But new threads are copied from a specific thread with an empty
> stack, which is faster than copying the current thread's stack.

Yes, threads are more efficient in this respect as well.  Creating a
new thread means that when (if ever) the new thread is switched to for
the first time, a "base" stack is copied.  Except for that special
case, switching between threads does not require copying stacks.
OTOH, both callcc and throw always copy the stack.  So, if you perform
suspend+resume using callcc+throw, you'll copy the stack twice.

> However, the function to call is passed to the nascent thread in a
> global variable (with suitable locking), and this results in unnecessary
> contention in a parallel environment.

True.  OTOH, note that callcc/throw also use the equivalent of a
global variable.  The call to Thread.copyCurrent saves the copy in a
field in GC state, which is then retrieved by calling Thread.savedPre.
 Both callcc and throw also perform locking (atomicBegin - atomicEnd).

In summary, assuming my understanding of the implementation is
correct, using callcc+throw to spawn a new thread and perform N
suspends and resumes takes O((N+1)*S) time, where S is the average
stack size, while the same with threads takes O(N+1) time.

> It seems that there is some room for improvement here.

Looks like it, although I'm not sure how difficult it might be.

-Vesa Karvonen