Concurrency

oleg at pobox.com oleg at pobox.com
Wed Apr 5 01:33:02 EDT 2006


It would be really great if the concurrency portion of Haskell' did
not outlaw light-weight threads implemented via delimited
continuations (similar to those in the ZFS system). Such threads are
cooperative: a thread runs until it requests service from a
`supervisor' (yield() being one of such requests). The advantage of
these threads is that they are lightweight, that the scheduler becomes
expressible in the Haskell itself (and so each application can have
its own scheduler, with or without priorities, with or without
sophisticated resource-aware scheduling), and such threads have a
natural transactional semantics. In the ZFS project threads can only
do IO that is explicitly provided for them, and nothing else.  Or, to
be more precise, threads are statically prevented from any IO; they
must request IO from the supervisor, which then decides if to satisfy
the request, and when. Due to the natural 'copy-on-write' semantics,
transactional memory becomes trivial; exceptions require no roll-back
because no global state is modified unless the explicit commit is
requested.  Incidentally, the cooperative nature of lightweight
threads does not preclude preemption: because all processing occurs in
a monad, we can just as well make a monad that issues yield() after
a certain number of 'binds'. Still, it will be nice if yield() per se
were available, so users could chose the strategy for themselves.

Interacting with foreign calls is indeed a problem: it is imperative
that foreign calls be non-blocking. ZFS had to implement select(2)
binding to get the non-blocking network IO. 

Fortunately, asynchronous behavior is possible for *any* operating
system call, under generous assumptions (which hold for Linix and
BSD systems, among others):

	Lazy Asynchronous I/O for Event-Driven Servers
	http://www.usenix.org/events/usenix04/tech/general/elmeleegy.html

>From the abstract:
``We compare the performance of web servers implemented using LAIO to the
  performance obtained with previous interfaces. For workloads with an
  appreciable amount of disk I/O, LAIO performs substantially better than
  the alternatives, because it avoids blocking entirely. In one such case,
  the peak throughput with LAIO is 24% higher than the next best
  alternative. For in-memory workloads it performs comparably.''


It does seem to be a general consensus that events are faster than
threads, but more difficult to program [just because first-class
delimited continuations are not available for all languages,
IMHO]. Here's a summary of HotOS X presentation that touches on the
topic:

** Making Events Less Slippery with eel
Ryan Cunningham and Eddie Kohler,
University of California, Los Angeles
HotOS X: Tenth Workshop on Hot Topics in operating systems. 
Santa Fe, New Mexico, June 12-15, 2005.
Cited from the summaries in USENIX ;login: v.30, N5, p.67, 2005.
http://www.usenix.org/publications/login/2005-10/openpdfs/hotos05.pdf

''This talk continued the old debate concerning threads and events.
Events are fast but difficult to program. The speaker described eel, a
programming tool designed to simplify programming with
events. [Basically, a GUI for losers. Should use better languages!]

eel uses program analysis techniques to improve programmability while
preserving the event model, and provides the libeel event library,
visualization, and debugging tools.  Programming events is hard
because it is difficult to understand the flow of the program and
difficult to debug. eel's visualization tools make it easy to
visualize the control flow, and the debugger allows you to step
through each program flow separately; you follow the callbacks
related to the same connection, so each flow of related events appears
sequential. The speaker concluded that events don't need to be hard to
program. You can use simple tools to extract program control flow
and to help with visualization, verification, and debugging.

Margo Seltzer pointed out that while eel helps clarify the event-
based program after it's written, it does not appear to help with the
actual writing of the program. The speaker responded that by allowing
the programmer to visualize newly written code, eel does make writing
easier. Margo was not convinced that using events is worth all this
trouble. The speaker said that using events is preferable because they
are much faster. Pei Cao responded that based on her experience of
designing large software projects people use both threads and events.
Events are a pain, so people use them only when performance is
absolutely critical, which does not happen very often.''


More information about the Haskell-prime mailing list