About Haskell Thread Model

[Jan-Willem Maessen]

William Lee Irwin III <wli at holomorphy.com> discusses SMP threading issues:
> On Mon, Oct 13, 2003 at 12:02:52PM -0400, Jan-Willem Maessen wrote:
> > In reality you probably want to use some sort of thin lock / fat lock
> > approach a la Java.  Is the location thinly locked?  If so, CAS in a
> > fat lock instead, then wait on that.  Now update requires a CAS as
> > well, to see whether the thin lock was fattened.  If so, the fat lock
> > must be unlocked and deallocated.
> > Naturally, we'd like to keep track of unshared objects so we can avoid
> > any kind of complicated update protocol in the common case.  This
> > requires the implementor to establish a careful and clear contract
> > between the compiler, the GC, and the thread scheduler.
> 
> This sounds very heavyweight. I'd be tempted to start looking at
> lockless algorithms from the outset if you need to synchronize such
> basic/frequently exercised operations.

The above is about as lockless as you can get.  The reader can read
the object header, and only does fancy stuff if the object is
uncomputed.  The writer can fill the object at the cost of a memory
barrier (if stores are not ordered) and a compare and swap.  All the
rest of the complexity is to get blocked threads to play nicely with
the OS.  

It's possible that the futex abstraction in Linux would be really
helpful here; I don't know it well enough to say.  Ideally the OS
would give us a primitive that says "block this thread until this
location changes value, but don't expect the OS to be told when that
happens"---in which case we need only a memory barrier, and not a CAS.
In this latter case, if we have a machine with ordered stores we don't
need any special operations at all, and thus we need not make a
local/global distinction (though it may still be useful for
multiprocessor GC).

> [Re: multiprocessor GC]
> I've not really heard horror stories per se, but indirectly I've gotten
> the idea that the JVM's out there spent a lot of time on this. I suspect
> some of the Java userspace lock contention I've seen was related to GC.

Possibly.  Mostly it involve a lot of development effort to make it
correct, and still more dvelopment effort to tune it so that it
performs reasonably.  Again, because Haskell is allocation-intensive
it's likely to require more intensive tuning, and probably a different
GC strategy (for example, copying GC looks more attractive).

-Jan-Willem Maessen
jmaessen at alum.mit.edu