William Lee Irwin III <wli@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@alum.mit.edu