Monday, February 9, 2009

Equeue compared to Lwt

I feel like taking a break from Camlp4, so in this post I'll take a look at two libraries for asynchronous networking programming in OCaml: Equeue and Lwt. Each provides cooperative multithreading and asynchronous access to networking calls; each has protocol implementations built on top of it (e.g. Nethttpd for Equeue and Ocsigen's HTTP implementation for of Lwt). So why would you want to use one over the other? Let's start with an overview of each.

Equeue

An Equeue event system comprises a queue of events and a set of event handlers. A running event system just pulls events off the queue and passes them to the event handlers. You can think of a group of related handlers as a thread (the thread is blocked until one of its handlers is called; when the handler returns the thread yields) but there is no particular data structure tying them together.

The Unixqueue module specializes Equeue to the case where the source of events is the Unix select call. It adds the idea of resources, which are operations that may cause an event. For example, the operation Wait_in on some file descriptor can cause the event Input_arrived for that descriptor. A resource also has an associated timeout (the Timeout event fires if the timeout is exceeded). Unixqueue also adds a way to group resources and handlers; a group can be removed from the event system with one call, so everything associated with a thread can be cleaned up at once.

On top of the low-level event queue mechanism, Equeue builds engines, which package up some event handlers and some internal state with a particular interface:

type 't engine_state =
  [ `Working of int
  | `Done of 't
  | `Error of exn
  | `Aborted
  ]

class type [ 't ] engine = object
  method state : 't engine_state
  method abort : unit -> unit
  method request_notification : (unit -> bool) -> unit
  method event_system : Unixqueue.event_system
end
An engine runs for a while, then finishes with some value, fails with an exception, or becomes aborted. Code that's interested in the result of an engine can use request_notification to find out when the state of the engine has changed.

Equeue provides a number of engines for networking tasks (such as connecting to a socket), and also for hooking engines together in various ways. Maybe the most interesting one (when comparing to Lwt at least) is:

class ['a, 'b] seq_engine :
  'a #engine ->
  ('a -> 'b #engine) ->
  ['b] engine
which feeds the result of one engine into a function that creates another engine. Does this look familiar?

Lwt

Lwt provides no equivalent to Equeue's low-level event handling. But an Lwt thread is quite similar to an Equeue engine, in that it runs for a while then finishes successfully with a value or fails with an exception (there is no aborted state). However, the type 'a Lwt.t of threads returning values of type 'a is abstract; to implement your own thread you must build it out of the functions provided by Lwt. Here are some important ones:

val return : 'a -> 'a t
val fail : exn -> 'a t
You create an already-terminated thread with a value or exception with return and fail respectively. (Equeue has epsilon_engine which does essentially the same thing.)
val wait : unit -> 'a t
val wakeup : 'a t -> 'a -> unit
val wakeup_exn : 'a t -> exn -> unit
These functions give you a way to make threads that return only after some event occurs. A thread created with wait is blocked until woken either with a value or an exception. Any threads using its value block until it's woken. But how does a thread use another thread's value?
val bind : 'a t -> ('a -> 'b t) -> 'b t
This function feeds the result of one thread into a function that creates another thread, just like Equeue's seq_engine above. The important thing is that the value may not be available yet. In that case the function you give as the second argument is added to a notification list and called when the value arrives. This is similar to Equeue's request_notification, except that with Lwt notification is entirely under the hood: asking to be notified and getting the value of the thread are the same operation.

(Maybe you noticed that the type Lwt.t together with the functions return and bind form a monad. It would appear that the same is true of Equeue's engine, epsilon_engine, and seq_engine, although I haven't checked that they satisfy the monad laws.)

The Lwt_unix module provides a set of Unix I/O functions that match many of the ordinary ones in the Unix module, but return Lwt.t values (i.e. threads). In order to use the value you have to bind the thread, and possibly block until the value arrives.

Comparison

Lwt is a very beautiful library. The monadic interface encourages you to think about interacting threads in terms of values and dependencies, rather than states and callbacks. Lwt code can be very concise, and with the help of pa_monad, it can look pretty much just like straight-line code. Equeue engines require more machinery to implement (in particular, request_notification, although the engine_mixin class helps with that), and this increased overhead makes it less convenient to use threads in a fine-grained way.

Lwt is particularly nice with exception handling. In most cases, if a thread raises an exception it will be converted to a failing thread, rather than escaping the thread machinery (as would happen in an Equeue engine if you don't explicitly catch the exception). Unfortunately there are places this doesn't work (in order to support constant-space tail calls), which can be surprising.

Equeue, on the other hand, gives you much better low-level control. Lwt gives you the monadic equivalent of a blocking threads interface: you get a read call that blocks until data is ready. Equeue separates notification of events from the actual I/O operations, so if you want to do something other than read when data is ready you can. You can also remove a resource, to indicate that you're no longer interested in its events. With Lwt once a thread is waiting to read, it keeps waiting until data is ready or the channel is aborted (using Lwt_unix.abort). This covers the common case where you want to close the connection on a timeout, but more complicated things are harder. In addition, since you always care about timeouts when doing network programming, it's convenient that Equeue builds them into the resource interface.

Equeue may be more efficient in low-level ways: for instance, if you're going to repeatedly read a socket you can leave the resource and handler in the event system; in Lwt every read adds a new action (the Lwt equivalent of a handler). But I bet this doesn't matter almost all the time.

So which one?

Lwt definitely wins on clarity, simplicity, and concision for higher-level coding. Equeue wins if you need low-level control, or possibly if you need the absolute most performance.

Another factor, however, is that Equeue works with the rest of Ocamlnet, and in particular the ONC RPC implementation and the awesome Netplex server framework. For this reason I've adapted Lwt to run on top of Equeue, in the lwt-equeue library that comes with orpc. (I hope to do another orpc release soon with the latest version of lwt-equeue; in the meantime you can try the trunk version.) With lwt-equeue it's straightforward to mix Lwt and Equeue code, so you can use each when it's most appropriate.

(By the way, Jérôme Vouillon's ML Workshop paper on Lwt is really nice; it explains some tricky details of the implementation.)

Next time back to Camlp4.