Asynchronous C# and F# (III.): How does it work?

Some time ago, I started writing a series about the differences between the asynchronous model in F# (in Visual Studio 2010) and the asynchronous language extensions for C# proposed at PDC 2010. In the first article, I showed how both of the language features look and I highlighted a couple of differences. In the second article, I discussed the support for cancellation (available only in F#) and how the two models differ semantically (i.e. what are differences in the behaviour). However, I didn't talk about more techincal differences and, in particular, how is the asynchronous code compiled. We'll look at this topic today...

Although the C# asynchronous programming model is very similar to F# asynchronous workflows, the compilation looks quite different. The C# compiler uses a similar technique as when compiling iterators and creates a state machine, while the F# compiler uses an approach based on higher order functions (combinators) that's shared with (most) other computation expressions.

I won't discuss the syntax of F# asynchronous workflows or the C# asynchronous extensions in this article, so if you're new to one of these, here are links to other articles in this series:

• Asynchronous C# and F# (I.): Simultaneous introduction
• Asynchronous C# and F# (II.): How do they differ?
• Asynchronous C# and F# (III.): How does it work?
• Asynchronous C# and F# (IV.): Calling F# libraries from C# (not yet available)

Let's start by looking at the mechanism used in the C# compiler. If you already know how iterators work in C# 2.0, then you'll find it quite easy to understand. If you're not familiar with iterators, then don't worry - I'll make the explanation self-contained.

State-machine async compilation in C#

To explain the compilation, I'll use slightly simplified version of code that downloads the contents of a web page from the first article. I'll omit disposal using the using construct and also exception handling, so that I can show you (roughly) what the C# compiler generates in a few lines of code that can be explained. If you want to see the translation in its full beauty, then you can use Reflector. We'll look at the compilation of the following snippet:

var request = HttpWebRequest.Create(url);
var response = await request.GetResponseAsync();
var stream = response.GetResponseStream();

do {
  count = await stream.ReadAsync(buffer, 0, buffer.Length);
  temp.Write(buffer, 0, count);
} while (count > 0);

temp.Seek(0, SeekOrigin.Begin);
// (Some code at the end of the method omitted)
return Tuple.Create(title, html.Length);

Leaving synchronous code aside, the snippet starts by asynchronously getting HTTP response (see the first await keyword). Then it enters a loop in which it asynchronously reads data from a stream (second await point) and then synchronously writes the data to a memory stream. At the end of the loop, it does some (synchronous) processing of the downloaded data.

The C# compiler turns the above method into a class. All local variables of the method are turned into fileds of the class (I also added underscore to the name). This is needed, because when an asynchronous operation is started, the method that starts it returns, so all state needs to be stored on heap (in private fields).

The body of the method is divided into blocks where each block runs some synchronous code and then starts asynchronous operation. The operation is started in the background and the method that starts it returns immediately after starting it. (After returning, the current thread can do some other work, such as run another asynchronous computation, perform some GUI update etc.) The individual blocks are all compiled into a single method named MoveNext that contains a big switch that runs the next block (which is stored in a private field _state):

public void MoveNext() {  
  switch (this._state) {
  case Initial:
    // State when the method is called - start getting response
    this._request = HttpWebRequest.Create(this._url);
    this._awaitResponse = request.GetResponseAsync();
    this._awaitResponse.TrySetContinuation(this.MoveNextDelegate);
    this._state = GotResponse;
    break;

  case GotResponse:
    // Got response - obtain the stream and start the loop
    this._response = this._awaitResponse.GetResult<WebResponse>();
    this._stream = this._response.GetResponseStream();
    goto case LoopBodyStart:

  case LoopBodyStart: 
    // Loop body - start reading next chunk of data to a buffer 
    this._awaitRead = this._stream.ReadAsync(this._buffer, 0, this._buffer.Length);
    this._awaitRead.TrySetContinuation(this.MoveNextDelegate);
    this._state = LoopAfterRead;
    break;

  case LoopAfterRead: 
    // Downloading completed - read the result and start writing
    this._count = this._awaitRead.GetResult<int>();
    this._temp.Write(this._buffer, 0, this._count);
    // If the loop has not completed, go to the beginning
    if (this._count < 0) goto case LoopBodyStart;

    this._temp.Seek(0L, SeekOrigin.Begin);
    // (Some code at the end of the method omitted)
    this._state = Returned;
    this._result = Tuple.Create(this._title, this._html.Length);
  }
}

