Re: Threads

[Jonathan Bachrach <jrb@xxxxxxxxxx>]

Neel Krishnaswami <neelk@alum.mit.edu> writes:

> First off, GOO is very sweet. I like it. 
> 
> jrb wrote:
> >
> > we have discussed the possibility.  i think the general thought is to
> > not support native threads but to instead support threads built out of
> > upward continuations (i.e., cooperative threads).  full parallelism
> > would be built instead out of more insular processes.  the problem of
> > making user programs thread safe and the overhead of system thread
> > safety are thought to be too high a price to pay for parallelism.
> 
> What exactly is the price? 

it's not so much the price to the implementor but to the users trying
to get correct/safe concurrent code running.  perhaps another regime
is in order (such as in erlang where threads can't directly read/write
data from each other)?  the thinking goes that it's too easy to shoot
yourself in the foot in something like java because it gives you a
false sense of security (and atomicity).  what are your thoughts on
this?

> To me, it looks like the main difficulties are:
> 
>   o Can updating the subtype table be made thread-safe?
>   o Can adding methods to a gf be made thread-safe?

and collection code (e.g., vec and tab) and the compiler itself (as
discussed in a previous mail message).

> Even with full parallelism, you can make each of these thread-safe at
> the cost of an extra indirection at each gf dispatch and each subtype
> test. You can store a pointer to a pointer to the relevant data
> structures, and then when it's necessary to update them you can make a
> modified copy, and then make the update with an atomic compare-and-
> swap. The CAS would need a tiny bit of per-architecture assembly, but
> fortunately the CILK project (http://supertech.lcs.mit.edu/cilk/) has
> stealable code to do that for x86, IA64, SPARC, Alpha, PowerPC and
> MIPS. I dunno how much of a hit the extra indirection would inflict,
> though I'd guess it's fairly modest.

yeah, we did all of this in fun-o-dylan.  it's not that bad, but it
does cost every user even in the single threaded case.  there are
certain knock on effects that aren't obvious.  i'm definitely up for
the work, but i'm wondering whether there's a better way, a way that's
more pay as you go and provides a more realistic model.  certainly,
there is research concerning global analysis to know when and/or where
a program is single threaded in such a way as to inform optimizations
to remove these overheads, but this might be difficult in an
interactive environment.  in fun-o-dylan, we tried to at least to hide
the costs in the less frequent paths such as table writes instead of
reads etc.

> On a related note, the C-- people have written a paper that identifies
> a continuation discipline that enables you to write exceptions and
> coroutines/threads, but is compatible with a stack implementations. If
> you allow continuations with a dynamic-extent (like Dylan/GOO
> continuations), but permit them to be called multiple times (unlike
> GOO), then you can write coroutines but can still use a stack. See:
> 
>   Featherweight Concurrency in a Portable Assembly Language. Ramsey and
>   Peyton-Jones. http://citeseer.nj.nec.com/ramsey01featherweight.html
> 
> I guess you could implement this by compiling into CPS and then
> allocating continuations using alloca() and occasionally cleaning up.

jonathan