I am a new learner of Haskell and I am interested in Haskell's concurrent model. Can somebody give me a brief intro about Haskell's thread model, like how the use-level threads are mapped to kernel thread and what scheduling mechanism that Haskell uses, or point me to some links or documents that I can learn from.
In the interpreter Hugs, all Haskell threads are run in one kernel thread. They are scheduled cooperatively; thread switches only take place when a function from the "Concurrent" module is called. In the currently released version of GHC, all Haskell threads are run in one kernel thread, too; however, thread switches can take place whenever memory is allocated --- and in Haskell, that means "almost always". The optimizer manages to compile a fibonacci function that doesn't allocate any memory, but in the real world, it's as good as real preemption. If you compile the bleeding-edge GHC from the CVS HEAD, you'll get something else; while "most" threads (those created using "forkIO") are still light-weight threads that are scheduled in just one kernel thread, you can also create threads that get their own operating system thread. This is solves all the problems that lightweight threads can have with foreign (i.e. non-Haskell) libraries. You should also note that no Haskell implementation currently supports SMP; even when multiple kernel threads are used, there is a mutual exclusion lock on the Haskell heap, so a multithreaded Haskell program will use only one CPU on an SMP system. I hope my answer was useful... Cheers, Wolfgang P.S.: If you want to do me a favour, you could tell your mail program not to send multipart or HTML messages to the list; they look terrible to people like me who get a daily digest from the mailing list.
On Sat, Oct 11, 2003 at 10:58:04PM +0200, Wolfgang Thaller wrote:
If you compile the bleeding-edge GHC from the CVS HEAD, you'll get something else; while "most" threads (those created using "forkIO") are still light-weight threads that are scheduled in just one kernel thread, you can also create threads that get their own operating system thread. This is solves all the problems that lightweight threads can have with foreign (i.e. non-Haskell) libraries. You should also note that no Haskell implementation currently supports SMP; even when multiple kernel threads are used, there is a mutual exclusion lock on the Haskell heap, so a multithreaded Haskell program will use only one CPU on an SMP system. I hope my answer was useful...
That's a painful-sounding state of affairs, though not entirely unexpected. It would be interesting to hear of "BKL breakup" efforts for Haskell runtime systems, though anymore I'm totally ignorant of what the devil is going on in userspace except database-only syscalls. -- wli
William Lee Irwin III wrote:
On Sat, Oct 11, 2003 at 10:58:04PM +0200, Wolfgang Thaller wrote:
You should also note that no Haskell implementation currently supports SMP; even when multiple kernel threads are used, there is a mutual exclusion lock on the Haskell heap, so a multithreaded Haskell program will use only one CPU on an SMP system. I hope my answer was useful...
That's a painful-sounding state of affairs, though not entirely unexpected. It would be interesting to hear of "BKL breakup" efforts for Haskell runtime systems, though anymore I'm totally ignorant of what the devil is going on in userspace except database-only syscalls.
I'm not sure I understand you. I found out that "BKL" refers to the "Big Kernel Lock" (in the Linux kernel), but I have no idea what "database-only syscalls" are. The reason why we currently do not take advantage of SMP is that the Haskell Heap is a shared data structure which is modified whenever a thunk (an unevaluated expression) is evaluated. Using synchronisation primitives like pthread_mutex_lock for every evaluation of a thunk would be deadly for performance. There is some old (1999) code in the GHC RTS that attempts this (using intel cmpxchg instructions for synchronisation), but it's currently "bitrotted" and I don't know how successful it was. Cheers, Wolfgang
William Lee Irwin III wrote:
That's a painful-sounding state of affairs, though not entirely unexpected. It would be interesting to hear of "BKL breakup" efforts for Haskell runtime systems, though anymore I'm totally ignorant of what the devil is going on in userspace except database-only syscalls.
On Mon, Oct 13, 2003 at 11:13:56AM +0200, Wolfgang Thaller wrote:
I'm not sure I understand you. I found out that "BKL" refers to the "Big Kernel Lock" (in the Linux kernel), but I have no idea what "database-only syscalls" are.
remap_file_pages() (lightweight mmap() for doing, say, 65536 mappings of distinct 32KB chunks of a file without kernel memory usage exploding) and async io syscalls are examples of database-only syscalls, that I'm aware userspace is doing largely from various kernel mailing list controversies. On Mon, Oct 13, 2003 at 11:13:56AM +0200, Wolfgang Thaller wrote:
The reason why we currently do not take advantage of SMP is that the Haskell Heap is a shared data structure which is modified whenever a thunk (an unevaluated expression) is evaluated. Using synchronisation primitives like pthread_mutex_lock for every evaluation of a thunk would be deadly for performance. There is some old (1999) code in the GHC RTS that attempts this (using intel cmpxchg instructions for synchronisation), but it's currently "bitrotted" and I don't know how successful it was.
cmpxchg and then taking a blocking lock sounds like the 2-tier locking supported with Linux' new futex system calls. I wonder how they chose to block in the older GHC RTS. -- wli
William Lee Irwin III <wli@holomorphy.com> asks about true SMP haskell.
On Mon, Oct 13, 2003 at 11:13:56AM +0200, Wolfgang Thaller wrote:
The reason why we currently do not take advantage of SMP is that the Haskell Heap is a shared data structure which is modified whenever a thunk (an unevaluated expression) is evaluated. Using synchronisation primitives like pthread_mutex_lock for every evaluation of a thunk would be deadly for performance. There is some old (1999) code in the GHC RTS that attempts this (using intel cmpxchg instructions for synchronisation), but it's currently "bitrotted" and I don't know how successful it was.
cmpxchg and then taking a blocking lock sounds like the 2-tier locking supported with Linux' new futex system calls. I wonder how they chose to block in the older GHC RTS.
This invariably proves tricky, even more so now that GHC effectively uses a many-to-one threading model (and where it may therefore be wrong to simply block the OS-level thread). In pH, which isn't quite haskell but has the same syntax and runs on multiple processors with a shared heap, we kludged: we simply called "yield" or "sleep" and kept spinning. We were actually using work stealing (with lock-free work queues as I recall) along with wait queues on empty locations, so we didn't sleep very often. Nonetheless, this did occasionally turn out to cause real performance problems. 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. Finally, the complexity of thunk update pales in comparison to the complexity of multiprocessor GC. In pH we punted on this issue---debugging a GC with per-thread allocation pools was hard enough. It killed us; thread performance didn't scale because GC didn't scale. Eager Haskell was designed with multithreaded shared-memory execution in mind, but I simply couldn't find the year or more it would take to build and debug a true multiprocessor GC---so it remains a uniprocessor implementation. -Jan-Willem Maessen jmaessen@alum.mit.edu
William Lee Irwin III <wli@holomorphy.com> asks about true SMP
cmpxchg and then taking a blocking lock sounds like the 2-tier locking supported with Linux' new futex system calls. I wonder how they chose to block in the older GHC RTS.
On Mon, Oct 13, 2003 at 12:02:52PM -0400, Jan-Willem Maessen wrote:
This invariably proves tricky, even more so now that GHC effectively uses a many-to-one threading model (and where it may therefore be wrong to simply block the OS-level thread). In pH, which isn't quite haskell but has the same syntax and runs on multiple processors with a shared heap, we kludged: we simply called "yield" or "sleep" and kept spinning. We were actually using work stealing (with lock-free work queues as I recall) along with wait queues on empty locations, so we didn't sleep very often. Nonetheless, this did occasionally turn out to cause real performance problems.
Abusing sched_yield() like this has been a performance problem with threading engines on Linux for a while, though usually as the middle tier of 3-tier locks as opposed to being the sole blocking primitive. 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. On Mon, Oct 13, 2003 at 12:02:52PM -0400, Jan-Willem Maessen wrote:
Finally, the complexity of thunk update pales in comparison to the complexity of multiprocessor GC. In pH we punted on this issue---debugging a GC with per-thread allocation pools was hard enough. It killed us; thread performance didn't scale because GC didn't scale. Eager Haskell was designed with multithreaded shared-memory execution in mind, but I simply couldn't find the year or more it would take to build and debug a true multiprocessor GC---so it remains a uniprocessor implementation.
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. -- wli
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
participants (3)
-
Jan-Willem Maessen -
William Lee Irwin III -
Wolfgang Thaller