[MLton] CML

[Matthew Fluet]

> > One  thing  I  never  understood  about  CML:  why is it that a single object
> > represents a bi-directional channel instead of having  a  separate  read  and
> > write  channel.   The advantage of the latter is that it makes it much easier
> > (and obvious) for the GC to eliminate threads that can have no effect.  As an
> > example,  if  the  write  end  of  a  channel  is lost (GC'd) then any thread
> > blocking on a read from the channel is garbage.  Because of  the  synchronous
> > aspect of channels, the same is true of the reverse situation.
> >
> > There  are  clearly times when you need a bi-directional connection, but that
> > can trivially be done by creating two channels and packaging the write end of
> > one and the read end of the other one.
> >
> > I  assume  that unless you are lucky, with the CML method, I will get threads
> > blocked for ever and never collected quite frequently, right?
>
> Yes, I believe it is true that you can end up with multiple threads
> blocked on a read of a channel and never collected, but it is not a
> trivial situation. When a thread blocks on a channel (read or write), it
> is added to the appropriate queue in the channel.  If the channel gets
> GCed, then all the blocked threads will be GCed as well.  (That is,
> everything will be GCed in a deadlock situation).  So, the situation you
> describe requires the channel to kept live by some active thread, but
> never writes to the channel or blocks reading the channel.

In thinking about this a little more, there is a general "problem" with
CML in that queues of blocked events are only ever cleaned if some other
thread touches the queue.  For a pathological example, consider a million
threads that all block choosing between a recv from a channel and a
timeout event.  If, the channel is kept alive but is never sent to or
received from, then even when all the million threads are enabled by the
timeout event, their old blocked threads will remain on the channel's
queue.

Note, MLton seems to have a real advantage here.  Even though those
million threads will stick around on the channel's queue, because MLton's
threads are essentially one-shot, once the threads are unblocked by the
timeout event and switched to, all of the threads on the channel's queue
will be Dead.  That means that while the GC will continue to walk the
channel queue, it won't trace into any MLton stacks, because the threads
are dead.

SML/NJ, on the other hand, will leave continuations on the channel's
queue.  And those continuations may keep alive a lot of data that is
really unreachable, because the associated transaction ID has been
cancelled.

(Although, I think this is a design problem that can be easily fixed.  The
transaction id datatype is always paired with some data (usually a CML
thread and maybe some associated data) that predicates as being either
still a valid transaction or a cancelled transaction.  If we made the
trans_id datatype an essentially an 'a option ref, then the paired data
could be held within the trans_id and would automatically become
unreachable when the transaction is cancelled.)