Posts Tagged ‘coroutine’
Rolling your own coroutines
This post marks the conclusion of the async programming series I originally started as lead in for my monospace 2011 talk. The remaining subject, as promised in my last article, is the creation of tradtional coroutines using .NET iterators. The example code and Monospace slides talking about it can be found on github. I had hoped to time it with a definite date for async/await arriving in .NET but WinRT has kind of derailed future releases, it would seem.
But before I get into, let's roll up the posts that got us here:
- Tasked To Get Results – Introducing our asynchronous completion handles, DReAM's Result and the Task Parallel Library's Task
- What's Asynchrony Good For? — When should we use these constructs
- Exit … Screen Right — CPS (Continuation Passing Style) asynchronous chaining using Result and Task
- Asynchrony and Sequential Workflows — Using DReAM coroutines and TPL's async/await to bring back sequential flow in asynchronous operations
The canonical example of coroutines are producer/consumer pipelines, in which each stage of the pipeline does some amount of work and yields execution to the next stage once it cannot continue. The benefits of this type of processing pipeline is avoidance of locks and maximum utilization of the processing power given to it, in addition to the loose coupling of the pipeline that easily let you add or remove steps in the chain.
For this processing to work the coroutines must all have the same "shape", e.g. signature. For the Iterator based coroutines I will cover first, I chose the following shape:
The coroutine accepts the Coordinator and yields once it cannot continue with any more work. The Coordinator contains the shared state T that all coroutines have access to. Since only one coroutine is ever executed at a time, the state can be mutated without locks.
The example we'll use is a producer of a 3x4 matrix and a consumer that outputs that matrix transpoed to 6x2. To show the ability to add random stages to this chain, we will have another coroutine that will take every value and square it.
We create a Coordinator<int[]>, i.e. our state is a block of ints, requiring a coroutine signature of IEnumerator Coroutine<T>(Coordinator<T> coordinator), but since the Coordinator accepts the coroutines as an array of Funcs, we can curry signatures of different shapes into the required shape. In our example we capture a source and destination for the Producer and Consumer coroutines, respectively, while the Exponetiator already has the required shape.
Let's look at the Producer:
The Producer takes the input matrix and writes it one row at a time into the state object. After each row, the producer yields execution to the next coroutine. We yield null, since the iterator is just used for its side-effect of letting us suspend a method mid-execution and continue later. And that's the magic of it. Yes, it looks like a regular method, but it really does exit and re-enter multiple times. Every time yield is called, the state of the method is suspended while another coroutine gets to run, and once resumed, the method continues on with all its local state from the point right after the yield. We are stopping in the middle of a loop, letting someone else go and then continue on from that exact same place in the loop, all without blocking a thread.
The Consumer is provided the output matrix and starts a loop that will continue until its output matrix is filled, reading the block of integers from the state, writing it to the new matrix and yielding its execution to the coordinator, so that the a fresh set of integers can be provided.
The last coroutine is the Exponentiator which just continues to square every value in the state integer block each time it is resumed and then yields execution until provided a fresh set of integers to square.
Finally, Coordinator<T> allows the construction of these arbitrary co-operative processing chains. It is simply an inversion of a regular iterator. Instead of receiving a new value, one at a time from an enumerator, we have one enumerator per coroutine that we can command to run to its next yield point with MoveNext(). MoveNext() will return false if it was a yield break, signaling that the coroutine is done or true if it was a yield return, signaling that the coroutine is willing to continue in which case we put the enumerator into our queue, pick the next coroutine from the queue and compel it resume.
In the github project I also implemented the same coroutines using async/await. The one benefit that implementation has over Iterator based coroutines is that once inside an async method, you can await any other async method. Allowing these types of coroutines to suspend the execution chain to let some other async task (such as a web request) execute.
While interesting and useful in a limited set of circumstances the coroutines introduced in this article are not likely going to find themselves into your next project. Far more useful and applicable in any application liable to block on I/O are the asynchronous workflows introduced in Asynchrony and Sequential Workflows since these types of coroutines allow us to use traditional sequential coding styles while never blocking on asynchronous operations.
MindTouch Coroutines and C#5.0 async
This week, at PDC 2010, Anders Hejlsberg introduced what is to become C# 5.0 and it’s major new feature: Making Async easy. The main facility for achieving this goal is the language keyword pair or async and await. Together they allow synchronous methods to be called in an asynchronous way without having to jump through all sorts of hoops.
This is very exciting stuff for us here at MindTouch, since we’ve built almost exactly that facility with our Asynchronous Method Pattern and Coroutine infrastructure in DReAM. But the one thing that has always bothered us what the additional manual code and sometimes unintuitive syntax required.
The Result and Task based asynchronous patterns
Steve Bjorg introduced Result<T> with DReAM on top of the .NET 2.0 and mono 1.1.16 back in 2006. You can find a quick overview of it here. I've also covered it extensively in my monoconf talk. It's is similar in purpose to the Task class in the Task Parallel Library introduced by Microsoft in .NET 4.0. Both of them are a kind of future, a handle for a value that may or may not have been produced yet. Both provide asynchrony patterns for easily calling a method that promises to produce a result eventually.
The MindTouch Asynchronous Method Pattern (AMP) takes this form:
Result<T> MethodName(...input paramaters..., Result<T> result)
where the trailing Result<T> is used to set up conditions on the return value, such as Timeout.
The Task-based Asynchronous Pattern (TAP) looks like this:
Task<T> MethodNameAsync(...input paramaters...)
Both are easy enough to call in blocking form, but that defeats their purpose. Both could also be set up with continuation handles, which get executed once a value T is available, but that takes the return code out of the current flow. And as completions call other asynchronous methods, your code just wanders off the right-hand side of the screen. This is common problem with continuations and is both a aesthetic and readability problem, in that your logically linear (if non-blocking) execution flow becomes increasingly difficult to follow.
Simplifying async flow with MindTouch Coroutines
What would be really nice is being able to call an asynchronous method and write the code that deals with the result on the next line, while simultaneously having your code suspend itself, freeing up your thread while the asynchronous code completes.
One way to approach this is with coroutines, i.e. a method that can exit and resume multiple times, rather having only one entry point. A coroutine can yield control to the async method and resume after it completes. In .NET 2.0 the yield operator was added to C# for the iterator pattern. If you turn the iterator pattern upside down, you end up with a method that yields not iteration results but continuations to some engine executing the control flow, i.e. MindTouch Coroutines:
Result<XDoc> r; yield return r = Download(uri, new Result<XDoc>); var doc = r.Value;
This provided us with the ability to write methods in synchronous style that could call to potentially long running asynchronous processes but continue their linear flow without ever blocking the thread. For a more detailed look at how coroutines are implemented check this article. However, the cost of achieving this came with some syntactic artifacts.
As illustrated above, we can't declare and assign the result type T in the yield return, hence the pre-declaration of Result<XDoc> r and the trailing var doc = r.Value. Three lines instead of one. In C# 3.0, using Lambdas, we reduced this to two lines:
XDoc doc; yield return doc = DownloadAndProcess(uri, new Result<XDoc>).Set(v => doc = v);
Another artifact is that a coroutine has to return an enumerator. We use IYield, which Result implements and coroutines require the return type IEnumerator<IYield> and by convention use a Result<T> as their last argument. That means coroutines can yield AMPs but are not AMPs themselves. As I stated above, a coroutine is an iterator turned upside down, yielding control to some executing engine. This means that every AMP that uses a coroutine can be written using this convention:
Result<XDoc> DownloadAndProcess(XUri uri, Result<XDoc> result) {
return Coroutine.Invoke(DownloadAndProcess_Coroutine, uri, result);
}
IEnumerator<IYield> DownloadAndProcess_Coroutine(XUri uri, Result<XDoc> result) {
XDoc doc;
yield return Plug.New(uri).Get(new Result<DreamMessage>)
.Set(v => doc = v.ToDocument());
// do some more async work
result.Return(doc);
}
Note: I snuck in Plug here, which is our fluent interface wrapper around HttpWebRequest and implements the AMP, internally using the async interface of HttpWebRequest, i.e. we can yield a Plug.Get and it will resume execution once the request completes.
C# 5.0 async/wait continuation flow
With C# vNext, Microsoft introduces two new language keywords that basically let you create the same flow we provide via the AMP and Coroutines, but using Task and leaving the syntactic cost to the compiler instead. This means that the TAP can be used without having to define a custom method with a different signature to execute the async work flow:
async Task<XDoc> DownloadAndProcess(XUri uri) {
var doc = await Plug.New(uri).Get();
// do some more async work
return doc;
}
The async keyword marks the method as one that the compiler needs to rewrite a sequence of continuations. The await keyword tells the compiler that a TAP method is being called and to squirrel the rest of the method body into a continuation that is executed once the Task<XDoc> has a result. Here the compiler takes on the work of letting you use a single method signature to call either as a regular method or as source of a continuation and rewrites a TAP call to yield execution flow and resume after completion. Using async/await certainly reduces ceremony and makes it all more readable. We wish we could have had that luxury when we embarked on this pattern 4 years ago. Note: The above code pre-supposes a version of Plug that implements the TAP instead of the AMP.
yield vs. await vs. something else
Shortly after Anders' PDC talk Eric Lippert posed the question whether await is the best name for this new facility in the post Asynchronous Programming in C# 5.0 part two: Whence await? on his blog. The comment thread is a good read of arguments for and against various keywords. Personally being partial to yield, I read Jon Skeet's case against it in his post C# 5 async and choosing terminology: why I'm against "yield" with interest. His point is that "[w]hen the action completes very quickly and synchronously, it isn't yielding at all." My personal feeling is that whether or not the call returns very quickly is an implementation detail invisible to the caller. The caller is yielding control to the callee, who makes the decision whether to return immediately or suspend the caller until completion.
However await does seem like the least appropriate of the options, since we're really not waiting at all. Syntax like continue after, continue with and continue when certainly seem more appropriate and descriptive of the action taking place. While yield return perfectly describes to me what happens, maybe that is a sign the terminology reveals the implementation detail rather than the intent. The caller doesn't care about the yielding of control. The caller just wants the result from the call and get on with its business. So from a clarity of code perspective, I have to side with the continue (after|with|when) camp.
When can I use async/await?
The CTP is available now. Of course, there is no release date, taking a gaming industry "when it's done!" stance. My bet is that async/await will be usable in the next mono release (2.10? 3.0?) before C# 5.0 ships. Any way you look at it, though, it's going to be a while before you can rely on it existing on a platform you didn't personally configure.
In the meantime, DReAM coroutines are battle tested, powering all REST services in the MindTouch product and any other product using DReAM, and you can be sure that as C#5 approaches we will be tracking its progress closely to evaluate using the TAP in DReAM. We certainly would love to take advantage of the simplified syntax, while staying compatible with our existing syntax.
MindTouch @ Monospace: Going Concurrent & Keeping your Sanity
Last week, on October 28th, Steve and I had the pleasure of presenting at the Monospace conference. I picked a topic close to the API Team’s heart, Concurrency, and specifically covered our use of the asynchronous method pattern and our coroutine framework. We’ve covered a lot of the motivation and reasoning for this a number of times on the Concurrent Podcast. I captured the talk as a screencast because i think it’s a useful primer on concurrency in MindTouch 2009 and our Dream framework and its especially useful as a hands-on companion for Concurrent Podcast 3: Coroutines:
I’d like to thank Scott Bellware for putting on a great conference, as well as everyone from the Mono team and the Mono/.NET community who attended. Monospace was incredibly insightful and I met a lot of very smart people there. Let’s hope this becomes a regular conference.
Concurrent Podcast (Episode 3): Coroutines
Photo by ToniVC
Concurrent Podcast 03: Coroutines
One topic we’ve mentioned in both previous episodes is Coroutines. We use them extensively at MindTouch and the asynchronous programming model provided by the Dream framework fundamentally relies on them. Since we’re likely to keep bringing them up in the future, we thought it best to cover them sooner rather than later.
For some background reading on Coroutines in C# check out my previous article corporate blog or the same content as a tutorial on the developer site (better code formatting).
As usual, you can find future topic listed here, and we always welcome suggestions on what should take precedence or what other topics to cover. If you want to subscribe to just the podcasts, you can find the feed here.
Advanced DekiScript extension in C# tutorial
I just posted a new tutorial about some of the more advanced features of DekiScript extensions written in C#. This is not the tutorial on the event bus I promised last week, which I am still working on and will blog about in the near future, but it introduces a number of concept that tutorial will use as well, so it is good primer material for what it to come.
The “Writing an extension in C# with Properties and Deki callbacks” tutorial covers these topics:
- Lazy execution and function pointers in script results
- Calling into other services from an extension using the Yield pattern for better scalability
- How-to create DekiScript properties
- Using the implicit environment to make calls back into Deki for access to the Deki API
Lazy Execution
For a DekiScript function that returns a list of lists or lists of hashes, each item in these collections can be a function pointer instead of the actual data. When a function pointer is accessed it’s automatically executed and since DekiScript is executed on the server, this does not incur additional round-trips to the server. It does mean that any item not accessed will avoid the overhead of fetching its data.
As an example, suppose you have a DekiScript function userutil.GetUserMap() which returns a map of users indexed by their name and you wanted to just list the users that start with ‘u’. If map values were function pointers to the user maps, the below code would only fetch the details of the users starting with ‘u’ during execution, rather than fetching all user maps and then not using them.
<ul>;
foreach( var kv in GetUserMap().KeyValues ) {
if( string.startswith(kv.key,"u") ) {
<li><a href=(kv.value.Uri)>kv.key</li>;
}
}
</ul>;
The Yield Pattern
I have previously written about Asychronous Coroutines in Dream using the yield keyword to suspend execution of a coroutine as it waits for some asynchronous resource to return data. What isn’t well known is that when creating DekiScript functions in C#, they can be defined either in their natural form, where the signature of the C# function mimics that of the DekiScript function, or in the format using the Yield pattern. The former means that the function will always execute as a synchronous unit, so that a remote call using Plug will block the thread while executing. The latter format allows the DekiScript function to take advantage of Dream’s asynchronous plumbing.
DekiScript Properties
Another capability of DekiScript extensions that is often overlooked is the ability to create Properties in addition to Functions. While properties just seem like Functions without arguments and parentheses, in conjunction with function pointers and the concept of currying, also explained in the tutorial, Properties are the ideal candidate lazy executed capabilities.
The Implicit Environment
Along with every execution of a DekiScript function, the DekiScript execution engine passes along a lot of useful data that can be used in your functions. Since it’s not passed into the function as an argument it’s not well understood, so the tutorial illustrates examples of accessing the environment to let the function know about the context (such as current user, page and site information) under which it is executing
The approach of the tutorial to these topics is to walk through a sample problem that takes advantage of all these features and showing the use of each to build the final solution. We hope these advanced topics help you create even more ambitious extensions to DekiScript for your projects.