The code is a beautified version of what the C# compiler generates, but the structure of the method is the same. This method is used to generate task that's returned as the result of the async method, but that's not as interesting (you can discover that yourself using Reflector). The interesting aspect is how the code executes:

• At the beginning the state of the object (state machine) is Initial. When an asynchronous method is called, the program actually calls our MoveNext method, which executes the first case of the switch. It (synchronously) creates HTTP web request and then calls the GetResponseAsync method. The result of the call is a Task that starts running in the background.

  Immediately after the asynchronous operation is started, the method continues executing. It uses TrySetContinuation to register a handler that will be executed after the background operation completes and it configures the current state to run the next block (GotResponse) when the MoveNext method is called the next time.

• The MoveNextDelegate (set as a continuation in the previous step) refers to the MoveNext method, so when the first asynchronous operation completes, the shown method will be called again. The current state is GotResponse, so it will execute the second block. In the block, it gets the WebResponse value using GetResult and synchronously creates stream. Then it jumps to the start of the loop.

• The body of the loop is first executed from the GotResponse state. Later, it may be executed after the asynchronous operation inside the loop body completes in case when there are still some remaining data.

  Inside the body, we start the asynchronous operation ReadAsync, store the returned task in a local field and register a continuation to be called when the operation completes. Then we set the state to LoopAfterEnd, so that the next block is executed after the reading completes.

• In the LoopAfterRead state, we first get the result of the asynchronous operation and then write the data to a local stream. If there are some remaining data then the execution jumps back to the LoopBodyStart case and starts the next asynchronous operation. Otherwise, it processes the data and returns a result (by setting the _result field).

Probably the most important fact about the asynchronous execution described above is that the MoveNext method (which contains all code from our original method translated into a state machine) is executed repeatedly and it never blocks the calling thread. When running asynchronous operation, it schedules the operation and then returns. When the operation completes, it will use the provided continuation to run MoveNext again to perform the next step of the asynchronous computation.

Combinator based compilation in F#

The way F# asynchronous workflows are compiled is quite different, but one key aspect is the same. The compiler needs to split the whole expression (or method body) into parts between asynchronous calls. This makes it possible to start an asynchronous operation and then release the current thread.

Let's now look at the same example implemented in F#. In the earlier versions of this code snippet, I used a recursive function to implement the looping. This would be translated to a recursive asynchronous workflow. However I thought it would be more interesting to show exactly the same code snippet that uses while loop in F# too. Here is the implementation of the download:

 1: let request = HttpWebRequest.Create(url)
 2: let! response = request.AsyncGetResponse()
 3: let stream = response.GetResponseStream()
 4: while !count > 0 do
 5:   let! n = stream.AsyncRead(buffer, 0, buffer.Length)
 6:   temp.Write(buffer, 0, n)
 7:   count := n
 8: temp.Seek(0L, SeekOrigin.Begin) |> ignore
 9: (Some code at the end of the method omitted)
10: return title, html.Length F# Web Snippets

The snippet uses a mutable reference cell count to keep the number of bytes returned by the last AsyncRead call. We need to use a mutable value to be able to check it in the termination condition of the while loop. Otherwise, the code is essentially the same as the C# version. It contains two asynchronous operations written using let! and a single while loop. Let's look at the compiled form...

