TP

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:

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:

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:

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.

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#).

val request : WebRequest

  type: WebRequest
  implements: System.Runtime.Serialization.ISerializable
  inherits: System.MarshalByRefObject
type HttpWebRequest =
  class
    inherit System.Net.WebRequest
    member Abort : unit -> unit
    member Accept : string with get, set
    member AddRange : int -> unit
    member AddRange : int * int -> unit
    member AddRange : string * int -> unit
    member AddRange : string * int * int -> unit
    member Address : System.Uri
    member AllowAutoRedirect : bool with get, set
    member AllowWriteStreamBuffering : bool with get, set
    member AutomaticDecompression : System.Net.DecompressionMethods with get, set
    member BeginGetRequestStream : System.AsyncCallback * obj -> System.IAsyncResult
    member BeginGetResponse : System.AsyncCallback * obj -> System.IAsyncResult
    member ClientCertificates : System.Security.Cryptography.X509Certificates.X509CertificateCollection with get, set
    member Connection : string with get, set
    member ConnectionGroupName : string with get, set
    member ContentLength : int64 with get, set
    member ContentType : string with get, set
    member ContinueDelegate : System.Net.HttpContinueDelegate with get, set
    member CookieContainer : System.Net.CookieContainer with get, set
    member Credentials : System.Net.ICredentials with get, set
    member EndGetRequestStream : System.IAsyncResult -> System.IO.Stream
    member EndGetRequestStream : System.IAsyncResult * System.Net.TransportContext -> System.IO.Stream
    member EndGetResponse : System.IAsyncResult -> System.Net.WebResponse
    member Expect : string with get, set
    member GetRequestStream : unit -> System.IO.Stream
    member GetRequestStream : System.Net.TransportContext -> System.IO.Stream
    member GetResponse : unit -> System.Net.WebResponse
    member HaveResponse : bool
    member Headers : System.Net.WebHeaderCollection with get, set
    member IfModifiedSince : System.DateTime with get, set
    member KeepAlive : bool with get, set
    member MaximumAutomaticRedirections : int with get, set
    member MaximumResponseHeadersLength : int with get, set
    member MediaType : string with get, set
    member Method : string with get, set
    member Pipelined : bool with get, set
    member PreAuthenticate : bool with get, set
    member ProtocolVersion : System.Version with get, set
    member Proxy : System.Net.IWebProxy with get, set
    member ReadWriteTimeout : int with get, set
    member Referer : string with get, set
    member RequestUri : System.Uri
    member SendChunked : bool with get, set
    member ServicePoint : System.Net.ServicePoint
    member Timeout : int with get, set
    member TransferEncoding : string with get, set
    member UnsafeAuthenticatedConnectionSharing : bool with get, set
    member UseDefaultCredentials : bool with get, set
    member UserAgent : string with get, set
    static member DefaultCachePolicy : System.Net.Cache.RequestCachePolicy with get, set
    static member DefaultMaximumErrorResponseLength : int with get, set
    static member DefaultMaximumResponseHeadersLength : int with get, set
  end

Full name: System.Net.HttpWebRequest

  type: HttpWebRequest
  implements: System.Runtime.Serialization.ISerializable
  inherits: WebRequest
  inherits: System.MarshalByRefObject
Multiple overloads
WebRequest.Create(requestUri: System.Uri) : WebRequest
WebRequest.Create(requestUriString: string) : WebRequest
val url : string

Full name: Untitled.url

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
val response : WebResponse

  type: WebResponse
  implements: System.Runtime.Serialization.ISerializable
  implements: System.IDisposable
  inherits: System.MarshalByRefObject
member WebRequest.AsyncGetResponse : unit -> Async<WebResponse>
val stream : Stream

  type: Stream
  implements: System.IDisposable
  inherits: System.MarshalByRefObject
WebResponse.GetResponseStream() : Stream
val count : int ref

Full name: Untitled.count

  type: int ref
  implements: System.Collections.IStructuralEquatable
  implements: System.IComparable<Ref<int>>
  implements: System.IComparable
  implements: System.Collections.IStructuralComparable
val n : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType
Multiple overloads
member Stream.AsyncRead : count:int -> Async<byte []>
member Stream.AsyncRead : buffer:byte [] * ?offset:int * ?count:int -> Async<int>
val buffer : 'a []

Full name: Untitled.buffer
val temp : MemoryStream

Full name: Untitled.temp

  type: MemoryStream
  implements: System.IDisposable
  inherits: Stream
  inherits: System.MarshalByRefObject
Stream.Write(buffer: byte [], offset: int, count: int) : unit
Stream.Seek(offset: int64, origin: SeekOrigin) : int64
type SeekOrigin =
  | Begin = 0
  | Current = 1
  | End = 2

Full name: System.IO.SeekOrigin

  type: SeekOrigin
  inherits: System.Enum
  inherits: System.ValueType
field SeekOrigin.Begin = 0
val ignore : 'T -> unit

Full name: Microsoft.FSharp.Core.Operators.ignore
let html = (new StreamReader(temp)).ReadToEnd()
let title = regTitle.Match(html).Groups.[1].Value, html.Length
val title : string * int
val html : string

  type: string
  implements: System.IComparable
  implements: System.ICloneable
  implements: System.IConvertible
  implements: System.IComparable<string>
  implements: seq<char>
  implements: System.Collections.IEnumerable
  implements: System.IEquatable<string>
property System.String.Length: int
val async : AsyncBuilder

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.async
member AsyncBuilder.Delay : generator:(unit -> Async<'T>) -> Async<'T>
member AsyncBuilder.Bind : computation:Async<'T> * binder:('T -> Async<'U>) -> Async<'U>
member AsyncBuilder.Combine : computation1:Async<unit> * computation2:Async<'T> -> Async<'T>
member AsyncBuilder.While : guard:(unit -> bool) * computation:Async<unit> -> Async<unit>
member AsyncBuilder.Zero : unit -> Async<unit>
member AsyncBuilder.Return : value:'T -> Async<'T>

Published: Sunday, 21 November 2010, 3:15 AM
Author: Tomas Petricek
Typos: Send me a pull request!
Tags: c#, functional, asynchronous, f#