[MLton] More on parallelism

[Eric McCorkle]

On Dec 4, 2006, at 3:41 PM, Matthew Fluet wrote:

> (Talk about parallel implementation)

I can't say much about the garbage collection, my background being in  
OS.  However, it's probably a better idea to do an 1:1 (aka N:N)   
thread model for the following reasons:

- Presumably, the pthread library (or other OS-specific library) will  
also be doing some sort of multiplexing, though maybe not.  The M:N  
model has fallen out of favor, and if I'm not mistaken, even Solaris  
(the originator of it) has abandoned it for 1:1.  What we don't want  
is both the thread library and the ML system doing M:N...

- The C stacks will be allocated per call to pthread_create (or  
whatever).  There needs to be one C stack per MLton thread.  Now,  
pthreads allocates C stacks with malloc, so that could be an issue too.


As for garbage collection, how viable is this?  One thread does  
garbage collection.  Most of the time it waits on a condition  
variable.  All other threads share one huge heap.  When they run out  
of space, they signal the garbage collector.  The real challenge is  
that every thread would have to be stopped before the collector could  
run, I would think.  Again, I'm not very familiar with garbage  
collection algorithms.

> This would actually be fairly easy; one would just pattern match on  
> the existing Ref primitives.  The semantics of cmpSet and cmpSwap  
> need a little thought when 'a isn't a primitive type, though it  
> presumably is pointer equality on boxed types.  There are various  
> places where one would or wouldn't want flattening of atomic refs  
> into containing data structures.  But, otherwise, these primitives  
> would just flow through the entire compile and be emitted by the  
> codegen as either the appropriate C function call or the  
> appropriate assembly code.
>

For anything bigger than a word it would have to be a pointer.   
Otherwise the atomic instructions won't work.  An atomic integer  
(which would behave more like an int reference) would probably be a  
good idea too.

For lock-free lists, you'll need a "marked" reference.  This can be  
implemented easily by using the low bits, which for pointers are  
always 0 as the mark.

-- 
Eric McCorkle,
Brown University
CS Graduate Student