A Language-based Approach to Unifying Events and Threads – Li and Zdancewic, 2006

So far in this mini-series we’ve seen that thread and event-based models are duals, that threads are a bad idea – you should really be using events, and that events are a bad idea – you should really be using threads.

What if we could combine the two models and bring together the deadlocks, data races and corruption of threads with the hard to understand control flow of events? 😉 Or, if we applied the techniques wisely, the easy to follow control flow of the thread-based approach, with the natural way that events model some domains. I think the latter is more what the authors had in mind!

The goal is to design a software library that provides two different abstractions for application-level threads: the thread view, which allows per-thread code be written in the natural, imperative, multi-threaded style, and the event view, which allows the threads be passively manipulated by the underlying scheduler in an abstract, type-safe way.

…

This dualized model gives the best of two worlds: the expressiveness of threads and the customizability of events.

After briefly comparing event and thread-based models, the authors go on to present a unified model implemented in Haskell: “Our experience shows that Haskell is a reasonable language for building scalable systems software; it is expressive, succinct, efficient and type safe; it also interacts well with C libraries and APIs.”

The primary advantage of the thread model is that the programmer can reason about the series of actions taken by a thread in the familiar way, just as for a sequential program…. Event-driven programming, in contrast, is hard. The control flow graph has to be decomposed to multiple event handlers and represented as some form of state machines with explicit message passing or in continuation-passing style (CPS).

Event-driven programs however are ‘usually more flexible and customizable,’ and are a good match for interrupt-driven systems. Note that the description of ‘event handlers, state machines, and explicit message passing’ is very reminiscent of the actor model. The CPS style evokes callbacks and promises.

So how do Li and Zdancewic bring the two together?

• Monads provide the thread abstraction by defining an imperative sub-language of Haskell with system calls and thread control primitives
• Higher-order functions provide the internal representation of threads in continuation-passing style
• Lazy data structures provide the event abstraction, which is a lazy tree that represents the trace of system calls generated by threads.

The goal is to design a monad that provides a thread abstraction, so the programmer can write multi-threaded code using the overloaded “do”-syntax with a set of system calls. The implementation of this monad is tricky, but the details are hidden from the programmer.

For example:

[code lang=text]
sock_accept server_fd do {
new_fd <- sys_nbio (accept server_fd);
if new_fd > 0
then return new_fd
else do {
sys_epoll_wait fd EPOLL_READ;
sock_accept server_fd;
}
}
[/code]

(If you’re not familiar with reading Haskell code, the semi-colon separated statements in the do blocks provide elegant syntactic sugar for sequential composition of functions).

By designing thread control primitives as monadic combinators, the monad interface can be used as an abstraction for multi-threaded programming, because it provides a way of hiding the ‘internal plumbing’ needed to write programs in CPS style.

Here’s an example of a simple recursive event loop:

[code lang=text]
worker_epoll sched =
do {
results <- epoll_wait;
mapM (writeChan (ready_queue sched)) results;
worker_epoll sched;
}
[/code]

(case statements can be used to select among multiple possible events).

This event-driven architecture is similar to that in SEDA, but our events are finer-grained: instead of requiring the programmer manually decompose a computation into stages and specify what stages can be performed in parallel, the event-driven scheduler automatically decomposes a threaded computation into fine-grained segments separated by system calls. Haskell’s type system ensures that each segment is a purely functional computation without I/O, so such segments can be safely executed in parallel.

A web server is implemented to assess the programming model and performance of the solution.

Not only is the multi-threaded programming style natural and elegant, but the event-driven architecture also makes the scheduler clean. The scheduler, including the CPS monad, system call implementations, event loops and queues for AIO, epoll, mutexes, file-opening and exception handling (but not counting the wrapper interfaces for C library functions), is only 220 lines of well-structured code.

Performance-wise the authors report that ‘in our experience Haskell programs, while slower that C programs, are not orders of magnitude slower.’ In their tests, the implementation performed favourably when compared to the Linux Native-POSIX Thread Library (NPTL) and against Apache for disk-bound workloads. Introducing Haskell STM transactions made the solution slower than C, but this disadvantage becomes less significant as more processors are introduced.

In exchange for performance, Haskell delivers many features that simplify program development, including a very expressive static type system, type inference, lightweight closures, garbage collection, and convenient syntax overloading. We heavily use these features in our thread library implementation; it might be possible to implement the unified concurrency model in a general-purpose language lacking some of these features, but the results would likely be cumbersome to use. Nevertheless, it is worth investigating how to apply our approach in more mainstream languages like Java.

Tomorrow we’ll look at a paper that reports on experiences trying to do exactly that.

The bottom line:

Events and threads should be combined into an unified programming model in general-purpose programming languages. With proper language support, application-level threads can be made extremely lightweight and easy to use. Our experiments demonstrate that this approach is practical and our programming experience suggests that this is a very appealing way of writing scalable, massively concurrent software.