The essential principle of the compilation of asynchronous operations is that the compiler needs to (somehow) make it possible to start the operation in the background and specify the rest of the method as a continuation that can be called when the operation completes. In C#, the continuation is the MoveNext method of some object (where the _state field of the object remembers the current location in the method body). In F#, the continuation is a (lambda) function that directly contains the rest of the body to be executed.

When compiling F# asynchronous workflows, the compiler turns each non-standard operation into a call to some primitive of the computation builder (e.g. async) and transforms the rest of the code into a continuation:

 1: async.Delay(fun () -> 
 2:   let request = HttpWebRequest.Create(url)
 3:   async.Bind(request.AsyncGetResponse(), fun response ->
 4:     let stream = response.GetResponseStream()
 5:     // Combine two asynchronous computations
 6:     async.Combine(
 7:       // Build computation representing while loop
 8:       async.While( (fun () -> !count > 0),
 9:         async.Bind(stream.AsyncRead(buffer, 0, buffer.Length), fun n ->
10:           temp.Write(buffer, 0, n)
11:           count := n
12:           async.Zero() ) ),
13:       // Build (a delayed) computation that follows the loop
14:       async.Delay(fun () ->
15:         temp.Seek(0L, SeekOrigin.Begin) |> ignore
16:         (Some code at the end of the method omitted)
17:         async.Return(title, html.Length) ))))F# Web Snippets

Compared to the state machine compilation done by the C# compiler, the transformation performed by the F# compiler is quite simple. It follows these rules:

• let! bindings are translated to calls to the Bind member. The asynchronous operation is passed as the first argument and a continuation is passed as the second argument.
• while loop containing asynchronous operation is translated to a call to the While member. The first argument is a function that evaluates the termination condition and the second parameter is the body (which can be executed repeatedly).
• Sequence of expressions (e.g. while loop and the expression that follows it) is combined using the Combine member that takes two workflows and returns a single one that runs both of them in a sequence.
• The whole computation is wrapped inside Delay (so that it doesn't start running the first few (synchronous) lines when creating an asynchronous workflow)

The translated version of the code doesn't reveal anything about how F# asynchronous workflows run (when started using Async.Start or other method). The behavior is all encapsulated in the primitive members that are used to build the workflow (such as Bind and While). However, the execution proceeds similarly to the corresponding C# example.

• When the workflow is started, it runs the function passed as an argument to Delay. The function calls AsyncGetResponse to create a workflow representing the operation and passes it to Bind.
• Bind starts the operation and provides it a continuation (our lambda function) that will be called after the operation completes. Then the Bind member returns and so the calling thread can do some other work.
• When the lambda function is called (with response as an argument), it synchronously gets the response stream. Then it constructs a workflow that will be executed next by combining a while loop with consecutive code.
• The workflow returned by the Combine combinators starts the first workflow (constructed by While). It repeatedly runs the body of the loop (which is itself an asynchronous workflow) until the termination condition returns false.
• When the workflow constructed by While completes, the code generated by Combine calls the second workflow, which performs some (synchronous) processing and then constructs & returns a workflow that reports the result (using Return).

Comparison

The approaches used by C# and F# are quite different and both have pros and cons. The key advantage of the state machine compilation is that it generates more efficient code. However, this is probably not a big concern for asynchronous code, which spends most of the time waiting for some I/O operation or an external event. However, if you used async to write CPU bound code, then there will probably be some difference in the performance. Currently, the F# compiler performs similar translation when compiling sequence expressions (where efficiency depends more on the compilation). I remember talking about the compilation of asynchronous workflows with Don Syme during my second internship (two years ago :-)), so this may eventually be added to F# too.

The key advantage of the compilation based on combinators is that it is very flexible. The implementation is hidden in a library that can be easily changed. This also makes it possible to implement more complicated behavior - for example, the support for cancellation. Moreover, F# asynchronous workflows are just an example of computation expressions, which means that the compiler doesn't know anything about them. The same mechanism can be used to implement a wide range of other interesting computations (e.g. my article about implementing break in F#).