Jon Skeet: Coding Blog

Currying vs partial function application

skeet — Mon, 30 Jan 2012 18:32:06 GMT

This is a slightly odd post, and before you read it you should probably put yourself into one of three buckets:

Someone who doesn't care too much about functional programming, and finds higher order functions tricky: feel free to skip this post entirely.
Someone who knows all about functional programming, and already knows the difference between currying and partial function application: please read this post carefully and post comments about any inaccuracies you find. (Yes, the CAPTCHA is broken on Chrome; sorry.)
Someone who doesn't know much about functional programming yet, but is interested to learn more: please take this post with a pinch of salt, and read the comments carefully. Read other articles by more experienced developers for more information.

Basically, I've been aware for a while that some people use the terms currying and partial function application somewhat interchangably, when they shouldn't. It's one of those topics (like monads) which I feel I understand to some extent, and I've decided that the best way of making sure I understand it is to try to write about it. If it helps the topic become more accessible to other developers, so much the better.

This post contains no Haskell

Almost every explanation I've ever seen of either topic has given examples in a "proper" functional language, typically Haskell. I have absolutely nothing against Haskell, but I typically find it easier to understand examples in a programming language I understand. I also find it much easier to write examples in a program language I understand, so all the examples in this post are going to be in C#. In fact, it's all available in a single file - that includes all of the examples, admittedly with a few variables renamed. Just compile and run.

C# isn't really a functional language - I know just about enough to understand that delegates aren't really a proper substitute for first class functions. However, they're good enough to demonstrate the principles involved.

While it's possible to demonstrate currying and partial function application using a function (method) taking a very small number of parameters, I've chosen to use 3 for clarity. Although my methods to perform the currying and partial function application will be generic (so all the types of parameters and return value are arbitrary) I'm using a simple function for demonstration purposes:

static string SampleFunction(int a, int b, int c)
{
return string.Format("a={0}; b={1}; c={2}", a, b, c);
}

So far, so simple. There's nothing tricky about that method, so don't look for anything surprising.

What's it all about?

Both currying and partial function application are about converting one sort of function to another. We'll use delegates as an approximation to functions, so if we want to treat the method SampleFunction as a value, we can write:

Func<int, int, int, string> function = SampleFunction;

This single line is useful for two reasons:

Assigning the value to a variable hammers home the point that it really is a value. A delegate instance is an object much like any other, and the value of the function variable is a reference just like any other.
Method group conversions (using just the name of the method as a way of creating a delegate) doesn't work terribly nicely with type inference when calling a generic method.

We can already call the function using three arguments with no further work:

string result = function(1, 2, 3);

Or equivalently:

string result = function.Invoke(1, 2, 3);

(The C# compiler just converts the shorthand of the first form to the second. The IL emitted will be the same.)

That's fine if we've got all the arguments available at the same time, but what if we haven't? To give a concrete (if somewhat contrived) example, suppose we have a logging function with three parameters (source, severity, message) and within a single class (which I'll call BusinessLogic for the moment) we always want to use the same value for the "source" parameter, and we'd like to be able to log easily everywhere in the class specifying just the severity and message. We have a few options:

Create an adapter class which takes the log function (or more generally a logging object) and the "source" value in its constructor, stashes both in instance variables, and exposes a method with two parameters. That method just delegates to the stashed logger, using the source it's remembered to supply the first argument to the three-parameter method. In BusinessLogic we create an instance of the adapter class, and stash a reference in an instance variable - then just call the two-parameter method everywhere we need to. This is probably overkill if we only need the adapter from BusinessLogic, but it's reusable... so long as we're trying to adapt the same logging function.
Store the original logger in our BusinessLogic class, but create a helper method with two parameters. This can hard-code the value used for the "source" parameter in one place (the helper method). If we need to do this in several places, it gets annoying.
Use a more general functional programming approach - probably partial function application in this case.

I'm deliberately ignoring the discrepancy between holding a reference to "the logger" and holding a reference to "the logging function". Obviously there's a significant difference if we need to use more than one function from the logging class, but for the purposes of thinking about currying and partial function application, we'll just think of "a logger" as "a function taking three parameters" (like our sample function).

Now that I've given the slightly-real-world concrete example for a bit of motivation, I'm going to ignore it for the rest of the post, and just talk about our sample function. I don't want to write a whole BusinessLogic class which pretends to do something useful; I'm sure you can perform the appropriate mental conversion from "the sample function" to "something I might actually want to do".

Partial Function Application

The purpose of partial function application is to take a function with N parameters and a value for one of those parameters, and return a function with N-1 parameters, such that calling the result will assemble all the required values appropriately (the 1 argument given to the partial application operation itself, and the N-1 arguments given to the returned function). So in code form, these two calls should be equivalent for our 3-parameter method:

// Normal call
string result1 = function(1, 2, 3);

// Call via partial application
Func<int, int, string> partialFunction = ApplyPartial(function, 1);
string result2 = partialFunction(2, 3);

In this case I've implemented partial application with a single parameter, and chosen the first one - you could write an ApplyPartial method which took more arguments to apply, or which used them somewhere else in the final function execution. I believe that picking off parameters one at a time, from the start, is the most conventional approach.

Thanks to anonymous functions (a lambda expression in this case, but an anonymous method wouldn't be much more verbose), the implementation of ApplyPartial is simple:

static Func<T2, T3, TResult> ApplyPartial<T1, T2, T3, TResult>
(Func<T1, T2, T3, TResult> function, T1 arg1)
{
return (b, c) => function(arg1, b, c);
}

The generics make the method look more complicated than it really is. Note that the lack of higher order types in C# means that you'd need a method like this for every delegate you wanted to use - if you wanted a version for a function which started with four parameters, you'd need an ApplyPartial<T1, T2, T3, T4, TResult> method etc. You'd probably also want a parallel set of methods for the Action delegate family.

The final thing to note is that assuming we had all of these methods, we could perform partial function application again - even potentially down to a parameterless function if we wanted, like this:

Func<int, int, string> partial1 = ApplyPartial(function, 1);
Func<int, string> partial2 = ApplyPartial(partial1, 2);
Func<string> partial3 = ApplyPartial(partial2, 3);
string result = partial3();

Again, only the final line would actually invoke the original function.

Okay, so that's partial function application. That's relatively straightforward. Currying is slightly harder to get your head round, in my view.

Currying

Whereas partial function application converts a function with N parameters into a function with N-1 parameters by applying one argument, currying effectively decomposes the function into functions taking a single parameter. We don't pass any arguments into the Curry method itself:

Curry(f) returns a function f1 such that...
f1(a) returns a function f2 such that...
f2(b) returns a function f3 such that...
f3(c) invokes f(a, b, c)

(Again, note that this is specific to our three-parameter function - but hopefully it's obvious how it would extend to other signatures.)

To give our "equivalence" example again, we can write:

// Normal call
string result1 = function(1, 2, 3);

// Call via currying
Func<int, Func<int, Func<int, string>>> f1 = Curry(function);
Func<int, Func<int, string>> f2 = f1(1);
Func<int, string> f3 = f2(2);
string result2 = f3(3);

// Or to do make all the calls together...
var curried = Curry(function);
string result3 = curried(1)(2)(3);

The difference between the latter examples shows one reason why functional languages often have good type inference and compact representations of function types: that declaration of f1 is pretty fearsome.

Now that we know what the Curry method is meant to do, it's actually surprisingly simple to implement. Indeed, all we need to do is translate the bullet points above into lambda expressions. It's a thing of beauty:

static Func<T1, Func<T2, Func<T3, TResult>>> Curry<T1, T2, T3, TResult>
(Func<T1, T2, T3, TResult> function)
{
return a => b => c => function(a, b, c);
}

If you want to add some brackets to make it clearer for you, feel free - personally I think it just adds clutter. Either way, we get what we want. (It's worth thinking about how annoying it would be to write that without lambda expressions or anonymous methods. Not hard, just annoying.)

So that's currying. I think. Maybe.

Conclusion

I can't say I've ever knowingly used currying, whereas I suspect some bits of Noda Time's text parsing effectively use partial functional application. (If anyone really wants me to dig in and check, I'll do so.)

I really hope I've got the difference between them right here - it feels right, in that the two are clearly related, but also quite distinct. Now that we've reached the end, think about how that difference manifests itself when there are only two parameters, and hopefully you'll see why I chose to use three :)

My gut feeling is that currying is a more useful concept in an academic context, whereas partial functional application is more useful in practice. However, that's the gut feeling of someone who hasn't really used a functional language in anger. If I ever really get round to using F#, maybe I'll do a follow-up post. For now, I'm hoping that my trusty smart readers can provide useful thoughts for others.

Eduasync part 19: ordering by completion, ahead of time...

skeet — Mon, 16 Jan 2012 22:22:43 GMT

Today's post involves the MagicOrdering project in source control (project 28).

When I wrote part 16 of Eduasync, showing composition in the form of majority voting, one reader mailed me a really interesting suggestion. We don't really need to wait for any of the tasks to complete on each iteration of the loop - we only need to wait for the next task to complete. Now that sounds impossible - sure, it's great if we know the completion order of the tasks, but half the point of asynchrony is that many things can be happening at once, and we don't know when they'll complete. However, it's not as silly as it sounds.

If you give me a collection of tasks, I'll give you back another collection of tasks which will return the same results - but I'll order them so that the first returned task will have the same result as whichever of your original tasks completes first, and the second returned task will have the same result as whichever of your original tasks completes second, and so on. They won't be the same tasks as you gave me, reordered - but they'll be tasks with the same results. I'll propagate cancellation, exceptions and so on.

It still sounds impossible... until you realize that I don't have to associate one of my returned tasks with one of your original tasks until it has completed. Before anything has completed, all the tasks look the same. The trick is that as soon as I see one of your tasks complete, I can fetch the result and propagate it to the first of the tasks I've returned to you, using TaskCompletionSource<T>. When the second of your tasks completes, I propagate the result to the second of the returned tasks, etc. This is all quite easy using Task<T>.ContinueWith - barring a few caveats I'll mention later on.

Once we've built a method to do this, we can then really easily build a method which is the async equivalent of Parallel.ForEach (and indeed you could write multiple methods for the various overloads). This will execute a specific action on each task in turn, as it completes... it's like repeatedly calling Task.WhenAny, but we only actually need to wait for one task at a time, because we know that the first task in our "completion ordered" collection will be the first one to complete (duh).

Show me the code!

Enough description - let's look at how we'll demonstrate both methods, and then how we implement them.

private static async Task PrintDelayedRandomTasksAsync()
{
    Random rng = new Random();
    var values = Enumerable.Range(0, 10).Select(_ => rng.Next(3000)).ToList();
    Console.WriteLine("Initial order: {0}", string.Join(" ", values));

    var tasks = values.Select(DelayAsync);

    var ordered = OrderByCompletion(tasks);

    Console.WriteLine("In order of completion:");
    await ForEach(ordered, Console.WriteLine);
}

/// <summary>
/// Returns a task which delays (asynchronously) by the given number of milliseconds,
/// then return that same number back.
/// </summary>
private static async Task<int> DelayAsync(int delayMillis)
{
    await TaskEx.Delay(delayMillis);
    return delayMillis;
}

The idea is that we're going to create 10 tasks which each just wait for some random period of time, and return the same time period back. We'll create them in any old order - but obviously they should complete in (at least roughly) the same order as the returned numbers.

Once we've created the collection of tasks, we'll call OrderByCompletion to create a second collection of tasks, returning the same results but this time in completion order - so ordered.ElementAt(0) will be the first task to complete, for example.

Finally, we call ForEach and pass in the ordered task collection, along with Console.WriteLine as the action to take with each value. We await the resulting Task to mimic blocking until the foreach loop has finished. Note that we could make this a non-async method and just return the task returned by ForEach, given that that's our only await expression and it's right at the end of the method. This would be marginally faster, too - there's no need to build an extra state machine. See Stephen Toub's article about async performance for more information.

ForEach

I'd like to get ForEach out of the way first, as it's so simple: it's literally just iterating over the tasks, awaiting them and propagating the result to the action. We get the "return a task which will wait until we've finished" for free by virtue of making it an async method.

/// <summary>
/// Executes the given action on each of the tasks in turn, in the order of
/// the sequence. The action is passed the result of each task.
/// </summary>
private static async Task ForEach<T>(IEnumerable<Task<T>> tasks, Action<T> action)
{
    foreach (var task in tasks)
    {
        T value = await task;
        action(value);
    }
}

Simple, right? Let's get onto the meat...

OrderByCompletion

This is the tricky bit, and I've actually split it into two methods to make it slightly easier to comprehend. The PropagateResult method feels like it could be useful in other composition methods, too.

The basic plan is:

Copy the input tasks to a list: we need to work out how many there are and iterate over them, so let's make sure we only iterate once
Create a collection of TaskCompletionSource<T> references, one for each input task. Note that we're not associating any particular input task with any particular completion source - we just need the same number of them
Declare an integer to keep track of "the next available completion source"
Attach a continuation to each input task which will be increment the counter we've just declared, and propagate the just-completed task's status
Return a view onto the collection of TaskCompletionSource<T> values, projecting each one to its Task property

Once you're happy with the idea, the implementation isn't too surprising (although it is quite long):

/// <summary>
/// Returns a sequence of tasks which will be observed to complete with the same set
/// of results as the given input tasks, but in the order in which the original tasks complete.
/// </summary>
private static IEnumerable<Task<T>> OrderByCompletion<T>(IEnumerable<Task<T>> inputTasks)
{
    // Copy the input so we know it'll be stable, and we don't evaluate it twice
    var inputTaskList = inputTasks.ToList();

    // Could use Enumerable.Range here, if we wanted...
    var completionSourceList = new List<TaskCompletionSource<T>>(inputTaskList.Count);
    for (int i = 0; i < inputTaskList.Count; i++)
    {
        completionSourceList.Add(new TaskCompletionSource<T>());
    }

    // At any one time, this is "the index of the box we've just filled".
    // It would be nice to make it nextIndex and start with 0, but Interlocked.Increment
    // returns the incremented value...
    int prevIndex = -1;

    // We don't have to create this outside the loop, but it makes it clearer
    // that the continuation is the same for all tasks.
    Action<Task<T>> continuation = completedTask =>
    {
        int index = Interlocked.Increment(ref prevIndex);
        var source = completionSourceList[index];
        PropagateResult(completedTask, source);
    };

    foreach (var inputTask in inputTaskList)
    {
        // TODO: Work out whether TaskScheduler.Default is really the right one to use.
        inputTask.ContinueWith(continuation,
                               CancellationToken.None,
                               TaskContinuationOptions.ExecuteSynchronously,
                               TaskScheduler.Default);
    }

    return completionSourceList.Select(source => source.Task);
}

/// <summary>
/// Propagates the status of the given task (which must be completed) to a task completion source
/// (which should not be).
/// </summary>
private static void PropagateResult<T>(Task<T> completedTask,
    TaskCompletionSource<T> completionSource)
{
    switch (completedTask.Status)
    {
        case TaskStatus.Canceled:
            completionSource.TrySetCanceled();
            break;
        case TaskStatus.Faulted:
            completionSource.TrySetException(completedTask.Exception.InnerExceptions);
            break;
        case TaskStatus.RanToCompletion:
            completionSource.TrySetResult(completedTask.Result);
            break;
        default:
            // TODO: Work out whether this is really appropriate. Could set
            // an exception in the completion source, of course...
            throw new ArgumentException("Task was not completed");
    }
}

You'll notice there are a couple of TODO comments there. The exception in PropagateResult really shouldn't happen - the continuation shouldn't be called when the task hasn't completed. I still need to think carefully about how tasks should propagate exceptions though.

The arguments to ContinueWith are more tricky: working through my TimeMachine class and some unit tests with Bill Wagner last week showed just how little I know about how SynchronizationContext, the task awaiters, task schedulers, and TaskContinuationOptions.ExecuteSynchronously all interact. I would definitely need to look into that more deeply before TimeMachine was really ready for heavy use... which means you should probably be looking at the TPL in more depth too.

Conclusion

Sure enough, when you run the code, the results appear in order, as the tasks complete. Here's one sample of the output:

Initial order: 335 468 1842 1991 2512 2603 270 2854 1972 1327
In order of completion:
270
335
468
1327
1842
1972
1991
2512
2603
2854

TODOs aside, the code in this post is remarkable (which I can say with modesty, as I've only refactored it from the code sent to me by another reader and Stephen Toub). It makes me smile every time I think about the seemingly-impossible job it accomplishes. I suspect this approach could be useful in any number of composition blocks - it's definitely one to remember.

Coding in the style of Glee

skeet — Sun, 15 Jan 2012 20:07:55 GMT

As previously mentioned, at CodeMash 2012 I gave a very silly Pecha Kucha talk entitled "Coding in the style of Glee". The video is on YouTube, or can be seen embedded below:

(There's also another YouTube video from a different angle.)

This post gives the 20 slides (which were just text; no fancy pictures unlike my competitors) and what I meant to say about them. (Edited very slightly to remove a couple of CodeMash-specific in-jokes.) Don't forget that each slide was only up for 20 seconds.

Coding in the style of Glee

As you may know, I’m from the UK, and it’s wonderful to be here. This is my first US conference, so it’s great to be in the country which has shared with the world its most marvellous cultural output: the Fox show, Glee.

At first I watched it just for surface story – but now I know better – I know that really, the songs are all about the culture and practice of coding.

(It isn't easy) Bein' Green

When I started coding, it was on a ZX Spectrum, in Basic. It was hard, but the computer came with a great manual. I later learned C from a ringbinder of some course or other – and entirely failed to understand half the language. Of course, this was before Stack Overflow, when it was really hard being a newbie – where could you turn for information?

Getting to know you

Over time I became semi-competent in C, with the help of friends. But learning is a constant process, of course – getting to know new languages and platforms is just part of a good dev's life every day.

Learning itself is a skill – how similar it is to getting to know small children, I leave to your imagination.

Man in the Mirror

Glee doesn’t just talk about the coding experience, of course – it talks about specific technologies. This Michael Jackson song is talking about reflection, of course. Although the idea wasn’t new in Java, it was new to me – and now it would be almost unthinkable to come up with a new platform which didn’t let you find out about what was in the code.

Bridge over Troubled Water

Another technology covered beautifully by Glee is the interop. We’re in a big world, and we always need to talk to other systems. Whether it’s over JNI (heaven help you), P/Invoke, SOAP, REST – whatever, I hope next time you connect to another system, you’ll hear this haunting Simon and Garfunkel melody in the background.

I will survive

And who could forget persistence frameworks. I’m not sure whether Gloria Gaynor had Hibernate and the Entity Framework in mind when she sang this, but I’m utterly convinced that the Glee writers did. When you submit your data, it’s just got to survive – what else would you want?

You can't always get what you want

We’d all like perfect specifications, reliable libraries, ideal languages, etc – but that’s just not going to happen. It’s possible that of course you won’t get what you need – even if you try real hard. But hey, you might just.

Lean on me (or Agile on me)

(I didn't actually have notes written for this one. Copied from the video.)

Glee sympathizes with you - but it also have a bit of an answer: lean on me. Lean and agile development, so we can adapt to constantly changing specifications, and eventually we will have something that is useful. Maybe nothing like what we initially envisaged, but it will be something useful.

Losing my Religion

Of course, we don’t always stay in love with a platform. I’d like to dedicate this slight to Enterprise Java. Fortunately I never had to deal with Enterprise Java Beans, but I “enjoyed” enough other J2EE APIs to make me yearn for a world without BeanProcessorFactoryFactories.

Anything Goes

Now I’m pretty conservative – only in terms of coding, mind you. I’m a statically typed language guy. But Glee celebrates dynamic languages too – languages where really, anything goes until you try to execute it. Even though I haven’t gone down the dynamic route myself much, it’s important that we all welcome the diversity of languages and platforms we have.

Get Happy

Along with the rise of dynamic languages, we seem to have seen a rise of happy developers. We’ve always had enthusiastic developers, but there’s a certain air about your typical Ruby on Rails developer which feels new to me. Again, I’m not a Ruby fan myself – but it’s always nice to see other happy people, and maybe one day I’ll see the light.

Bust your Windows

I don’t know what I can say about this song. Do the Glee writers have it in for Microsoft? I don’t remember “Bust your OSX” or “Bust your Linux” for example. Only Windows is targeted here.

The Safety Dance

One big change for me since joining Google is increased awareness of the need for redundancy – the intricate dance we need to perform to create a service which will stay up no matter what. Where redundancy is a dirty word in most of industry, as developers we celebrate it – and will do anything we can to avoid…

The Only Exception

… a single point of failure.

(Yes, that really is all I'd prepared for that slide. Hence the need for improvisation.)

Telephone

(From video.) Glee celebrates the rise of phone apps. Who these days could be unaware of the importance of the development of mobile applications? And obviously, we can credit the iPhone for that, but since the iPhone, and just smart phone apps, we've also started...

U Can't Touch This

(From video.) Tablets! And touch screen devices of all kinds. So Windows 8 - very touch-based, and sooner or later we're all going to have to get with it. I don't do UIs, I've never done a touch UI in my life, I have no idea how it works. But clearly it's one of the ways forward.

Forget You

As smart phones and tablets become more ubiquitous and more bound to us as people, privacy has become more important. Glee gave us a timely reminder of the reverse of the persistence early on: we need to be able to forget about users, as well as remember them.

(A)waiting for a girl like you

(From video.) I'd like to leave on an up-note, so: I'm clearly very, very excited (really, really excited) about C# 5 and its await keyword so I ask you - I beg you - be excited about development. And always bear in mind your users.

My life would suck without you

Users rule our world. Can’t live without them, can’t shoot ‘em.

Celebrate – we do stuff to make users really happy! This is awesome! We should be thrilled!

(Even for enterprise apps, we’re doing useful stuff. Honest.)

Don't stop believing

(From video.) So to sum up: have fun, keep learning, really, really enjoy what you're doing, and... don't stop!

CodeMash 2012 report

skeet — Sun, 15 Jan 2012 19:38:42 GMT

I'm nearly home - on a bus back from Heathrow airport to Reading - returning from CodeMash 2012. This was my first US conference, and I had a wonderful time. It was pretty densely packed in terms of presenting / recording for me:

I presented two back-to-back sessions jointly with Bill Wagner, on async. These went down really well (particularly Bill's genius idea of using the Doctor Who quote about time being a "big ball of wibbly-wobbly, timey-wimey stuff") and were great fun to give. Bill's a class act, and I think we got the balance between use and underpinnings about right.
I recorded a podcast with Scott Hanselman (we were going to record two, but the first one ended up being longer than expected)
I presented a talk on "C#'s Greatest Mistakes" which ended up being somewhere between a discussion on language design, and a demonstration of surprising "features" of C#. It overran by 15 minutes without me coming close to running out of things to say, but hopefully it was useful. It was a somewhat rambly session, but at least I warned folks of that up-front. It would be nice to be able to present the same sort of material in a really "tight" way, but I'm just not sure how to.
I gave a 20x20 "Pecha Kucha" talk called "Coding in the style of Glee" as the silliest topic I could come up with on short notice. This was absolutely terrifying and extremely silly. I only came third in the contest (and the winner, Leon, was simply phenomenal) but I was happy that I'd only embarrassed myself about as much as I'd expected to. The YouTube video of this is already up, and I'll write a blog post with the slide titles and what I was trying to say in them :)

Unfortunately due to last minute async prep and desperately trying to cobble together slides for the Glee talk, I didn't have time to actually attend as many talks as I'd have liked. Even though I was present for the whole of the Scala Koans session in the PreCompilr on Wednesday, I found myself next to Bruce Eckel, and ended up chatting with him for most of the time. It would have been a bit of a waste not to, really. (And at least some of that talking was Scala-related...) I also watched the whole of the SignalR presentation by Brady Gaster - where I was apparently the only person in the room with an aversion to "dynamic" in C# 4. That made me the butt of a few jokes, but not too many for comfort.

In terms of C#-related talks, I went to the first half of Dustin Campbell's Roslyn session, but was somewhat distracted by putting together Glee slides and had to leave half way through to hand them in. My final session of the conference was Bill Wagner's "Stunt coding in C# - I dare you to try this at home" which was excellent, and a very fitting end to the conference for me.

Highlights of the conference for me:

Messing with Bill Wagner's code at the end of not just our joint async talk but also his Stunt Coding talk. I've never before asked a presented whether they mind me just stealing the keyboard, but I was confident that Bill (and the attendees) would get a kick out of it - and the code was nicer afterwards :)
Meeting so many people... some that I've met before (I hadn't seen Ted Neward since I gate-crashed a party at his house after the MVP 2005 Summit), some I'd met virtually but not physically before (like Bill) and there loads of other folks I'd never known at all before - including Cori Drew. Cori simply seemed to pop up everywhere - I swear she had about 20 clones at CodeMash. (She also recorded the video of the Glee talk, and it's her laughter you can hear - thanks very much, Cori!) Everyone at the conference was incredibly friendly, and I was really touched by how many people said on the last day that they'd appreciated me making the long trip.
Confounding Dustin Campbell and Kevin Pilch-Bisson with my evil generic overloading puzzle. Just to be clear, these are two seriously smart guys and this was a friendly over-lunch challenge. It's always a privilege to meet more of the team responsible for C# and Visual Studio.
The number of families who came - this is something I've never seen at other conferences, and it really made a difference in terms of the atmosphere of the non-dev bits. It was fabulous to see the kids in the water park, for example. Even out of just attendees, there was a greater proportion of women at CodeMash than at other conferences I've been to - obviously still vastly outnumbered by the men, but it was nice to see some improvement on that front.

This will probably be my only international conference for 2012, so it's a good job that it was so wonderfully organized. I really hope I have the chance to attend next year too. Many thanks to everyone who helped make it such a special conference.

Eduasync part 18: Changes between the Async CTP and the Visual Studio 11 Preview

skeet — Thu, 12 Jan 2012 01:34:31 GMT

In preparation for CodeMash, I've been writing some more async code and decompiling it with Reflector. This time I'm using the Visual Studio 11 Developer Preview - the version which installs alongside Visual Studio 2010 under Windows 7. (Don't ask me about any other features of Visual Studio 11 - I haven't explored it thoroughly; I've really only used it for the C# 5 bits.)

There have been quite a few changes since the CTP - they're not visible changes in terms of code that you'd normally write, but the state machine generated by the C# compiler is reasonably different. In this post I'll describe the differences, as best I understand them. There are still a couple of things I don't understand (which I'll highlight within the post) but overall, I think I've got a pretty good handle on why the changes have been made.

I'm going to assume you already have a reasonable grasp of the basic idea of async and how it works - the way that the compiler generates a state machine to represent an async method or anonymous function, with originally-local variables being promoted to instance variables within the state machine, etc. If the last sentence was a complete mystery to you, see Eduasync part 7 for more information. I don't expect you to remember the exact details of what was in the previous CTP though :)

Removal of iterator block leftovers

In the CTP, the code for async methods was based on the iterator block implementation. I suspect that's still the case, but possibly sharing just a little less code. There used to be a few methods and fields which weren't used in async methods, but now they're gone:

There's no now constructor, so no need for the "skeleton" method which replaces the real async method to pass in 0 as the initial state.
There's no Dispose method.
There's no disposing field.

It's nice to see these gone, but it's not terribly interesting. Now on to the bigger changes...

Large structural changes

There's a set of related structural changes which don't make sense individually. I'll describe them first, then look at how it all hangs together, and my guess as to the reasoning behind.

The state machine is now a struct

The declaration of the nested type for the state machine is now something like this:

[CompilerGenerated]
private struct StateMachine : IStateMachine
{
    // Fields common to all async state machines
    // (with caveats)
    private int state;
    private object awaiter;
    public AsyncTaskMethodBuilder<int> builder;
    public Action moveNextDelegate;
    private object stack;

    // Hoisted local variables

    // Methods
    [DebuggerHidden]
    public void SetMoveNextDelegate(Action action) { ... }
    public void MoveNext() { ... }
}

The caveats around the common field are in terms of the return type of the async method (which determines the type of builder used) and whether or not there are any awaits (if there are no awaits, the stack and awaiter fields aren't generated).

Note that throughout this blog post I've changed the names of fields and types - in reality they're all "unspeakable" names including angle-brackets, just like all compiler-generated names.

There's a new assembly-wide interface

As you can see from the code above, the state machine implements an interface (actually called <>t__IStateMachine). One of these is created in the global namespace in each assembly that contains at least one async method or anonymous function, and it looks like this:

[CompilerGenerated]
internal interface IStateMachine
{
void SetMoveNextDelegate(Action action);
}

The implementation for this method is always the same, and it's trivial:

[DebuggerHidden]
public void SetMoveNextDelegate(Action action)
{
this.moveNextDelegate = action;
}

Simplified skeleton method

The method which starts the state machine, which I've been calling the "skeleton" method everywhere, is now a bit simpler than it was. Something like this:

public static Task<int> FooAsync()
{
    StateMachine machine = new StateMachine();
    machine.builder = AsyncVoidMethodBuilder.Create();
    machine.MoveNext();
    return machine.builder.Task;
}

In fact if you decompile the IL, you'll see that it doesn't explicitly initialize the variable to start with - it just declares it, sets the builder field and then calls MoveNext(). That's not valid C# (as all the struct's fields aren't initialized), but it is valid IL. It's equivalent to the code above though. Note how there's nothing to set the continuation - where previously the moveNextDelegate field would be populated within the skeleton method.

Just-in-time delegate creation

Now that the skeleton method doesn't create the delegate representing the continuation, it can be done when it's first required - which is when we first encounter an await expression for an awaitable which hasn't already completed. (If the awaitable has completed before we await it, the generated code skips the continuation and just uses the results immediately and synchronously).

The code for that delegate creation is slightly trickier than you might expect, however. It looks something like this:

Action action = this.moveNextDelegate;
if (action == null)
{
    Task<int> task = this.builder.Task;
    action = new Action(this.MoveNext);
    ((IStateMachine) action.Target).SetMoveNextDelegate(action);
}

There are two oddities here, one of which I mostly understand and one of which I don't understand at all.

I really don't understand the "task" variable here. Why do we need to exercise the AsyncTaskMethodBuilder.Task property? We don't use the result anywhere... does forcing this flush some memory buffer? I have no clue on this one. (See the update at the bottom of the post...)

The part about setting the delegate via the interface makes more sense, but it's subtle. You might expect code like this:

// Looks sensible, but is actually slightly broken
Action action = this.moveNextDelegate;
if (action == null)
{
action = new Action(this.MoveNext);
this.moveNextDelegate = action;
}

That would sort of work - but we'd end up needing to recreate the delegate each time we encountered an appropriate await expression. Although the above code saves the value to the field, it saves it within the current value of the state machine... after we've boxed that value as the target of the delegate. The value we want to mutate is the one within the box - which is precisely why there's an interface, and why the code casts to it.

We can't even just unbox and then set the field afterwards - at least in C# - because the unbox operation is always followed by a copy operation in normal C#. I believe it would be possible for the C# compiler to generate IL which unboxed action.Target without the copy, and then set the field in that. It's not clear to me why the team went with the interface approach instead... I would expect that to be slower (as it requires dynamic dispatch) but I could easily be wrong. Of course, it would also make it impossible to decompile the IL to C#, which would make my talks harder, but don't expect the C# team to bend the compiler implementation for my benefit ;)

(As an aside to all of this, I've gone back and forth on whether the "slightly broken" implementation would recreate the delegate on every appropriate await, or only two. I think it would end up being on every occurrence, as even though on the second occurrence we'd be operating within the context of the first boxed instance, the new delegate would have a reference to a new boxed copy each time. It does my head in a little bit, trying to think about this... more evidence that mutable structs are evil and hard to reason about. It's not the wrong decision in this case, hidden far from the gaze of normal developers, but it's a pain to reason about.)

Single awaiter variable

In the CTP, each await expression generated a separate field within the state machine, and that field was always of the exact awaiter type. In the VS11 Developer Preview, there's always exactly one awaiter field (assuming there's at least one await expression) and it's always of type object. It's used like this:

// Single local variable used by both continuation and first-time paths
TaskAwaiter<int> localAwaiter;

...

if (conditions-for-first-time-execution)
{
      // Code before await

      localAwaiter = task.GetAwaiter();
      if (localAwaiter.IsCompleted)
      {
          goto Await1Completed;
      }
      this.state = 1;
      TaskAwaiter<int>[] awaiterArray = { localAwaiter };
      this.awaiter = awaiterArray;
      // Lazy delegate creation goes here
      awaiterArray[0].OnCompleted(action);
      return;
}
// Continuation would get into here
localAwaiter = ((TaskAwaiter<int>[]) this.awaiter)[0];
this.awaiter = null;
this.state = 0;
Await1Completed:
int result = localAwaiter.GetResult();
localAwaiter = default(TaskAwaiter<int>);

I realize there's a lot of code here, but it does make some sense:

The value of the awaiter field is always either null, or a reference to a single-element array of the awaiter type for one of the await expressions.
A single localAwaiter variable is shared between the two code paths, populated either from the awaitable (on the initial code path) or by copying the value from the array (in the second code path).
The field is always set to null and the local variable is set to its default value after use, presumably for the sake of garbage collection

It's basically a nice way of using the fact that we'll only ever need one awaiter at a time. It's not clear to me why an array is used instead of either using a reference to the awaiter for class-based awaiters, or simply by boxing for struct-based awaiters. The latter would need the same "unbox without copy" approach discussed in the previous section - so if there's some reason why that's actually infeasible, it would explain the use of an array here. We can't use the interface trick in this case, as the compiler isn't in control of the awaiter type (so can't make it implement an interface).

Expression stack preservation

This one is actually a fix to a bug in the async CTP, which I've written about before. We're used to the stack containing our local variables (in the absence of iterator blocks, captured variables etc, and modulo the stack being an implementation detail) but it's also used for intermediate results within a single statement. For example, consider this block of code:

int x = 10;
int y = 5;
int z = x + 50 * y;

That last line is effectively:

Load the value of x onto the stack
Load the value 50 onto the stack
Load the value of y onto the stack
Multiply the top two stack values (50 and y) leaving the result on the stack
Add the top two stack values (x and the previously-computed result) leaving the result on the stack
Store the top stack value into z

Now suppose we want to turn y into a Task<int>:

int x = 10;
Task<int> y = Task.FromResult(5);
int z = x + 50 * await y;

Our state machine needs to make sure that it will preserve the same behaviour as the synchronous version, so it needs the same sort of stack. In the new-style state machine, all of that stack is saved in the "stack" field. It's only one field, but may need to represent multiple different types within the code at various different await expressions - in the code above, for example, it represents two int values. As far as I can discover, the C# compiler generates code which uses the actual type of the value it needs, if it only requires a single value. If it needs multiple values, it uses an appropriate Tuple type, nesting tuples if it goes beyond the number of type parameters supported by the Tuple<...> family of types. So in our case above, we end up with code a bit like this:

// Local variable used in both paths
Tuple<int, int> tuple;

...

// Code before the await
if (conditions-for-first-time-execution)
{
    ...
    tuple = new Tuple<int, int>(this.x, 50);
    this.stack = tuple;
    ...
}

// Continuation would get into here
tuple = (Tuple<int, int>) this.stack;
// IL copies the values from the tuple onto the stack at this point
this.stack = null;

...

// Both the fast and slow code paths get here eventually
this.z = stack0 + stack1 * awaiter.GetResult()

I say it's a bit like this, because it's hard to represent the IL exactly in C# in this case. The tuple is only created if it's needed, i.e. not in the already-completed fast path. In that case, the values are loaded onto the stack but not then put into the tuple - execution skips straight to the code which uses the values already on the stack.

When the awaitable isn't complete immediately, then a Tuple<int, int> is created, stored in the "stack" field, and the continuation is handed to the awaiter. On continuation, the tuple is loaded back from the "stack" field (and cast accordingly), the values are loaded onto the stack - and then we're back into the common code path of fetching the value and performing the add and multiply operations.

Conclusion

As far as I'm aware, those are the most noticeable changes in the generated code. There may well still be a load more changes in Task<T> and the TPL in general - I wouldn't be at all surprised - but that's harder to investigate.

I'm sure all of this has been done in the name of performance (and correctness, in the case of stack preservation). The state machine is now much smaller in terms of the number of fields it requires, and objects are created locally as far as possible (including the state machine itself only requiring heap allocation if there's ever a "slow" awaitable). I suspect there's still some room for optimization, however:

Both the awaiter and the delegate use careful boxing and either arrays or a mutating interface to allow the boxed value to be changed. I suspect that using unbox with the concrete type, but without copying the value, would be more efficient. I may attempt to work this theory up into a test at some point.
If there's only one awaiter type (usually TaskAwaiter<T> for some T), that type could be used instead of object, potentially reducing heap optimization
I've no idea why the builder.Task property is explicitly fetched and then the results discarded
If there's only one await expression, the "stack" field can be strongly typed, which would also avoid boxing if only a single value needs to be within that stack
The stack field could be removed entirely when it's not needed for intermediate stack value preservation. (I believe that would be the case reasonably often.)

The use of mutable value types is really fascinating (for me, at least) - I'm sure most people on the C# team would still say they're evil, but when they're used in a carefully controlled environment where real developers don't have to reason about their behaviour, they can be useful.

Next time, I'll hopefully get back to the idea I promised to write up before, about ordering a collection of tasks in completion order... before they've completed. (Well, sort of.) Should be fun...

Update (January 16th 2012)

Stephen Toub got in touch with me after I posted the original version of this blog entry, to explain the use of the Task property. Apparently the idea is that at this point, we know we're going to return out of the state machine, so the skeleton method is going to access the Task property anyway. However, as we haven't scheduled the continuation yet we also know that nothing will be accessing the Task property on a different thread. If we access it now for the first time, we can lazily allocate the task in the same thread that created the AsyncMethodBuilder, with no risk of contention. If we can force there to be a task ready and waiting for whatever accesses it later, we don't need any synchronization in that area.

So why might we want to allocate the task lazily in the first place? Well, don't forget that we might never have to wait for an await (as it were). We might just have an async method which takes the fast path everywhere. If that's the case, then for certain cases (e.g. a non-generic, successfully completed task, or a Task<bool> which again has completed successfully) we can reuse the same instance repeatedly. Apparently this laziness isn't yet part of the VS11 Developer Preview, but the reason for the property access is in preparation for this.

Another case of micro-optimization - which is fair enough when it's at a system level :)

Awaiting CodeMash 2012

skeet — Sun, 01 Jan 2012 20:43:10 GMT

Happy New Year, everyone!

I'm attempting to make 2012 a quiet year in terms of my speaking engagements - I've turned down a few kind offers already, and I expect to do so again during the year. I may well still give user group talks in evenings if I can do so without having to take holiday, but full conferences are likely to be out, especially international ones. This is partly so I can take more time off to support my wife, Holly, who has her own books to promote. This year will be particularly important for Holly as she's one of the World Book Day 2012 authors - I'm tremendously proud of her, as you can no doubt imagine.

However, there's one international conference I decided to submit proposals for: CodeMash. I've never been to this or any other US conference, but I've heard fabulous things about it. I'm particularly excited that I'll be able to present alongside Bill Wagner, a fellow C# author (probably most famous for Effective C# which I've reviewed before now). Bill and I have never met, although we've participated jointly on a .NET Rocks show before now. I could barely hear Bill when we recorded that though, so it hardly counts :)

The conference schedule for CodeMash shows Bill and I each giving two talks: two individual ones on general C# (C# Stunt Coding by Bill, and C#'s Greatest Mistakes by me) and two sessions on the async support in C# 5... async "from the inside" and "from the outside". Although these have hitherto been shown as separate sessions, everyone involved thought it would make more sense to weave the two together... so this will be a double-length session. Bill will be presenting the "outside" view - how to use async, basically; I'll be presenting the "inside" view - how it all hangs together behind the scenes.

With any luck, this will be much more helpful to the conference attendees, as they should be able to build up confidence in the solid foundations underpinning it all at the same time as seeing how fabulously useful it'll be for developers. It also means that Bill and I can bounce ideas off each other spontaneously as we go - I intend to pay close attention and learn a thing or two myself!

It's pretty much impossible to predict how it'll all hang together, but I'm really excited about the whole shebang. I'll be fascinated to see if and how US conferences differ from the various ones this side of the pond... but it does make the whole thing that bit more nerve-wracking. If you're coming to CodeMash, please grab me and say hi - it never hurts to see a friendly face...

(Note: Bill has a similar blog post posted just before this one.)

Book Review: Fluent C# (Rebecca Riordan, Sams)

skeet — Mon, 05 Dec 2011 19:26:25 GMT

(As usual, I will be sending the publisher a copy of this review to give them and the author a chance to reply to it before I publish it to the blog. Other than including their comments and correcting any factual mistakes they may point out, I don't intend to change the review itself.)

Resources:

Publisher page (includes source code download)
Amazon / Barnes and Noble
My unofficial errata and notes
A more positive series of review blog posts (just for balance)

Introduction and disclaimers

In late October, Sams (the publisher) approached me to ask if I'd be interested in reviewing their newest introductory book on C#. Despite my burgeoning review stack, I said I was interested - I'm always on the lookout for good books to recommend. So, the first disclaimer is that this was a review copy - I didn't have to pay for it. I don't believe that has biased this review though.

Second disclaimer: obviously as C# in Depth is also "a book about C#" you might be wondering whether the two books are competitors. I don't believe this is the case: Fluent C# explicitly talks about its target audience, which is primarily complete newcomers to programming. C# in Depth pretty much requires you to know at least C# 1, or perhaps be very comfortable with a similar language such as Java. I find it hard to imagine someone for whom both books would be suitable.

Obviously that puts me firmly out of the target audience. As I've written before, if you think the two most important questions to answer in a technical book review are "Is it accurate?" and "How good is at teaching its topic?" then any one person will find it hard to answer both questions. Although I'm far from an expert in some of the areas of the book - notably WPF - I'm sure I don't have the same approach as a true newcomer. In particular, I find myself asking the questions I'd need the answers to in order to develop software professionally: how do I test it? How does the deployment model work? How does the data flow? These aren't the same concerns as someone who is coming to programming for the first time. This review should be read with that context in mind: that my approach to the subject matter won't be the same as a regular reader's.

Physical format and style

Fluent C# is very reminiscent of Head-First C# in its approach, even down to the introductory "why this book is great at teaching you" blurb. It's all very informal, with lots of pictures, diagrams and reader exercises. It's a chunky book, at nearly 900 pages including the index - which I'd expect to be pretty daunting to a newcomer. However, that isn't the main impression you come away with. Instead...

It's brown. Everywhere. The diagrams, the text, the pictures - they're all printed in brown, on off-white paper.

Combined with using multiple fonts including cursive ones, this makes for a pointlessly irritating reading experience right from the outset, however good or bad the actual content is. Now it's possible that this is actually deliberate: I was speaking to someone recently who mentioned some research that shows if you use a hard-to-read font in presentations, people tend to end up reading it several times, so you end up with better memories of the content than if it had been "clean". I don't know if that's what Sams intended with this book, but I frequently found myself longing for simple black ink on clean white paper.

Leaving that to one side, I'm not sure I'll ever really be a fan of the general tone of books like this, but I can certainly see that it's popular and therefore presumably helpful to many people. It's not clear to me whether it's possible to create a book which retains the valuable elements of this style while casting off the aspects which rub me up the wrong way. It's something about the enforced jollity which just doesn't quite sit right, but it wouldn't surprise me if that were more a peculiarity of my personality than anything about the book. Again, I've tried to set this to one side when reviewing the book, but it may come through nonetheless.

Structure

The book is broken up into the following sections, with several chapters per section:

Getting started (122 pages - finding your way around Visual Studio, debugging, deployment)
The Language (100 pages - introduction to C#)
The .NET Framework Library (162 pages - text, date/time APIs, collections - and actually more about C# as a language)
Best practice (116 pages - inheritance, some principles, design patterns)
WPF (341 pages)

I've included the page count for each section to show just how much is devoted to WPF. The book goes into much more detail about WPF than it does about the C# language itself (for example, drop shadow effects are included, but the "using" statement and nullable value types aren't). If you want to write any kind of application other than a WPF one, a large part of the book won't be useful to you. That's not to say it's useless per se - and in fact from my point of view, the WPF section was the most useful. The section on brushes is probably the best written in the whole book, for example. At time it feels to me like the author really wanted to write a book about WPF, but was asked to make it one about C# instead. That may well not be the case at all - it was just an impression.

Even though the best practice section talks briefly about MVC, MVP and MVVM, it doesn't really go into enough detail to build anything like a real application - and in fact there's no coverage of persistence of any form. No files, no XML, no database - nothing below the presentation layer, really. As such, although the book claims it's enough to get you started with application development, it actually only provides a veneer. Even though I didn't like the first edition of Head-First C# back in 2008, it did at least take the reader end-to-end - the exercises led to complete applications. The best practice section isn't entirely about architecture and design patterns, however - it's at this point that inheritance is properly introduced. While I wouldn't personally count that as a "best practice" as such, it does at least come at the start of the section, before the genuine patterns/architecture areas which would have been harder to understand without that background.

One aspect which concerned me was the emphasis on the debugger and interactive diagnostics. The author states that developers should expect to spend a large part of their time in the debugger, and she says how she prefers using MessageBox.Show for diagnostics over Console.WriteLine information appearing in the output window. While I'm all for something more sophisticated than Console.WriteLine, there are solutions which are a lot less invasive than popping up a dialog, and which can be left in the code (possibly under an execution-time configuration) to allow diagnostics to be produced for real systems.

The "testing and deployment" chapter says nothing about automated tests - it's as if the author believes that "testing" only involves "running the app in the debugger and seeing if it breaks". I hope that's not actually the case, and I can understand why newcomers ought to at least know about the debugger - but I'd have welcomed at least a few pages introducing unit testing as a way of recording and checking expectations of how your code behaves. My own preference is to spend as little time in the debugger as possible; I know that's not always practical, particularly for UI work, but I think it's a reasonable aim.

Accuracy

Anyone following me on Twitter or Google+ knows where I'm going with this section. After reading through the book, pen in hand (as I always do, even for the books I like), I decided that it was more important to get out some form of errata quickly than this review. As such, I started a Google document which is publicly available to read and add comments to. The result is over 60 pages of notes and errata, and that's excluding the introduction and table of contents. To be fair to the book, some of those notes are matters of disagreement which are more personal opinion than incontrovertible fact - but there are plenty of simple matters of inaccuracy. Some of the worst are:

Claims that String is a value type. (It's a reference type.)
Inconsistency between whether arrays are value types or reference types - but consistently claiming that arrays are immutable, with the exception of the size which can be changed (slowly) using Array.Resize. (Array types are always reference types, and they're always mutable except the size, which is fixed after creation. Array.Resize creates a new array, it doesn't change the size of the existing one.)
Incorrect syntax for chaining from one constructor to another.
The claim that all reference types are mutable. (Some aren't, and indeed I often aim for immutability. The canonical example of an immutable reference type is String.)

There are plenty more - including huge number of samples which simply won't compile. Whole double page spreads where every class declaration is missing the "class" keyword. Pieces of code using VB syntax... the list goes on. (The VB syntax errors are probably explained by the author's other book published at the same time: "Fluent Visual Basic". I suspect there was a certain amount of copy/paste, and the editing process didn't catch all the changes which were needed to reflect the differences between the languages.)

Beyond the factually incorrect statements, there's the matter of terminology. Now I'm well aware that I care more about terminology than more people - but there's simply no reason to start making up terminology or misusing the perfectly good terminology from the specification. The book has a whole section on "commands" in C#, including things like for statements, switch statements, try/catch/finally statements. Additionally, it mislabels class and namespace declarations as "statements", and even mislabels using directives as statements - although it later goes back on the latter point. The word "object" is used at various times to mean any of variable, type, class and object, with no sense of consistency that I could fathom. For example, at one point it's used in two different senses within the same sentence: "As we'll see, you can define several different kinds of objects (called TYPES) in C#, but the one you'll probably work with most often is the OBJECT."

Both accuracy and staying consistent with accepted terminology (primarily the specification) are particularly important for newcomers. If there's a typo in a relatively advanced book - or in one which is about a particular technology (e.g. MVC) rather than an introductory text on a language, the reader is fairly likely to be able to guess what should really be there based on their existing experience. If a beginner comes across the same problem, they're likely to assume it's their fault that the code won't compile. Likewise if they learn the wrong terminology to start with, they'll be severely hampered in communicating effectively with other developers - as well as when reading other books.

I don't want to make it sound like I expect perfection in a book - just yesterday someone mailed me a correction to C# in Depth, and I'd be foolish to try to hold other authors to standards I couldn't meet myself. Nor am I suggesting it's easy to be both accessible and accurate - so often an author may have an accurate picture of a complex topic, but have to simplify it in their writing, particularly for an introductory book like Fluent C#. But there are limits - and in my view this book goes well past the level of error that I'm willing to put up with.

Conclusion

I really don't like ranting. I don't like sounding mean - and I wanted to like this book. While I like C# 4.0 in a Nutshell and Essential C# 4.0, I'm still looking for a book which I can recommend to readers who want a more "lively" kind of book. Unfortunately I really can't recommend Fluent C# to anyone - it is simply too inaccurate, and I believe it will cause confusion and instil bad habits in its readers.

So, what next? I'm hoping that the publisher and author will take my errata on board for the next printing, and revise it thoroughly. At that point I still don't think I'd actually like the book due to its structure and WPF focus (and the colour scheme, which I don't expect to change), but it would at least be more a matter of taste then.

I have some reason to be hopeful - because my review of Head-First C# was somewhat like this one, and one of the authors of that book (Andrew Stellman) was incredibly good about the whole thing, and as a result the second edition of Head-First C# is a much better book than the first edition. Again, it's not quite my preferred style, but for readers who like that sort of thing, it's a much better option than Fluent C# at the moment, and one I'm happy to recommend (with the express caveat of getting the second edition).

At the same time, reading Fluent C# (and particularly thinking about its debugger-first approach) has set me something of a challenge. You see, I've mostly avoided writing for new programmers so far - but I feel it's really important to get folks off on the right foot, and I'd like to have a stab at it. In particular, I would like to see if it's possible to write an introductory text which teaches C# using unit tests wherever possible... but without being dry. Can we have a "fun" but accurate book, which tries to teach C# from scratch without giving the impression that user interfaces are the be-all and end-all of programming? Can I write in a way which is more personal but doesn't feel artificial? I can't see myself starting such a project any time in the next year, but maybe some time in 2013... Watch this space. In the meantime, I'll keep an eye out for any more introductory books which might be more promising than Fluent C#.

Eduasync part 17: unit testing

skeet — Fri, 25 Nov 2011 21:46:45 GMT

In the last post I showed a method to implement "majority voting" for tasks, allowing a result to become available as soon as possible. At the end, I mentioned that I was reasonably confident that it worked because of the unit tests... but I didn't show the tests themselves. I felt they deserved their own post, as there's a bigger point here: it's possible to unit test async code. At least sometimes.

Testing code involving asynchrony is generally a pain. Introducing the exact order of events that you want is awkward, as is managing the threading within tests. With a few benefits with async methods:

We know that the async method itself will only execute in a single thread at a time
We can control the thread in which the async method will execute, if it doesn't configure its awaits explicitly
Assuming the async method returns Task or Task<T>, we can check whether or not it's finished
Between Task<T> and TaskCompletionSource<T>, we have a way of injecting tasks that we understand

Now in our sample method we have the benefit of passing in the tasks that will be awaited - but assuming you're using some reasonably testable API to fetch any awaitables within your async method, you should be okay. (Admittedly in the current .NET framework that excludes rather a lot of classes... but the synchronous versions of those calls are also generally hard to test too.)

The plan

For our majority tests, we want to be able to see what happens in various scenarios, with tasks completing at different times and in different ways. Looking at the test cases I've implemented I have the following tests:

NullSequenceOfTasks
EmptySequenceOfTasks
NullReferencesWithinSequence
SimpleSuccess
InputOrderIsIrrelevant
MajorityWithSomeDisagreement
MajorityWithFailureTask
EarlyFailure
NoMajority

I'm not going to claim this is a comprehensive set of possible tests - it's a proof of concept more than anything else. Let's take one test as an example: MajorityWithFailureTask. The aim of this is to pass three tasks (of type Task<string>) into the method. One will give a result of "x", the second will fail with an exception, and the third will also give a result of "x". The events will occur in that order, and only when all three results are in should the returned task complete, at which point it will also have a success result of "x".

So, the tricky bit (compared with normal testing) is introducing the timing. We want to make it appear as if tasks are completing in a particular order, at predetermined times, so we can check the state of the result between events.

Introducing the TimeMachine class

Okay, so it's a silly name. But the basic idea is to have something to control the logical flow of time through our test. We're going to ask the TimeMachine to provide us with tasks which will act in a particular way at a given time, and then when we've started our async method we can then ask it to move time forward, letting the tasks complete as they go. It's probably best to look at the code for MajorityWithFailureTask first, and then see what the implementation of TimeMachine looks like. Here's the test:

[Test]
public void MajorityWithFailureTask()
{
    var timeMachine = new TimeMachine();
    // Second task gives a different result
    var task1 = timeMachine.AddSuccessTask(1, "x");
    var task2 = timeMachine.AddFaultingTask<string>(2, new Exception("Bang!"));
    var task3 = timeMachine.AddSuccessTask(3, "x");

    var resultTask = MoreTaskEx.WhenMajority(task1, task2, task3);
    Assert.IsFalse(resultTask.IsCompleted);

    // Only one result so far - no consensus
    timeMachine.AdvanceTo(1);
    Assert.IsFalse(resultTask.IsCompleted);

    // Second result is a failure
    timeMachine.AdvanceTo(2);
    Assert.IsFalse(resultTask.IsCompleted);

    // Third result gives majority verdict
    timeMachine.AdvanceTo(3);
    Assert.AreEqual(TaskStatus.RanToCompletion, resultTask.Status);
    Assert.AreEqual("x", resultTask.Result);
}

As you can see, there are two types of method:

AddSuccessTask / AddFaultingTask / AddCancelTask (not used here) - these all take the time at which they're going to complete as their first parameter, and the method name describes the state they'll reach on completion. The methods return the task created by the time machine, ready to pass into the production code we're testing.
AdvanceTo / AdvanceBy (not used here) - make the time machine "advance time", completing pre-programmed tasks as it goes. When those tasks complete, any continuations attached to them also execute, which is how the whole thing hangs together.

Now forcing tasks to complete is actually pretty simple, if you build them out of TaskCompletionSource<T> to start with. So all we need to do is keep our tasks in "time" order (which I achieve with SortedList), and then when we're asked to advance time we move through the list and take the appropriate action for all the tasks which weren't completed before, but are now. I represent the "appropriate action" as a simple Action, which is built with a lambda expression from each of the Add methods. It's really simple:

public class TimeMachine
{
    private int currentTime = 0;
    private readonly SortedList<int, Action> actions = new SortedList<int, Action>();

    public int CurrentTime { get { return currentTime; } }

    public void AdvanceBy(int time)
    {
        AdvanceTo(currentTime + time);
    }

    public void AdvanceTo(int time)
    {
        // Okay, not terribly efficient, but it's simple.
        foreach (var entry in actions)
        {
            if (entry.Key > currentTime && entry.Key <= time)
            {
                entry.Value();
            }
        }
        currentTime = time;
    }

    public Task<T> AddSuccessTask<T>(int time, T result)
    {
        TaskCompletionSource<T> tcs = new TaskCompletionSource<T>();
        actions[time] = () => tcs.SetResult(result);
        return tcs.Task;
    }

    public Task<T> AddCancelTask<T>(int time)
    {
        TaskCompletionSource<T> tcs = new TaskCompletionSource<T>();
        actions[time] = () => tcs.SetCanceled();
        return tcs.Task;
    }

    public Task<T> AddFaultingTask<T>(int time, Exception e)
    {
        TaskCompletionSource<T> tcs = new TaskCompletionSource<T>();
        actions[time] = () => tcs.SetException(e);
        return tcs.Task;
    }
}

Okay, that's a fair amount of code for a blog posts (and yes, it could do with some doc comments etc!) but considering that it makes life testable, it's pretty simple.

So, is that it?

It works on my machine... with my test runner... in simple cases...

When I first ran the tests using TimeMachine, they worked almost immediately. This didn't surprise me nearly as much as it should have done. You see, when the tests execute, they use async/await in the normal way - which means the continuations are scheduled on "the current task scheduler". I have no idea what the current task scheduler is in unit tests. Or rather, it feels like something which is implementation specific. It could easily have worked when running the tests from ReSharper, but not from NCrunch, or not from the command line NUnit test runner.

As it happens, I believe all of these run tests on thread pool threads with no task scheduler allocated, which means that the continuation is attached to the task to complete "in-line" - so when the TimeMachine sets the result on a TaskCompletionSource, the continuations execute before that call returns. That means everything happens on one thread, with no ambiguity or flakiness - yay!

However, there are two problems:

The words "I believe" aren't exactly confidence-inspiring when it comes to testing that your software works correctly.
Our majority voting code only ever sees one completed task at a time - we're not testing the situation where several tasks complete so quickly together that the continuation doesn't get chance to run before they've all finished.

Both of these are solvable with a custom TaskScheduler or SynchronizationContext. Without diving into the docs, I'm not sure yet which I'll need, but the aim will be:

Make TimeMachine implement IDisposable
In the constructor, set the current SynchronizationContext (or TaskScheduler) to a custom one having remembered what the previous one was
On disposal, reset the context
Make the custom scheduler keep a queue of jobs, such that when we're asked to advance to time T, we complete all the appropriate tasks but don't execute any continuations, then we execute all the pending continuations.

I don't yet know how hard it will be, but hopefully the Parallel Extensions Samples will help me.

Conclusion

I'm not going to claim this is "the" way of unit testing asynchronous methods. It's clearly a proof-of-concept implementation of what can only be called a "test framework" in the loosest possible sense. However, I hope it gives an example of a path we might take. I'm looking forward to seeing what others come up with, along with rather more polished implementations.

Next time, I'm going to shamelessly steal an idea that a reader mailed me (with permission, of course). It's insanely cool, simple and yet slightly brain-bending, and I suspect will handy in many situations. Love it.

Eduasync part 16: Example of composition: majority voting

skeet — Tue, 22 Nov 2011 23:18:41 GMT

Note: For the rest of this series, I'll be veering away from the original purpose of the project (investigating what the compiler is up to) in favour of discussing the feature itself. As such, I've added a requirement for AsyncCtpLib.dll - but due to potential distribution restrictions, I've felt it safest not to include that in the source repository. If you're running this code yourself, you'll need to copy the DLL from your installation location into the Eduasync\lib directory before it will build - or change each reference to it.

One of the things I love about async is the compositional aspect. This is partly due to the way that the Task Parallel Library encourages composition to start with, but async/await makes it even easier by building the tasks for you. In the next few posts I'll talk about a few examples of interesting building blocks. I wouldn't be surprised to see an open source library with a proper implementation of some of these ideas (Eduasync is not designed for production usage) whether from Microsoft or a third party.

In project 26 of Eduasync, I've implemented "majority voting" via composition. The basic idea is simple, and the motivation should be reasonably obvious in this day and age of redundant services. You have (say) five different tasks which are meant to be computing the same thing. As soon as you have a single answer which the majority of the tasks agree on, the code which needs the result can continue. If the tasks disagree, or fail (or a combination leading to no single successful majority result), the overall result is failure too.

My personal experience with services requiring a majority of operations to return is with Megastore, a storage system we use at Google. I'm not going to pretend to understand half of the details of how Megastore works, and I'm certainly not about to reveal any confidential information about its internals or indeed how we use it, but basically when discussing it with colleagues at around the time that async was announced, I contemplated what a handy feature async would be when implementing a Megastore client. It could also be used in systems where each calculation is performed in triplicate to guard against rogue errors - although I suspect the chances of those systems being implemented in C# are pretty small.

It's worth mentioning that the implementation here wouldn't be appropriate for something like a stock price service, where the result can change rapidly and you may be happy to tolerate a small discrepancy, within some bounds.

The API

Here's the signatures of the methods we'll implement:

public static Task<T> WhenMajority<T>(params Task<T>[] tasks)

public static Task<T> WhenMajority<T>(IEnumerable<Task<T>> tasks)

Obviously the first just delegates to the second, but it's helpful to have both forms, so that we can pass in a few tasks in an ad hoc manner with the first overload, or a LINQ-generated sequence of tasks with the second.

The name is a little odd - it's meant to match WhenAll and WhenAny, but I'm sure there are better options. I'm not terribly interested in that at the moment.

It's easy to use within an async method:

Task<int> firstTask = firstServer.ComputeSomethingAsync(input);
Task<int> secondTask = selectServer.ComputeSomethingAsync(input);
Task<int> thirdTask = thirdServer.ComputeSomethingAsync(input);

int result = await MoreTaskEx.WhenMajority(firstTask, secondTask, thirdTask);

Or using the LINQ-oriented overload:

var tasks = servers.Select(server => server.ComputeSomethingAsync(input));
int result = await MoreTaskEx.WhenMajority(tasks);

Of course we could add an extension method (dropping the When prefix as it doesn't make as much sense there, IMO):

int result = await servers.Select(server => server.ComputeSomethingAsync(input))
.MajorityAsync();

The fact that we've stayed within the Task<T> model is what makes it all work so smoothly. We couldn't easily express the same API for other awaitable types in general although we could do it for any other specific awaitable type of course. It's possible that it would work using dynamic, but I'd rather avoid that :) Let's implement it now.

Implementation

There are two parts to the implementation, in the same way that we implemented LINQ operators in Edulinq - and for the same reason. We want to go bang immediately if there are any clear input violations - such as the sequence of tasks being null or empty. This is in line with the Task-based Asynchronous Pattern white paper:

An asynchronous method should only directly raise an exception to be thrown out of the MethodNameAsync call in response to a usage error*. For all other errors, exceptions occurring during the execution of an asynchronous method should be assigned to the returned Task.

Now it occurs to me that we don't really need to do this in two separate methods (one for precondition checking, one for real work). We could create an async lambda expression of type Func<Task<T>>, and make the method just return the result of invoking it - but I don't think that would be great in terms of readability.

So, the first part of the implementation performing validation is really simple:

public static Task<T> WhenMajority<T>(params Task<T>[] tasks)
{
    return WhenMajority((IEnumerable<Task<T>>) tasks);
}

public static Task<T> WhenMajority<T>(IEnumerable<Task<T>> tasks)
{
    if (tasks == null)
    {
        throw new ArgumentNullException("tasks");
    }
    List<Task<T>> taskList = new List<Task<T>>(tasks);
    if (taskList.Count == 0)
    {
        throw new ArgumentException("Empty sequence of tasks");
    }
    foreach (var task in taskList)
    {
        if (task == null)
        {
            throw new ArgumentException("Null task in sequence");
        }
    }
    return WhenMajorityImpl(taskList);
}

The interesting part is obviously in WhenMajorityImpl. It's mildly interesting to note that I create a copy of the sequence passed in to start with - I know I'll need it in a fairly concrete form, so it's appropriate to remove any laziness at this point.

So, here's WhenMajorityImpl, which I'll then explain:

private static async Task<T> WhenMajorityImpl<T>(List<Task<T>> tasks)
{
    // Need a real majority - so for 4 or 5 tasks, must have 3 equal results.
    int majority = (tasks.Count / 2) + 1;
    int failures = 0;
    int bestCount = 0;

    Dictionary<T, int> results = new Dictionary<T, int>();
    List<Exception> exceptions = new List<Exception>();
    while (true)
    {
        await TaskEx.WhenAny(tasks);
        var newTasks = new List<Task<T>>();
        foreach (var task in tasks)
        {
            switch (task.Status)
            {
                case TaskStatus.Canceled:
                    failures++;
                    break;
                case TaskStatus.Faulted:
                    failures++;
                    exceptions.Add(task.Exception.Flatten());
                    break;
                case TaskStatus.RanToCompletion:
                    int count;
                    // Doesn't matter whether it was there before or not - we want 0 if not anyway
                    results.TryGetValue(task.Result, out count);
                    count++;
                    if (count > bestCount)
                    {
                        bestCount = count;
                        if (count >= majority)
                        {
                            return task.Result;
                        }
                    }
                    results[task.Result] = count;
                    break;
                default:
                    // Keep going next time. may not be appropriate for Created
                    newTasks.Add(task);
                    break;
            }
        }
        // The new list of tasks to wait for
        tasks = newTasks;

        // If we can't possibly work, bail out.
        if (tasks.Count + bestCount < majority)
        {
            throw new AggregateException("No majority result possible", exceptions);
        }
    }
}

I should warn you that this isn't a particularly efficient implementation - it was just one I wrote until it worked. The basic steps are:

Work out how many results make a majority, so we know when to stop
Keep track of how many "votes" our most commonly-returned result has, along with the counts of all the votes
Repeatedly:

Wait (asynchronously) for at least of the remaining tasks to finish (many may finish "at the same time")
Start a new list of "tasks we're going to wait for next time"
Process each task in the current list, taking an action on each state:

If it's been cancelled, we'll treat that as a failure (we could potentially treat "the majority have been cancelled" as a cancellation, but for the moment a failure is good enough)
If it's faulted, we'll add the exception to the list of exceptions, so that if the overall result ends up as failure, we can throw an AggregateException with all of the individual exceptions
If it's finished successfully, we'll check the result:

Add 1 to the count for that result (the dictionary will use the default comparer for the result type, which we assume is good enough)
If this is greater than the previous "winner" (which could be for the same result), check for it being actually an overall majority, and return if so.

If it's still running (or starting), add it to the new task list

Check whether enough tasks have failed - or given different results - so ensure that a majority is now impossible. If so, throw an AggregateException to say so. This may have some exceptions, but it may not (if there are three tasks which gave different results, none of them actually failed)

Each iteration of the "repeatedly" will have a smaller list to check than before, so we'll definitely terminate at some point.

I mentioned that it's inefficient. In particular, we're ignoring the fact that WhenAny returns a Task<Task<T>>, so awaiting that will actually tell us a task which has finished. We don't need to loop over the whole collection at that point - we could just remove that single task from the collection. We could do that efficiently if we kept a Dictionary<Task<T>, LinkedListNode<Task<T>> and a LinkedList<Task<T>> - we'd just look up the task which had completed in the dictionary, remove its node from the list, and remove the entry from the dictionary. We wouldn't need to create a new collection each time, or iterate through all of the old one. However, that's a job for another day... as is allowing a cancellation token to be passed in, and a custom equality comparer.

Conclusion

So we can make this implementation smarter and more flexible, certainly - but it's not insanely tricky to write. I'm reasonably confident that it works, too - as I have unit tests for it. They'll come in the next part. The important point from this post is that by sticking within the Task<T> world, we can reasonably easily create building blocks to allow for composition of asynchronous operations. While it would be nice to have someone more competent than myself write a bullet-proof, efficient implementation of this operation, I wouldn't feel too unhappy using a homegrown one in production. The same could not have been said pre-async/await. I just wouldn't have had a chance of getting it right.

Next up - the unit tests for this code, in which I introduce the TimeMachine class.

Eduasync part 15: implementing COMEFROM with a horrible hack

skeet — Fri, 11 Nov 2011 22:15:11 GMT

Ages ago when I wrote my previous Eduasync post, I said we'd look at a pipeline model of coroutines. I've decided to skip that, as I do want to cover the topic of this post, and I've got some more "normal" async ideas to write about too. If you want to look at the pipeline coroutines code, it's project 20 in the source repository. Have fun, and don't blame me if you get confused reading it - so do I.

The code I am going to write about is horrible too. It's almost as tricky to understand, and it does far nastier things. Things that the C# 5 specification explicitly says you shouldn't do.

If it makes you feel any better when your head hurts reading this code, spare a thought for me - I haven't looked at it in over six months, and I don't have a blog post explaining how it's meant to work. I just have almost entirely uncommented code which is designed to be hard to understand (in terms of the main program flow).

On no account should any code like this ever be used for anything remotely serious.

With that health warning out of the way, let's have a look at it...

COMEFROM at the caller level

The idea is to implement the COMEFROM control structure, which is sort of the opposite of GOTO (or in my implementation, more of a GOSUB). There are two operations, effectively:

ComeFrom(label): Register interest in a particular label.
Label(label): If anyone has registered interested in the given label, keep going from their registration point (which will be within a method), then continue from where we left off afterwards.

In some senses it's a little like the observer pattern, with labels taking the place of events. However, it looks entirely different and is much harder to get your head round, because instead of having a nicely-encapsulated action which is subscribed to an event, we just have a ComeFrom call which lets us jump back into a method somewhat arbitrarily.

I have two implementations, in project 22 and project 23 in source control. Project 22 is almost sane; a little funky, but not too bad. Project 23 is where the fun really happens. In addition to the operations listed above, there's an Execute operation which is sort of an implementation detail - it allows an async method containing ComeFrom calls to be executed without returning earlier than we might want.

Let's look at some code and the output, and try to work out what's going on.

internal class Program
{
    private static void Main(string[] args)
    {
        Coordinator coordinator = new Coordinator(SimpleEntryPoint);
        coordinator.Start();
    }

    private static async void SimpleEntryPoint(Coordinator coordinator)
    {
        await coordinator.Execute(SimpleOtherMethod);

        Console.WriteLine("First call to Label(x)");
        await coordinator.Label("x");

        Console.WriteLine("Second call to Label(x)");
        await coordinator.Label("x");

        Console.WriteLine("Registering interesting in y");
        bool firstTime = true;
        await coordinator.ComeFrom("y");

        Console.WriteLine("After ComeFrom(y). FirstTime={0}", firstTime);

        if (firstTime)
        {
            firstTime = false;
            await coordinator.Label("y");
        }
        Console.WriteLine("Finished");
    }

    private static async void SimpleOtherMethod(Coordinator coordinator)
    {
        Console.WriteLine("Start of SimpleOtherMethod");

        int count = 0;
        await coordinator.ComeFrom("x");

        Console.WriteLine("After ComeFrom x in SimpleOtherMethod. count={0}. Returning.",
                          count);
        count++;
    }
}

The reason for the "Simple" prefix on the method names is that there's another example in the same file, with a more complex control flow.

Here's the output - then we can look at why we're getting it...

Start of SimpleOtherMethod
After ComeFrom x in SimpleOtherMethod. count=0. Returning.
First call to Label(x)
After ComeFrom x in SimpleOtherMethod. count=1. Returning.
Second call to Label(x)
After ComeFrom x in SimpleOtherMethod. count=2. Returning.
Registering interesting in y
After ComeFrom(y). FirstTime=True
After ComeFrom(y). FirstTime=False
Finished

So, the control flow is a bit like this:

Start SimpleEntryPoint
- Call into SimpleOtherMethod
  - Log "Start of SimpleOtherMethod"
  - Initialize the "count" variable with value 0
  - Register interest in x; ComeFrom remembers the continuation but keeps going.
  - Log "After ComeFrom x in SimpleOtherMethod. count=0. Returning."
  - Increment count to 1.
  - Return.
- Return takes us back to SimpleEntryPoint...
Log "First call to Label(x)"
Call Label("x")...
- ... which takes us back into SimpleOtherMethod (remember, the method we thought we'd finished executing?) just after ComeFrom
  - Log AfterComeFrom x in SimpleOtherMethod. count=1. Returning.
  - Increment count to 2.
  - Return.
- Return takes us back to SimpleEntryPoint...
Log "Second call to Label(x)"
Call Label("x")...
- ... which takes us back into SimpleOtherMethod again
  - Log AfterComeFrom x in SimpleOtherMethod. count=2. Returning.
  - Increment count to 3.
  - Return.
- Return takes us back to SimpleEntryPoint...
Log "Registering interest in y"
Initialize the "firstTime" variable with value true.
Register interest in y; ComeFrom remembers the continuation and keeps going
Log "After ComeFrom(y). FirstTime=True"
Check the value of firstTime... It's true, so:
- Set firstTime to false
- Call Label("y")
... which takes us back to earlier in the method (just after ComeFrom), like a normal looping construct...
Log "After ComeFrom(y). FirstTime=False"
Check the value of firstTime... It's false, so:
- Log "Finished"
- Exit!

Doing all of this has a few interesting challenges. Let's look at them one at a time... and I would strongly advise you not to try to pay too much attention to the details.

Noting a continuation and continuing regardless...

Just as a quick reminder before we get cracking, it's worth remembering that all of this is entirely synchronous, despite being implemented with async. There's only a single user thread involved here. As with previous parts, we maintain a stack of actions to call, and basically keep calling from the top until we're done - but the actions we call can create extra stack entries, of course.

ComeFrom has unusual semantics in terms of async. We want to remember the continuation and keep executing as if we didn't need to wait. We can easily do one side or the other. If we wanted to just keep going without needing to know about the continuation, we could just return true from IsCompleted. If we just want to remember the continuation, we can make the awaiter's IsCompleted property return false, and remember the continuation when it's passed to OnCompleted. How do we do both?

Well, effectively we want to remember the continuation and then call it immediately. But we can't just call it directly from OnCompleted, as otherwise each ComeFrom call would end up in a "real" execution stack from, whereas our execution stack is stored as a Stack<Action>. So instead, we need to remember the continuation and immediately put it at the top of the stack.

However, that only works if as soon as the generated code returns from the async method containing the ComeFrom call, we go back into the state machine. If we'd just called SimpleOtherMethod directly in SimpleEntryPoint, we would have continued within SimpleEntryPoint with the new stack entry just waiting around. This is why we need the Executor method: that does exactly the same thing, effectively shuffling the stack around. When it's given something to execute, it puts its own continuation on the action stack, then the action it's been asked to execute, then returns. The top level code will then pick up the original action, and we're away.

So, here's the code for Execute, which is the simplest part of the coordinator:

public ExecuteAwaiter Execute(Action<Coordinator> action)
{
    return new ExecuteAwaiter(() => action(this), this);
}

public class ExecuteAwaiter
{
    private readonly Action action;
    private readonly Coordinator coordinator;

    internal ExecuteAwaiter(Action action, Coordinator coordinator)
    {
        this.action = action;
        this.coordinator = coordinator;
    }

    public ExecuteAwaiter GetAwaiter()
    {
        return this;
    }

    // Always yield
    public bool IsCompleted { get { return false; } }

    public void OnCompleted(Action callerContinuation)
    {
        // We want to execute the action continuation, then get back here,
        // allowing any extra continuations put on the stack *within* the action
        // to be executed.
        coordinator.stack.Push(callerContinuation);
        coordinator.stack.Push(action);
    }

    public void GetResult()
    {
    }
}

All the awaitables in this project return themselves as the awaiter - when you don't need any other state, it's an easy step to take.

That's all we need to say about Execute, but how exactly are we capturing the continuation in ComeFrom?

Capturing continuations

Once we've got the action stack shuffling under our belts, there are two more problems with ComeFrom:

What happens if we ComeFrom the same label twice?
How do we really capture a continuation?

The first point didn't come up in the sample I've shown here, but it does come up in the more complex example - imagine if SimpleOtherMethod had two ComeFrom calls; when we jump back to the first one, we'll execute the second one again. I made a simple policy decision to only allow a single "return point" for any label - if a ComeFrom call tries to register the existing continuation point for a label, we ignore it; otherwise we throw an exception. So we only need to care about a single continuation for any label, which makes life easier.

The second point is trickier. If you remember back to earlier posts in this series, we saw that the state machine generated for async only really contains a single entry point (MoveNext) which is used for all continuations. A variable in the state machine is responsible for remembering where we were within it between calls. So in order to really make the continuation remember the point at which it needs to continue, we need to remember that state. We need to store an object for the continuation, which contains the delegate to invoke, and the state of the state machine when we were first passed the continuation. I've created a class for this, unimaginatively called Continuation, which looks like this:

/// <summary>
/// This hack allows a continuation to be executed more than once,
/// contrary to the C# spec. It does this using reflection to store the
/// value of the "state" field within the generated class. NEVER, EVER, EVER
/// try to use this in real code. It's purely for fun.
/// </summary>
internal sealed class Continuation : IEquatable<Continuation>
{
    private readonly int savedState;
    private readonly object target;
    private readonly FieldInfo field;
    private readonly Action action;

    internal Continuation(Action action)
    {
        target = action.Target;
        field = target.GetType().GetField("<>1__state", BindingFlags.Instance | BindingFlags.NonPublic);
        savedState = (int) field.GetValue(target);
        this.action = action;
    }

    internal void Execute()
    {
        field.SetValue(target, savedState);
        action();
    }

    // Snip Equals/GetHashCode
}

Yes, we use reflection to fish out the <>1__state variable initially, and poke the state machine with the same value when we next want to execute the continuation. All highly implementation-specific, of course.

Now the ComeFrom method is reasonably straightforward - all we need is a dictionary mapping labels to continuations. Oh, and the same action stack shuffling as for Execute:

// In the coordinator
private readonly Dictionary<string, Continuation> labels = new Dictionary<string, Continuation>();

public ComeFromAwaiter ComeFrom(string label)
{
    return new ComeFromAwaiter(label, this);
}

public struct ComeFromAwaiter
{
    private readonly string label;
    private readonly Coordinator coordinator;

    internal ComeFromAwaiter(string label, Coordinator coordinator)
    {
        this.label = label;
        this.coordinator = coordinator;
    }

    public ComeFromAwaiter GetAwaiter()
    {
        return this;
    }

    // We *always* want to be given the continuation
    public bool IsCompleted { get { return false; } }

    public void OnCompleted(Action action)
    {
        Continuation newContinuation = new Continuation(action);
        Continuation oldContinuation;
        if (!coordinator.labels.TryGetValue(label, out oldContinuation))
        {
            // First time coming from this label. Always succeeds.
            coordinator.labels[label] = newContinuation;
        }
        else
        {
            // Current semantics are to prohibit two different ComeFrom calls for the same label.
            // An alternative would be to just replace the existing continuation with the new one,
            // in which case we wouldn't need any of this - we could just use
            // coordinator.labels[label] = newContinuation;
            // unconditionally.
            if (!oldContinuation.Equals(newContinuation))
            {
                throw new InvalidOperationException("Additional continuation detected for label " + label);
            }
            // Okay, we've seen this one before. Nothing to see here, move on.
        }
        // We actually want to continue from where we were: we're only really marking the
        // ComeFrom point.
        coordinator.stack.Push(action);
    }

    public void GetResult()
    {
    }
}

There's one interesting point here which is somewhat subtle, and screwed me up for a bit...

The default value of a struct is always valid...

You may have noticed that ComeFromAwaiter is a struct. That's pretty unusual for me. However, it's also absolutely critical. Without it, we'd get a NullReferenceException when we execute the continuation the second time.

Normally, the flow of async methods looks a bit like this, for an await expression taking the "long" route (i.e. IsCompleted is false):

Call GetAwaiter() and assign the result to an awaiter field
Call IsCompleted (which returns false in this scenario)
Set the state variable to remember where we'd got to
Call OnCompleted
Return
... When we continue...
Set state to 0 (running)
Call GetResult() on the awaiter
Set the awaiter field to default(TypeOfAwaiter)
Continue

Now that's fine when we're only continuing once - but if we need to jump into the middle of that sequence a second time, we're going to call GetAwaiter() on the awaiter field after it's been set to the default value of the awaiter type. If the default value is null, we'll go bang. So we must use a struct.

Fortunately, our GetResult() call doesn't need any of the state in the awaiter - it's purely there to satisfy the normal flow of things. So we're quite happy with a "default" ComeFrom awaiter.

Finally, labels...

We've now done all the hard work. The final piece of the puzzle is Label, which just needs to check whether there's a continuation to jump to, and shuffle the action stack in the way we're now painfully accustomed to:

public LabelAwaiter Label(string label)
{
    Continuation continuation;
    labels.TryGetValue(label, out continuation);
    return new LabelAwaiter(continuation, this);
}

public class LabelAwaiter
{
    private readonly Continuation continuation;
    private readonly Coordinator coordinator;

    internal LabelAwaiter(Continuation continuation, Coordinator coordinator)
    {
        this.continuation = continuation;
        this.coordinator = coordinator;
    }

    public LabelAwaiter GetAwaiter()
    {
        return this;
    }

    // If there's no continuation to execute, just breeze through.
    public bool IsCompleted { get { return continuation == null; } }

    public void OnCompleted(Action action)
    {
        // We want to execute the ComeFrom continuation, then get back here.
        coordinator.stack.Push(action);
        coordinator.stack.Push(continuation.Execute);
    }

    public void GetResult()
    {
    }
}

Almost painfully simple, really.

So that looks like all the code that's used, right? Not quite...

Reusable builders?

As we saw in the sample code, we can end up finishing the same async method multiple times (SimpleOtherMethod completes three times). That's going to call SetResult on the AsyncVoidMethodBuilder three times... which feels like it should go bang. Indeed, when I revisited my code earlier I wondered why it didn't go bang - it's the sort of illegal state transition the framework is usually pretty good at picking up on.

Then I remembered - this isn't the framework's AsyncVoidMethodBuilder - it's mine. And my SetResult method in this project does absolutely nothing. How convenient!

Make it stop, make it stop!

Okay thiat was a pretty quick tour of some horrible code. You'll never have to do anything like this with async in sane code, but it certainly made me painfully familiar with how it all worked. Just to recap on the oddities involved:

We needed to capture a continuation and then immediately keep going, almost as if the awaiter had said the awaitable had completed already. This involved shenanigans with the execution model and an extra method (Execute)
We needed to remember the state of a continuation, which we did with reflection.
We needed to make awaiter.GetResult() a valid call after awaiter had been reset to the default value for the type
We needed to ensure that the builder created in the skeleton method could have SetResult called on it multiple times

That's all on continuations and co-routines, I promise.

Next time (hopefully soon) I'll look at an example of how composition works so neatly in async, and then show how we can unit test async methods - at least sometimes.

Laptop review: Kobalt G150

skeet — Sun, 18 Sep 2011 07:09:41 GMT

EDIT, 17th October 2011: Last week Kobalt closed down... so the choice about whether or not I'd buy from them again is now moot. However, PC Specialist sells a very similar spec, now including the matte screen...

As some of you will know, our house was burgled in April, and the thieves took three laptops (and very little else), including my main personal laptop. Obviously I ordered a replacement, partly covered by the insurance from my old laptop. However, I took the opportunity to spoil myself a little... I ordered a G150 from Kobalt Computers. Various people have taken an interest in the progress and results of this, so this post is a little review.

Specs

As I said, I spoiled myself a little... the specs are somewhat silly:

Overall, it's a G150 which is based on the Clevo P150HM chassis
Screen: 1920x1080, matte, 95% gamut
CPU: Intel Sandybridge Core-i7 2720QM; quad core 2.2-3.33GHz
Graphics: Nvidia GeForce GTX 580M
RAM: 16GB Corsair DDR3
Disk: SSD - Intel 510, 250GB
Optical: Blu-ray ROM; DVD/RW

How does it run?

Well how do you think it runs? :) Obviously it's very nippy indeed. I'm not sure I've ever used more than a couple of cores at a time yet, but it's nice to know I can test out parallelization when I want to :) While Windows Experience numbers are obviously pretty crude, they're pleasant enough that I might as well show them off:

Visual Studio 2010 still takes a while to come up (10-15 seconds) whereas Office components start pretty much instantly - so I don't know where the bottleneck for VS is. You can do an awful lot in terms of both disk and CPU in 10 seconds on this laptop, so it's a bit of a mystery. (Eclipse starts noticeably faster.) However, once running, Visual Studio is as fast as you'd expect on this machine - builds and tests are nippy, and the editor is noticeably more responsive than on the "make-do" laptop I've been using since April.

I can't say I'm much of a gamer, but my experiences in Call Of Duty: Black Ops and Portal 2 have been wonderful so far; I can put everything on high settings until it looks absolutely beautiful, and still get a good frame rate. I've never had a laptop with a really good graphics card before, and the one in this beast is one of the most powerful out there, so I've really got no excuse for not getting into gaming more, other than my obvious lack of free time. I'm also looking forward to investigating the possibility of writing code in C# to be executed on the GPU - I believe there are a couple of projects around that, so it'll be fun to look into.

With a fast SSD, the boot time is fabulously fast - although it does take a while to go to sleep, as I use hybrid sleep mode and it needs to dump memory to disk first. That's one downside of having a large amount of memory, of course. There's still a lot of debate around the longevity of solid state drives, but the improved performance is so noticeable that I'd definitely not go back to a "normal" hard drive now. I chose the Intel 510 over some slightly faster drives as the 510 is generally reckoned to be more reliable - so I'm hedging my bets somewhat. I suspect the difference in performance between "stupidly fast" and "ridiculously fast" is irrelevant to me.

The screen is beautiful - just "really nice" for normal desktop work, but amazing for games and video - that's where the matte nature really wins out. The contrast is particularly nice, at least in the short tests I've performed so far. The hinge feels pleasantly firm but not stiff - it's hard to judge this early, but hopefully it'll prove robust over time. This screen is one of the reasons I chose Kobalt - I believe they're the only UK company selling machines with this screen, and I'd certainly recommend that anyone who has the chance to go for the matte screen should do so.

Personally I use a separate keyboard most of the time (see below) but the keyboard on the G150 itself is a nice chiclet style one. I'm not terribly fond of the layout of the cursor keys of the fact that there's no separate home / end / page up / page down keys, but it's not a big deal. The feeling of the keys themselves is good, and not too loud. The trackpad is fine - I've turned off "tap to click" as it always ends up activating when I don't want to, but that's not specific to this particular laptop - I always find the same thing. Maybe I type with my palms particularly close to the trackpad, or something like that.

A few more random, esoteric points:

The power socket is "grippy" which makes it slightly harder to pull out the power, but does give a feeling of security. This is clearly a deliberate decision, and while it's not one which would suit everyone, I'm pretty happy with it.
The fan comes on and goes off reasonably regularly, which can prove a little distracting sometimes, but is the natural result of having a fast/hot laptop, I guess. The fan itself is fairly quiet under normal load, so I'd probably be fine with it being constantly on - it's the stop / start nature that jars a little. Not a big deal once you get used to it.
The webcam is really washed out - I don't think I'd really want to use it, to be honest. I don't know whether it's my particular hardware, the general make/model, or the settings (which I've played with and improved somewhat, but not to really acceptable levels)
The built-in microphone is located on the keyboard, which is a little bizarre and obviously not helpful for any time you'd be typing as well as talking. There's a lot of white noise with it compared with actual signal - I couldn't get a Skype test call to be audible without it also having huge amounts of hiss. Fortunately, this isn't a problem for me - I have a standalone microphone which I use for screencasts etc. That's previously been problematically quiet with other laptops, possibly due to drawing a lot of power - but it works perfectly with this laptop. I'm also getting a Corsair headset, which should be handy both for gaming and podcast recordings.
The machine itself is fairly bulky, and the power brick is huge - but the feeling of the chassis is a very attractive matte black. If you're looking for a sleek laptop to carry around a lot, this probably wouldn't be the best choice, but most of the time I keep my laptop on the same table at home. I went for a 15" rather than 17" as it makes a big difference when carrying it around to conferences, but the extra thickness required to house and cool the powerful components doesn't really bother me.

Overall, I'm really pleased with the laptop. As far as I can tell so far, the build quality is excellent - no problems at all. The poor quality of the microphone and webcam are a niggly disappointment, but not one that bothers me enough to find out whether they're "working as expected" or not.

The buying experience

This is where some of you may be relishing the prospect of reading a rant against Kobalt - but I'm not going to air lots of dirty laundry here. It did take a very long time for the laptop to arrive - over three months - but the causes of this were varied, and are worth mentioning at least in passing. I'm hoping that a summary of frustrations and the good parts will give the right impression without getting ugly.

My first cause of frustration occurred very early - before I'd even received a detailed order confirmation from Kobalt. They'd suffered from a high proportion of staff going down with norovirus around the time I ordered. This is the sort of thing which will obviously hit a small company like Kobalt rather more than bigger ones, but it wasn't a great start; for a week all I had was an email saying that I'd paid Kobalt for something, but I couldn't even check whether the details were right.

Some of the delays actually put Kobalt into a better light as far as I'm concerned. In particular, I'd originally ordered an AMD 6970 graphics card and a Vertex 3 SSD. Kobalt withdrew both of these components from sale: the 6970 was failing too often in testing, and the Vertex 3 was causing blue screens, sometimes in testing and occasionally on customer machines, due to an issue between the laptop chipset and the disk. Some other vendors would no doubt have kept selling these components and let the customer take the risk of losing the use of the laptop while it went back for repair, and I applaud Kobalt for not doing this.

Likewise my order was actually built twice: the first one failed testing - the motherboard failed, so had to be built from scratch. Again, I'm very happy about this - I'd obviously rather have a delay but get a working laptop in the end than get a defective one sooner. This also worked to my advantage in terms of the graphics card; although I'd only ordered a 485M, the first one was used in another customer's machine while waiting for a new motherboard for me... by which time the 485M was no longer readily available. Kobalt swapped in the 580M for no extra charge.

Other delays were only partially under Kobalt's control - for example, their order management system blew up in August. Can you blame a company for their internal systems failing? It's hard to say - and I'll be the first to admit I don't have the details. Was it due to cutting corners by getting a cheap ordering system which might be expected to be flaky? Was it due to something catastrophic which would only happen once in a million years? Should there have been better "emergency backup" procedures? I don't know - but it feels like something that customers shouldn't be exposed to.

One benefit of the delays was that I was able to change my order a couple of times - upping the CPU and memory, choosing a different graphics card and disk drive etc. Kobalt have been very flexible around this; it was considerably easier to change the configuration than I suspect it would have been with somewhere like Dell.

My main issue through all of this was communication - which wasn't all bad, but was definitely flaky. I suspect Kobalt would argue that I had unreasonable expectations, whereas I'd say it's just part of providing good customer service. The problems that Kobalt experienced obviously made all of this much worse than normal, but I still think there's a mismatched set of expectations there. I clearly wasn't the only one getting frustrated - the forums had a lot of posts complaining of a lack of updates - but equally, satisfied customers don't tend to post much to provide balance. It's very obvious on the forums that while people have been frustrated with the buying process, almost everyone's really happy with the machine they get in the end, and Kobalt are actually really good at answering questions about drivers etc afterwards.

My own experience of communicating with Kobalt was negative until the reasonably late stages of the order, but I was then phoned to be informed of the laptop coming out of testing and again to check shipping dates, which was good. (In this case it was particularly important as without the check, the laptop would have been delivered to the office on Saturday, where there may well not have been anyone prepared to sign for it.)

For a week or so after I received my laptop I still saw quite a few frustrated posts from other customers, but now that seems to have gone down significantly. It's possible that I'm just not seeing the other complaining posts (as such posts are often deleted - leading to the customer in question getting more frustrated, of course). I'm currently hopeful that I happen to have just ordered at a really bad time where Kobalt was suffering a series of unrelated problems. Whether they handled those as well as they could have done is up for debate, but hopefully new customers wouldn't see the same problems.

It should be noted that Kobalt is definitely trying to get better, too. In August they introduced a new Customer Promise around price, upgrades, and delivery times. In particular, if your order takes more than 6 weeks, you can choose between various games and accessories as a gift. (I chose two games from Steam.) Also, they're actively recruiting, so hopefully that will help on the communications front, too.

Accessories

As tends to happen while waiting for something, I got itchy and started buying accessories to go with the new laptop. I thought I might as well mention those at the same time...

External USB 3 drive: Western Digital MyPassport. I would probably have bought a eSata drive if I'd found one with as neat a form factor as this, but there just don't seem to be many eSata drives around yet. Hopefully this will change, as I do notice my USB mouse/keyboard responding sluggishly while I'm putting a lot of traffic through the drive - but apart from that, it's lovely. It's a really nice form factor, and seems to take advantage of the USB 3 ports on my laptop to deliver pretty reasonable performance. I'm expecting this to be used primarily for VMs - I've heard mixed reports of using VMs with SSDs, including the possibility that the two really don't play nicely, leading to early drive failure. I don't know whether this is accurate or not, but I'm being cautious. Overall, I'm pretty happy with this, although it's reasonably hard to get excited about a disk drive...

Keyboard: I do quite a bit of typing, and while I'm used to laptop keyboards, they're obviously somewhat constrained. I had previously been using a Logitech K340 which is nice, but I treated myself to a K800 for the new machine. Both of these use Logitech's "Unifying" receiver, which is wonderful - it's a tiny little receiver which I just leave permanently in the USB port. It works with quite a few Logitech peripherals, so I share the same receiver for my keyboard and the Anywhere MX mouse I use. The K800 keyboard is really nice - a lovely action, a sensible layout of Ins/Del/Home/End/PgUp/PgDn (which is its main benefit over the K340, to be honest) and it's rechargable via USB. The backlighting is a nice extra, although it's probably not going to actually be useful for me. It's fun to just wave your hand over it and watch it light up though... I'm easily pleased :)

I also bought a Belkin Screencast WiDi 2.0, which turns out to have been a mistake. I had thought that because I was using a Sandybridge laptop with an appropriate Intel wifi card, I'd be able to use WiDi - a technology which allows you to transmit video and sound to a receiver which can then plug into the TV. Yay, I can display Youtube etc on the TV without leaving the comfort of the sofa, right? Not so much - it turns out that this only works if you're also using the integrated graphics card; as I'm using a separate GPU, it's a no-go. This wasn't made as obvious as it might be on Intel's web site about WiDi - it's there if you dig, but it's not obvious. Just to be clear, this is in no way Kobalt's fault - they never claimed the new laptop would be WiDi compatible. I've now sent the Screencast (which was no use to me for anything else) to Kobalt so they can try it out with other laptops. (I suspect the GS150 may work with it, for example.)

VM experiment

As I've tweeted before, I did have one hope for actually using most of the 16GB of memory. I don't want to run VMs directly from the SSD, as I mentioned before - but I had a thought of having the virtual disk on the SSD, but then mounting it as a ram drive. That way I'd only need to write to the disk after shutting down the VM - one big write instead of frequent spraying access.

That would only work with a small drive, of course... but I hoped I'd just about be able to get Windows 7 Home Premium + Visual Studio into a small enough drive. With 1GB of memory for the VM and 2GB of memory for the host machine I can have a 13GB ram drive - and I can install Windows 7 on that using Virtual PC, but Virtual PC also uses disk space alongside the VHD for memory for the VM, which obviously takes another 1GB off the usable size. I nearly managed it, but not quite. I may give it another go with Virtual Box and the Express edition of VS11... I'll blog again if I get it working, but I didn't want to hold up this post forever...

In terms of getting anything working, it took a little while - DataRam's RAMDisk product kept hanging while closing down; imdisk gave me access problems even after trying all the suggested tweaks, but VSuite Ramdisk (server edition) seems to do the job. It's not hugely cheap (and I need the server edition to support a drive over 4GB) but if I can get everything working, I may go with it. Currently I'm using the trial edition.

Conclusion

I guess the obvious question to ask is "If I had my time again, would I take the same action?"

Well, it's obviously been a frustrating experience, but the results should keep me happy for a long time. I think I would be cautious about buying from Kobalt again, but probably less so than you might expect. I'd probably hang out in the forums for a while to see whether folks were generally happy at the time. I'm hoping I was just unlucky, and hit a particularly nasty time in Kobalt's history - I can't imagine the staff there have enjoyed those three months any more than I did - and that normally everything runs smoothly. If I were in a real hurry I'd probably go for an off-the-shelf solution, but that's a different matter - when you buy a custom machine you should expect it to take a bit longer. Just not three months, normally :)

I'd certainly be happy to buy from Kobalt again in terms of the quality of the product - it's a lovely laptop, and I'm delighted with its performance, display and general handling. Obviously I regret buying the Screencast, but all my other decisions - memory, disk, external keyboard etc - have turned out well so far.

Upcoming speaking engagements

skeet — Fri, 02 Sep 2011 16:53:17 GMT

It's just occurred to me that I've forgotten to mention a few of the things I'll be up to in the near-ish future. (I've talked about next week's Progressive .NET session before.) This is just a quick rundown - follow the links for more blurb and details.

.NET Developer Network - Bristol, September 21st (evening)

I'll be talking about async in Bristol - possibly at a high level, possibly in detail, depending on the audience experience. This is my first time talking with this particular user group, although I'm sure there'll be some familiar faces. Come along if you're in the area.

Øredev 2011 - Malmö, November 9th

It's a whistle-stop trip to Sweden as I'm running out of vacation days; I'm flying out on the Tuesday evening and back on the Wednesday evening, but while I'm there I'll give two talks:

Async 101 (yes, more async; I wonder at what point I'll have given as many talks about it as Mads)
Effective technical communication (not a particularly technical talk, but definitely specific to technical communication)

Last year I had an absolute blast - looking forward to this year, even though I won't have as much time for socializing.

Stack Overflow Dev Days 2011 - London, November 14th - cancelled!

Update: Dev Days has been cancelled. I'm still hoping to do something around this topic, and there may be small-scale meet-ups in London anyway.

Two years ago I talked about how humanity had let the world of software engineering down. This was one of the best talks I've ever given, and introduced the world to Tony the Pony. Unfortunately that puts the bar relatively high for this year's talk - at least, high by my own pretty low standards.

In a somewhat odd topic for a Christian and a happy employee of a company with a code of conduct which starts "Don't be evil," this year's talk is entitled "Thinking in evil." As regular readers are no doubt aware, I love torturing the C# language and forcing the compiler to work with code which would make any right-thinking software engineer cringe. I was particularly gratified recently when Eric Lippert commented on one of my Stack Overflow answers that this was "the best abuse of C# I've seen in a while." I'm looking forward to talking about why I think it's genuinely a good idea to think about nasty code like this - not to use it, but to get to know your language of choice more intimately. Like last time, I have little idea of exactly what this talk will be like, but I'm really looking forward to it.

Optimization and generics, part 2: lambda expressions and reference types

skeet — Mon, 22 Aug 2011 23:06:18 GMT

As with almost any performance work, your mileage may vary (in particular the 64-bit JIT may work differently) and you almost certainly shouldn't care. Relatively few people write production code which is worth micro-optimizing. Please don't take this post as an invitation to make code more complicated for the sake of irrelevant and possibly mythical performance changes.

It took me a surprisingly long time to find the problem described in the previous blog post, and almost no time at all to fix it. I understood why it was happening. This next problem took a while to identify at all, but even when I'd found a workaround I had no idea why it worked. Furthermore, I couldn't reproduce it in a test case... because I was looking for the wrong set of triggers. I've now found at least some of the problem though.

This time the situation in Noda Time is harder to describe, although it concerns the same area of code. In various places I need to create new delegates containing parsing steps and add them to the list of steps required for a full parse. I can always use lambda expressions, but in many cases I've got the same logic repeatedly... so I decided to pull it out into a method. Bang - suddenly the code runs far slower. (In reality, I'd performed this refactoring first, and "unrefactored" it to speed things up.)

I think the problem comes down to method group conversions with generic methods and a type argument which is a reference type. The CLR isn't very good at them, and the C# compiler uses them more than it needs to.

Show me the benchmark!

The complete benchmark code is available of course, but fundamentally I'm doing the same thing in each test case: creating a delegate of type Action which does nothing, and then checking that the delegate reference is non-null (just to avoid the JIT optimizing it away). In each case this is done in a generic method with a single type parameter. I call each method in two ways: once with int as the type argument, and once with string as the type argument. Here are the different cases involved:

Use a lambda expression: Action foo = () => {};
Fake what I expected the compiler to do: keep a separate generic cache class with a static variable for the delegate; populate the cache once if necessary, and thereafter use the cache field
Fake what the compiler is actually doing with the lambda expression: write a separate generic method and perform a method group conversion to it
Do what the compiler could do: write a separate non-generic method and perform a method group conversion to it
Use a method group conversion to a static (non-generic) method on a generic type
Use a method group conversion to an instance (non-generic) method on a generic type, via a generic cache class with a single field in referring to an instance of the generic class

(Yes, the last one is a bit convoluted - but the line in the method itself is simple: Action foo = ClassHolder<T>.SampleInstance.NoOpInstance;

Remember, we're doing each of these in a generic method, and calling that generic method using a type argument of either int or string. (I've run a few tests, and the exact type isn't important - all that matters is that int is a value type, and string is a reference type.)

Importantly, we're not capturing any variables, and the type parameter is not involved in either the delegate type or any part of the implementation body.

Benchmark results

Again, times are in milliseconds - but this time I didn't want to run it for 100 million iterations, as the "slow" versions would have taken far too long. I've run this on the x64 JIT as well and seen the same effect, but I haven't included the figures here.

Times in milliseconds for 10 million iterations

Test	TestCase<int>	TestCase<string>
Lambda expression	180	29684
Generic cache class	90	288
Generic method group conversion	184	30017
Non-generic method group conversion	178	189
Static method on generic type	180	29276
Instance method on generic type	202	299

Yes, it's about 150 times slower to create a delegate from a generic method with a reference type as the type argument than with a value type... and yet this is the first I've heard of this. (I wouldn't be surprised if there were a post from the CLR team about it somewhere, but I don't think it's common knowledge by any means.)

Conclusion

One of the tricky things is that it's hard to know exactly what the C# compiler is going to do with any given lambda expression. In fact, the method which was causing me grief earlier on isn't generic, but it's in a generic type and captures some variables which use the type parameters - so perhaps that's causing a generic method group conversion somewhere along the way.

Noda Time is a relatively extreme case, but if you're using delegates in any performance-critical spots, you should really be aware of this issue. I'm going to ping Microsoft (first informally, and then via a Connect report if that would be deemed useful) to see if there's an awareness of this internally as potential "gotcha", and whether there's anything that can be done. Normal trade-offs of work required vs benefit apply, of course. It's possible that this really is an edge case... but with lambdas flying everywhere these days, I'm not sure that it is.

Maybe tomorrow I'll actually be able to finish getting Noda Time moved onto the new system... all of this performance work has been a fun if surprising distraction from the main job of shipping working code...

Optimization and generics, part 1: the new() constraint (updated: now with CLR v2 results)

skeet — Mon, 22 Aug 2011 21:57:55 GMT

I've been doing quite a bit of work on Noda Time recently - and have started getting my head round all the work that James Keesey has put into the parsing/formatting. I've been reworking it so that we can do everything without throwing any exceptions, and also to work on the idea of parsing a pattern once and building a sequence of actions for both formatting and parsing from the action. To format or parse a value, we then just need to apply the actions in turn. Simples.

Given that this is all in the name of performance (and I consider Noda Time to be worth optimizing pretty hard) I was pretty cross when I ran a complete revamp through the little benchmarking tool we use, and found that my rework had made everything much slower. Even parsing a value after parsing the pattern was slower than parsing both the value and the pattern together. Something was clearly very wrong.

In fact, it turns out that at least two things were very wrong. The first (the subject of this post) was easy to fix and actually made the code a little more flexible. The second (the subject of the next post, which may be tomorrow) is going to be harder to work around.

The new() constraint

In my SteppedPattern type, I have a generic type parameter - TBucket. It's already constrained in terms of another type parameter, but that's irrelevant as far as I'm aware. (After today though, I'm taking very little for granted...) The important thing is that before I try to parse a value, I want to create a new bucket. The idea is that bits of information end up in the bucket as they're being parsed, and at the very end we put everything together. So each parse operation requires a new bucket. How can we create one in a nice generic way?

Well, we can just call its public parameterless constructor. I don't mind the types involved having such a constructor, so all we need to do is add the new() constraint, and then we can call new TBucket():

// Somewhat simplified...
internal sealed class SteppedPattern<TResult, TBucket> : IParsePattern<TResult>
    where TBucket : new()
{
    public ParseResult<TResult> Parse(string value)
    {
        TBucket bucket = new TBucket();

        // Rest of parsing goes here
    }
}

Great! Nice and simple. Unfortunately, it turned out that that one line of code was taking 75% of the time to parse a value. Just creating an empty bucket - pretty much the simplest bit of parsing. I was amazed when I discovered that.

Fixing it with a provider

The fix is reasonably easy. We just need to tell the type how to create an instance, and we can do that with a delegate:

// Somewhat simplified...
internal sealed class SteppedPattern<TResult, TBucket> : IParsePattern<TResult>
{
    private readonly Func<TBucket> bucketProvider;

    internal SteppedPattern(Func<TBucket> bucketProvider)
    {
        this.bucketProvider = bucketProvider;
    }

    public ParseResult<TResult> Parse(string value)
    {
        TBucket bucket = bucketProvider();

        // Rest of parsing goes here
    }
}

Now I can just call new SteppedPattern(() => new OffsetBucket()) or whatever. This also means I can keep the constructor internal, not that I care much. I could even reuse old parse buckets if that wouldn't be a semantic problem - in other cases it could be useful. Hooray for lambda expressions - until we get to the next post, anyway.

Show me the figures!

You don't want to have to run Noda Time's benchmarks to see the results for yourself, so I wrote a small benchmark to time just the construction of a generic type. As a measure of how insignificant this would be for most apps, these figures are in milliseconds, performing 100 million iterations of the action in question. Unless you're going to do this in performance-critical code, you just shouldn't care.

Anyway, the benchmark has four custom types: two classes, and two structs - a small and a large version of each. The small version has a single int field; the large version has eight long fields. For each type, I benchmarked both approaches to initialization.

The results on two machines (32-bit and 64-bit) are below, for both the v2 CLR and v4. The 64-bit machine is much faster in general - you should only compare results within one machine, as it were.)

CLR v4: 32-bit results (ms per 100 million iterations)

Test type	new() constraint	Provider delegate
Small struct	689	1225
Large struct	11188	7273
Small class	16307	1690
Large class	17471	3017

CLR v4: 64-bit results (ms per 100 million iterations)

Test type	new() constraint	Provider delegate
Small struct	473	868
Large struct	2670	2396
Small class	8366	1189
Large class	8805	1529

CLR v2: 32-bit results (ms per 100 million iterations)

Test type	new() constraint	Provider delegate
Small struct	703	1246
Large struct	11411	7392
Small class	143967	1791
Large class	143107	2581

CLR v2: 64-bit results (ms per 100 million iterations)

Test type	new() constraint	Provider delegate
Small struct	510	686
Large struct	2334	1731
Small class	81801	1539
Large class	83293	1896

(An earlier version of this post had a mistake - my original tests used structs for everything, despite the names.)

Others have reported slightly different results, including the new() constraint being better for both large and small structs.

Just in case you hadn't spotted them, look at the results for classes. Those are the real results - it took over 2 minutes to run the test using the new() constraint on my 32-bit laptop, compared with under two seconds for the provider. Yikes. This was actually the situation I was in for Noda Time, which is built on .NET 2.0 - it's not surprising that so much of my benchmark's time was spent constructing classes, given results like this.

Of course you can download the benchmark program for yourself and see how it performs on your machine. It's a pretty cheap-and-cheerful benchmark, but when the differences are this big, minor sources of inaccuracy don't bother me too much. The simplest way to run under CLR v2 is to compile with the .NET 3.5 C# compiler to start with.

What's going on under the hood?

As far as I'm aware, there's no IL to give support for the new() constraint. Instead, the compiler emits a call to Activator.CreateInstance<T>. Apparently, that's slower than calling a delegate - presumably due to trying to find an accessible constructor with reflection, and invoking it. I suspect it could be optimized relatively easily - e.g. by caching the results per type it's called with, in terms of delegates. I'm slightly surprised this hasn't (apparently) been optimized, given how easy it is to cache values by generic type. No doubt there's a good reason lurking there somewhere, even if it's only the memory taken up by the cache.

Either way, it's easy to work around in general.

Conclusion

I wouldn't have found this gotcha if I didn't have before and after tests (or in this case, side-by-side tests of the old way and the new way of parsing). The real lesson of this post shouldn't be about the new() constraint - it should be how important it is to test performance (assuming you care), and how easy it is to assume certain operations are cheap.

Next post: something much weirder.

Speaking engagement: Progressive .NET, London, September 7th

skeet — Thu, 28 Jul 2011 20:29:40 GMT

Just a quick note to mention an event I'll be speaking at in September. SkillsMatter will be hosting Progressive .NET, a 3-day event set of tutorials on September 5th-7th in London. I'll be speaking about C# 5's async feature on the last day (9.30am-1pm) but there's a host of other speakers too. Should be good. For my own part, with four hours or so to cover async, I should be able to cover both the high level stuff and the implementation details, with plenty of time for the inevitable questions.

This one isn't free though, I'm afraid - it's normally £425. Hardly pocket money, but pretty good value for three full days of deep-dive sessions. However, there are two bits of good news:

Readers of this blog can get £50 off using the promo code "PROGNET50" at the checkout.
I have two free tickets to give away.

In an effort to make the ticket give-away fair, I'm thinking of a 32-bit number - mail me (skeet@pobox.com) an Int32, and the two readers with the closest value will get the tickets. Please include "Progressive .NET" in the subject line of the mail so I can filter them easily :)

Anyway, hope to see you there - please grab me to say hi.

Update (August 4th): and the winners are...

Congratulations to The Configurator and Haris Hasan who submitted the closest numbers to the one I was thinking of: -890978631.

In fact, The Configurator guessed the exact value - which is the result of calling "Progressive .NET".GetHashCode() on my 32-bit laptop running .NET 4. (I can't remember which versions have different hash algorithms, but as it's pretty arbitrary, it seemed good enough...) I'm impressed!

I'll be emailing SkillsMatter to let them know about the winners - and thanks to everyone else who mailed me a guess. Hope I'll see some of you there anyway!

Eduasync part 14: Data passing in coroutines

skeet — Wed, 29 Jun 2011 17:18:20 GMT

(This post covers project 19 in the source code.)

Last time we looked at independent coroutines running in a round-robin fashion. This time we'll keep the round-robin scheduling, but add in the idea of passing data from one coroutine to another. Each coroutine will act on data of the same type, which is necessary for the scheme to work when one coroutine could "drop out" of the chain by returning.

Designing the data flow

It took me a while to get to the stage where I was happy with the design of how data flowed around these coroutines. I knew I wanted a coordinator as before, and that it should have a Yield method taking the value to pass to the next coroutine and returning an awaitable which would provide the next value when it completed. The tricky part was working out what to do at the start of each method and the end. If the method just took a Coordinator parameter, we wouldn't have anything to do with the value yielded by the first coroutine, because the second coroutine wouldn't be ready to accept it yet. Likewise when a coroutine completed, we wouldn't have another value to pass to the next coroutine.

Writing these dilemmas out in this post, the solution seems blindingly obvious of course: each coroutine should accept a data value on entry, and return one at the end. At any point where we transfer control, we provide a value and have a value which is required by something. The final twist is to make the coordinator's Start method take an initial value and return the value returned by the last coroutine to complete.

So, that's the theory... let's look at the implementation.

Initialization

I've changed the coordinator to take all the coroutines as a constructor parameter (of the somewhat fearsome declaration "params Func<Coordinator<T>, T, Task<T>>[] coroutines") which means we don't need to implement IEnumerable pointlessly any more.

This leads to a code skeleton of this form:

private static void Main(string[] args)
{
    var coordinator = new Coordinator<string>(FirstCoroutine,
                                              SecondCoroutine,
                                              ThirdCoroutine);
    string finalResult = coordinator.Start("m1");
    Console.WriteLine("Final result: {0}", finalResult);
}

private static async Task<string> FirstCoroutine(
    Coordinator<string> coordinator,
    string initialValue)
{
    ...
}

// Same signature for SecondCoroutine and ThirdCoroutine

Last time we simply had a Queue<Action> internally in the coordinator as the actions to invoke. You might be expecting a Queue<Func<T, T>> this time - after all, we're passing in data and returning data at each point. However, the mechanism for that data transfer is "out of band" so to speak. The only time we really "return" an item is when we reach the end of a coroutine. Usually we'll be providing data to the next step using a method. Likewise the only time a coroutine is given data directly is in the first call - after that, it will have to fetch the value by calling GetResult() on the awaiter which it uses to yield control.

All of this is leading to a requirement for our constructor to convert each coroutine delegate into a simple Action. The trick is working out how to deal with the data flow. I'm going to include SupplyValue() and ConsumeValue() methods within the coordinator for the awaiter to use, so it's just a case of calling those appropriately from our action. In particular:

When the action is called, it should consume the current value.
It should then call the coroutine passing in the coordinator ("this") and the initial value.
When the task returned by the coroutine has completed, the result of that task should be used to supply a new value.

The only tricky part here is the last bullet - and it's not that hard really, so long as we remember that we're absolutely not trying to start any new threads. We just want to hook onto the end of the task, getting a chance to supply the value before the next coroutine tries to pick it up. We can do that using Task.ContinueWith, but passing in TaskContinuationOptions.ExecuteSynchronously so that we use the same thread that the task completes on to execute the continuation.

At this point we can implement the initialization part of the coordinator, assuming the presence of SupplyValue() and ConsumeValue():

public sealed class Coordinator<T>
{
    private readonly Queue<Action> actions;
    private readonly Awaitable awaitable;

    public Coordinator(params Func<Coordinator<T>, T, Task<T>>[] coroutines)
    {
        // We can't refer to "this" in the variable initializer. We can use
        // the same awaitable for all yield calls.
        this.awaitable = new Awaitable(this);
        actions = new Queue<Action>(coroutines.Select(ConvertCoroutine));
    }

    // Converts a coroutine into an action which consumes the current value,
    // calls the coroutine, and attaches a continuation to it so that the return
    // value is used as the new value.
    private Action ConvertCoroutine(Func<Coordinator<T>, T, Task<T>> coroutine)
    {
        return () =>
        {
            Task<T> task = coroutine(this, ConsumeValue());
            task.ContinueWith(ignored => SupplyValue(task.Result),
                TaskContinuationOptions.ExecuteSynchronously);
        };
    }
}

I've broken ConvertCoroutine into a separate method so that we can use it as the projection for the Select call within the constructor. I did initially have it within a lambda expression within the constructor, but it was utterly hideous in terms of readabililty.

One suggestion I've received is that I could declare a new delegate type instead of using Func<Coordinator<T>, T, Task<T>> to represent a coroutine. This could either be a non-generic delegate nested in the generic coordinator class, or a generic stand-alone delegate:

public delegate T Coroutine<T>(Coordinator<T> coordinator, T initialValue);

// Or nested...
public sealed class Coordinator<T>
{
public delegate T Coroutine(Coordinator<T> coordinator, T initialValue);
}

Both of these would work perfectly well. I haven't made the change at the moment, but it's certainly worth considering. The debate about whether to use custom delegate types or Func/Action is one for another blog post, I think :)

The one bit of the initialization I haven't explained yet is the "awaitable" field and the Awaitable type. They're to do with yielding - so let's look at them now.

Yielding and transferring data

Next we need to work out how we're going to transfer data and control between the coroutines. As I've mentioned, we're going to use a method within the coordinator, called from the coroutines, to accomplish this. The coroutines have this sort of code:

private static async Task<string> FirstCoroutine(
    Coordinator<string> coordinator,
    string initialValue)
{
    Console.WriteLine("Starting FirstCoroutine with initial value {0}",
                      initialValue);
    ...
    string received = await coordinator.Yield("x1");
    Console.WriteLine("Returned to FirstCoroutine with value {0}", received);
    ...
    return "x3";
}

The method name "Yield" here is a double-edged sword. The word has two meanings - yielding a value to be used elsewhere, and yielding control until we're called back. Normally it's not ideal to use a name that can mean subtly different things - but in this case we actually want both of these meanings.

So, what does Yield need to do? Well, the flow control should look something like this:

Coroutine calls Yield()
Yield() calls SupplyValue() internally to remember the new value to be consumed by the next coroutine
Yield() returns an awaitable to the coroutine
Due to the await expression, the coroutine calls GetAwaiter() on the awaitable to get an awaiter
The coroutine checks IsCompleted on the awaiter, which must return false (to prompt the remaining behaviour)
The coroutine calls OnCompleted() passing in the continuation for the rest of the method
The coroutine returns to its caller
The coordinator proceeds with the next coroutine
When we eventually get back to this coroutine, it will call GetResult() to get the "current value" to assign to the "received" variable.

Now you'll see that Yield() needs to return some kind of awaitable type - in other words, one with a GetAwaiter() method. Previously we put this directly on the Coordinator type, and we could have done that here - but I don't really want anyone to just "await coordinator" accidentally. You should really need to call Yield() in order to get an awaitable. So we have an Awaitable type, nested in Coordinator.

We then need to decide what the awaiter type is - the result of calling GetAwaiter() on the awaitable. This time I decided to use the Coordinator itself. That means people could accidentally call IsCompleted, OnCompleted() or GetResult(), but I figured that wasn't too bad. If we were to go to the extreme, we'd create another type just for the Awaiter as well. It would need to have a reference to the coordinator of course, in order to actually do its job. As it is, we can make the Awaitable just return the Coordinator that created it. (Awaitable is nested within Coordinator<T>, which is how it can refer to T without being generic itself.)

public sealed class Awaitable
{
    private readonly Coordinator<T> coordinator;

    internal Awaitable(Coordinator<T> coordinator)
    {
        this.coordinator = coordinator;
    }

    public Coordinator<T> GetAwaiter()
    {
        return coordinator;
    }
}

The only state here is the coordinator, which is why we create an instance of Awaitable on the construction of the Coordinator, and keep it around.

Now Yield() is really simple:

public Awaitable Yield(T value)
{
SupplyValue(value);
return awaitable;
}

So to recap, we now just need the awaiter members, SupplyValue() and ConsumeValue(). Let's look at the awaiter members (in Coordinator) to start with. We already know that IsCompleted will just return false. OnCompleted() just needs to stash the continuation in the queue, and GetResult() just needs to consume the "current" value and return it:

public bool IsCompleted { get { return false; } }

public void OnCompleted(Action continuation)
{
actions.Enqueue(continuation);
}

public T GetResult()
{
return ConsumeValue();
}

Simple, huh? Finally, consuming and supplying values:

private T currentValue;
private bool valuePresent;

private void SupplyValue(T value)
{
    if (valuePresent)
    {
        throw new InvalidOperationException
            ("Attempt to supply value when one is already present");
    }
    currentValue = value;
    valuePresent = true;
}

private T ConsumeValue()
{
    if (!valuePresent)
    {
        throw new InvalidOperationException
            ("Attempt to consume value when it isn't present");
    }
    T oldValue = currentValue;
    valuePresent = false;
    currentValue = default(T);
    return oldValue;
}

These are relatively long methods (compared with the other ones I've shown) but pretty simple. Hopefully they don't need explanation :)

The results

Now that everything's in place, we can run it. I haven't posted the full code of the coroutines, but you can see it on Google Code. Hopefully the results speak for themselves though - you can see the relevant values passing from one coroutine to another (and in and out of the Start method).

Starting FirstCoroutine with initial value m1
Yielding 'x1' from FirstCoroutine...
    Starting SecondCoroutine with initial value x1
    Starting SecondCoroutine
    Yielding 'y1' from SecondCoroutine...
        Starting ThirdCoroutine with initial value y1
        Yielding 'z1' from ThirdCoroutine...
Returned to FirstCoroutine with value z1
Yielding 'x2' from FirstCoroutine...
    Returned to SecondCoroutine with value x2
    Yielding 'y2' from SecondCoroutine...
        Returned to ThirdCoroutine with value y2
        Finished ThirdCoroutine...
Returned to FirstCoroutine with value z2
Finished FirstCoroutine
    Returned to SecondCoroutine with value x3
    Yielding 'y3' from SecondCoroutine...
    Returned to SecondCoroutine with value y3
    Finished SecondCoroutine
Final result: y4

Conclusion

I'm not going to claim this is the world's most useful coroutine model - or indeed useful at all. As ever, I'm more interested in thinking about how data and control flow can be modelled than actual usefulness.

In this case, it was the realization that everything should accept and return a value of the same type which really made it all work. After that, the actual code is pretty straightforward. (At least, I think it is - please let me know if any bits are confusing, and I'll try to elaborate on them.)

Next time we'll look at something more like a pipeline model - something remarkably reminiscent of LINQ, but without taking up as much stack space (and with vastly worse readability, of course). Unfortunately the current code reaches the limits of my ability to understand why it works, which means it far exceeds my ability to explain why it works. Hopefully I can simplify it a bit over the next few days.

Eduasync part 13: first look at coroutines with async

skeet — Wed, 22 Jun 2011 20:37:30 GMT

(This part covers project 18 in the source code.)

As I mentioned in earlier parts, the "awaiting" part of async methods is in no way limited to tasks. So long as we have a suitable GetAwaiter() method which returns a value of a type which in turn has suitable methods on it, the compiler doesn't really care what's going on. It's time to exploit that to implement some form of coroutines in C#.

Introduction to coroutines

The fundamental idea of coroutines is to have multiple methods executing cooperatively, each of them maintaining their position within the coroutine when they yield to another. You can almost think of them as executing in multiple threads, with only one thread actually running at a time, and signalling between the different threads to control flow. However, we don't really need multiple threads once we've got continuations - we can have a single thread with a complex flow of continuations, and still only a very short "real" stack. (The control flow is stored in normal collections instead of being implicit on the thread's stack.)

Coroutines were already feasible in C# through the use of iterator blocks, but the async feature of C# allows a slightly more natural way of expressing them, in my view. (The linked Wikipedia page gives a sketch of how coroutines can be built on top of generators, which in the general concept that iterator blocks implement in C#.)

I have implemented various flavours of coroutines in Eduasync. It's possible that some (all?) of them shouldn't strictly be called coroutines, but they're close enough to the real thing in feeling. This is far from an exhaustive set of approaches. Once you've got the basic idea of what I'm doing, you may well want to experiment with your own implementations.

I'm not going to claim that the use of coroutines in any of my examples really makes any sense in terms of making real tasks easier. This is purely for the sake of interest and twisting the async feature for fun.

Round-robin independent coroutines

Our first implementation of coroutines is relatively simple. A coordinator effectively "schedules" the coroutines it's set up with in a round-robin fashion: when one of the coroutines yields control to the coordinator, the coordinator remembers where the coroutine had got to, and then starts the next one. When each coroutine has executed its first piece of code and yielded control, the coordinator will go back to the first coroutine to continue execution, and so on until all coroutines have completed.

The coroutines don't know about each other, and no data is being passed between them.

Hopefully it's reasonably obvious that the coordinator contains all the smarts here - the coroutines themselves can be relatively dumb. Let's look at what the client code looks like (along with the results) before we get to the coordinator code.

Client code

The sample code contains three coroutines, all of which take a Coordinator parameter and have a void return type. These are passed to a new coordinator using a collection initializer and method group conversions; the coordinator is then started. Here's the entry point code for this:

private static void Main(string[] args)
{
    var coordinator = new Coordinator {
        FirstCoroutine,
        SecondCoroutine,
        ThirdCoroutine
    };
    coordinator.Start();
}

When each coroutine is initially started, the coordinator passes a reference to itself as the argument to the coroutine. That's how we solve the chicken-and-egg problem of the coroutine and coordinator having to know about each other. The way a coroutine yields control is simply by awaiting the coordinator. The result type of this await expression is void - it's just a way of "pausing" the coroutine.

We're not doing anything interesting in the actual coroutines - just tracing the execution flow. Of course we could do anything we wanted, within reason. We could even await a genuinely asynchronous task such as fetching a web page asynchronously. In that case the whole coroutine collection would be "paused" until the fetch returned.

Here's the code for the first coroutine - the second and third ones are similar, but use different indentation for clarity. The third coroutine is also shorter, just for fun - it only awaits the coordinator once.

private static async void FirstCoroutine(Coordinator coordinator)
{
    Console.WriteLine("Starting FirstCoroutine");
    Console.WriteLine("Yielding from FirstCoroutine...");

    await coordinator;

    Console.WriteLine("Returned to FirstCoroutine");
    Console.WriteLine("Yielding from FirstCoroutine again...");

    await coordinator;

    Console.WriteLine("Returned to FirstCoroutine again");
    Console.WriteLine("Finished FirstCoroutine");
}

And here's the output...

Starting FirstCoroutine
Yielding from FirstCoroutine...
    Starting SecondCoroutine
    Yielding from SecondCoroutine...
        Starting ThirdCoroutine
        Yielding from ThirdCoroutine...
Returned to FirstCoroutine
Yielding from FirstCoroutine again...
    Returned to SecondCoroutine
    Yielding from SecondCoroutine again...
        Returned to ThirdCoroutine
        Finished ThirdCoroutine...
Returned to FirstCoroutine again
Finished FirstCoroutine
    Returned to SecondCoroutine again
    Finished SecondCoroutine

Hopefully that's the output you expected, given the earlier description. Again it may help if you think of the coroutines as running in separate pseudo-threads: the execution within each pseudo-thread is just linear, and the timing is controlled by our explicit "await" expressions. All of this would actually be pretty easy to implement using multiple threads which really did just block on each await expression - but the fun part is keeping it all in one real thread. Let's have a look at the coordinator.

The Coordinator class

Some of the later coroutine examples end up being slightly brainbusting, at least for me. This one is relatively straightforward though, once you've got the basic idea. All we need is a queue of actions to execute. After initialization, we want our queue to contain the coroutine starting points.

When a coroutine yields control, we just need to add the remainder of it to the end of the queue, and move on to the next item. Obviously the async infrastructure will provide "the remainder of the coroutine" as a continuation via the OnContinue method.

When a coroutine just returns, we continue with the next item in the queue as before - it's just that we won't add a continuation to the end of the queue. Eventually (well, hopefully) we'll end up with an empty queue, at which point we can stop.

Initialization and a choice of data structures

We'll represent our queue using Queue<T> where the T is a delegate type. We have two choices here though, because we have two kinds of delegate - one which takes the Coordinator as a parameter (for the initial coroutine setup) and one which has no parameters (for the continuations). Fortunately we can convert between the two in either direction very simply, bearing in mind that all of this is within the context of a coordinator. For example:

// If we're given a coroutine and want a plain Action
Action<Coordinator> coroutine = ...;
Action action = () => coroutine(this);

// If we're given a plain Action and want an Action<Continuation>:
Action continuation = ...;
Action<Coordinator> coroutine = ignored => continuation();

I've arbitrarily chosen to use the first option, so there's a Queue<Action> internally.

Now we need to get the collection initializer working. The C# compiler requires an appropriate Add method (which is easy) and also checks that the type implements IEnumerable. We don't really need to be able to iterate over the queue of actions, so I've use explicit interface implementation to reduce the likelihood of GetEnumerator() being called inappropriately, and made the method throw an exception for good measure. That gives us the skeleton of the class required for setting up:

public sealed class Coordinator : IEnumerable
{
    private readonly Queue<Action> actions = new Queue<Action>();

    // Used by collection initializer to specify the coroutines to run
    public void Add(Action<Coordinator> coroutine)
    {
        actions.Enqueue(() => coroutine(this));
    }

    // Required for collection initializers, but we don't really want
    // to expose anything.
    IEnumerator IEnumerable.GetEnumerator()
    {
        throw new NotSupportedException("IEnumerable only supported to enable collection initializers");
    }
}

(Note that I haven't used XML documentation anywhere here - it's great for real code, but adds clutter in blog posts.)

For production code I'd probably prevent Add from being called after the coordinator had been started, but there's no need to do it in our well-behaved sample code. We're only going to add extra actions to the queue via continuations, which will be added due to await expressions.

The main execution loop and async infrastructure

So far we've got code to register coroutines in the queue - so now we need to execute them. Bearing in mind that the actions themselves will be responsible for adding continuations, the main loop of the coordinator is embarrassingly simple:

// Execute actions in the queue until it's empty. Actions add *more*
// actions (continuations) to the queue by awaiting this coordinator.
public void Start()
{
    while (actions.Count > 0)
    {
        actions.Dequeue().Invoke();
    }
}

Of course, the interesting bit is the code which supports the async methods and await expressions. We know we need to provide a GetAwaiter() method, but what should that return? Well, we're just going to use the awaiter to add a continuation to the coordinator's queue. It's got no other state than that - so we might as well return the coordinator itself, and put the other infrastructure methods directly in the coordinator.

Again, this is slightly ugly, as the extra methods don't really make sense on the coordinator - we wouldn't want to call them directly from client code, for example. However, they're fairly irrelevant - we could always create a nested type which just had a reference to its "parent" coordinator if we wanted to. For simplicity, I haven't bothered with this - I've just implemented GetAwaiter() trivially:

// Used by await expressions to get an awaiter
public Coordinator GetAwaiter()
{
return this;
}

So, that leaves just three members still to implement: IsCompleted, OnCompleted and GetResult. We always want the IsCompleted property to return false, as otherwise the coroutine will just continue executing immediately without returning to cede control; the await expression would be pointless. OnCompleted just needs to add the continuation to the end of the queue - we don't need to attach it to a task, or anything like that. Finally, GetResult is a no-op - we have no results, no exceptions, and basically nothing to do. You might want to add a bit of logging here, if you were so inclined, but there's no real need.

So, here are the final three members of Coordinator:

// Force await to yield control
public bool IsCompleted { get { return false; } }

public void OnCompleted(Action continuation)
{
    // Put the continuation at the end of the queue, ready to
    // execute when the other coroutines have had a go.
    actions.Enqueue(continuation);
}

public void GetResult()
{
    // Our await expressions are void, and we never need to throw
    // an exception, so this is a no-op.
}

And that's it! Fewer than 50 lines of code required, and nothing complicated at all. The interesting behaviour is all due to the way the C# compiler uses the coordinator when awaiting it.

We need AsyncVoidMethodBuilder as before, as we have some async void methods - but that doesn't need to do anything significant. That's basically all the code required to implement these basic round-robin coroutines.

Conclusion

Our first foray into the weird and wonderful world of coroutines was relatively tame. The basic idea of a coordinator keeping track of the state of all the different coroutines in one sense or another will keep coming back to us, but with different ways of controlling the execution flow.

Next time we'll see some coroutines which can pass data to each other.

Eduasync part 12: Observing all exceptions

skeet — Wed, 22 Jun 2011 06:04:20 GMT

(This post covers projects 16 and 17 in the source code.)

Last time we looked at unwrapping an AggregateException when we await a result. While there are potentially other interesting things we could look at with respect to exceptions (particularly around cancellation) I'm just going to touch on one extra twist that the async CTP implements before I move on to some weird ways of using async.

TPL and unobserved exceptions

The Task Parallel Library (TPL) on which the async support is based has some interesting behaviour around exceptions. Just as it’s entirely possible for more than one thing to go wrong with a particular task, it's also quite easy to miss some errors, if you're not careful.

Here's a simple example of an async method in C# 5 where we create two tasks, both of which will throw exceptions:

private static async Task<int> CauseTwoFailures()
{
    Task<int> firstTask = Task<int>.Factory.StartNew(() => {
        throw new InvalidOperationException();
    });
    Task<int> secondTask = Task<int>.Factory.StartNew(() => {
        throw new InvalidOperationException();
    });

    int firstValue = await firstTask;
    int secondValue = await secondTask;

    return firstValue + secondValue;
}

Now the timing of the two tasks is actually irrelevant here. The first task will always throw an exception, which means we're never going to await the second task. That means there's never any code which asks for the second task's result, or adds a continuation to it. It's alone and unloved in a cruel world, with no-one to observe the exception it throws.

If we call this method from the Eduasync code we've got at the moment, and wait for long enough (I've got a call to GC.WaitForPendingFinalizers in the same code) the program will abort, with this error:

Unhandled Exception: System.AggregateException: A Task's exception(s) were not observed either by Waiting on the Task or accessing its Exception property. As a result, the unobserved exception was rethrown by the finalizer thread. ---> System.InvalidOperationException: Operation is not valid due to the current state of the object.

Ouch. The TPL takes a hard line on unobserved exceptions. They indicate failures (presumably) which you'll never find out about until you start caring about the result of a task. Basically there are various ways of "observing" a task's failure, whether by performing some act which causes it to be thrown (usually as part of an AggregateException) or just asking for the exception for a task which is known to be faulted. An unobserved exception will throw an InvalidOperationException in its finalizer, usually causing the process to exit.

That works well in "normal" TPL code, where you're explicitly managing tasks - but it's not so handy in async, where perfectly reasonable looking code which starts a few tasks and then awaits them one at a time (possibly doing some processing in between) might hide an unobserved exception.

Observing all exceptions

Fortunately TPL provides a way of us to get out of the normal task behaviour. There's an event TaskScheduler.UnobservedTaskException which is fired by the finalizer before it goes bang. The handlers of the event are allowed to observe the exception using UnobservedTaskExceptionEventArgs.SetObserved and can also check whether it's already been observed.

So all we have to do is add a handler for the event and our program doesn't crash any more:

TaskScheduler.UnobservedTaskException += (sender, e) =>
{
    Console.WriteLine("Saving the day! This exception would have been unobserved: {0}",
                      e.Exception);
    e.SetObserved();
};

In Eduasync this is currently only performed explicitly, in project 17. In the async CTP something like this is performed as part of the type initializer for AsyncTaskMethodBuilder<T>, which you can unfortunately tell because that type initializer crashes when running under medium trust. (That issue will be fixed before the final release.)

Global changes

This approach has a very significant effect: it changes the global behaviour of the system. If you have a system which uses the TPL and you want the existing .NET 4 behaviour of the process terminating when you have unobserved exceptions, you basically can't use async at all - and if you use any code which does, you'll see the more permissive behaviour.

You could potentially add your own event handler which aborted the application forcibly, but that's not terribly nice either. You should quite possibly add a handler to at least log these exceptions, so you can find out what's been going wrong that you haven't noticed.

Of course, this only affects unobserved exceptions - anything you're already observing will not be affected. Still, it's a pretty big change. I wouldn't be surprised if this aspect of the behaviour of async in C# 5 changed before release; it feels to me like it isn't quite right yet. Admittedly I'm not sure how I would suggest changing it, but effectively reversing the existing behaviour goes against Microsoft's past behaviour when it comes to backwards compatibility. Watch this space.

Conclusion

It's worth pondering this whole issue yourself (and the one from last time), and making your feelings known to the team. I think it's symptomatic of a wider problem in software engineering: we're not really very good at handling errors. Java's approach of checked exceptions didn't turn out too well in my view, but the "anything goes" approach of C# has problems too... and introducing alternative models like the one in TPL makes things even more complicated. I don't have any smart answers here - just that it's something I'd like wiser people than myself to think about further.

Next, we're going to move a bit further away from the "normal" ways of using async, into the realm of coroutines. This series is going to get increasingly obscure and silly, all in the name of really getting a feeling for the underlying execution model of async, before it possibly returns to more sensible topics such as task composition.

Eduasync part 11: More sophisticated (but lossy) exception handling

skeet — Wed, 22 Jun 2011 05:25:46 GMT

(This post covers projects 13-15 in the source code.)

Long-time readers of this blog may not learn much from this post - it's mostly going over what I've covered before. Still, it's new to Eduasync.

Why isn't my exception being caught properly?

Exceptions are inherently problematic in C# 5. There are two conflicting aspects:

The point of the async feature in C# 5 is that you can write code which mostly looks like its synchronous code. We expect to be able to catch specific exception types as normal.
Asynchronous code may potentially have multiple exceptions "at the same time". The language simply isn't designed to deal with that in the synchronous case.

Now if the language had been designed for asynchrony to start with, perhaps exception flow would have been designed differently - but we are where we are, and we all expect exceptions to work in a certain way.

Let's make all of this concrete with a sample:

private static void Main(string[] args)
{
    Task<int> task = FetchOrDefaultAsync();
    Console.WriteLine("Result: {0}", task.Result);
}

private static async Task<int> FetchOrDefaultAsync()
{
    // Nothing special about IOException here
    try
    {
        Task<int> fetcher = Task<int>.Factory.StartNew(() => { throw new IOException(); });
        return await fetcher;
    }
    catch (IOException e)
    {
        Console.WriteLine("Caught IOException: {0}", e);
        return 5;
    }
    catch (Exception e)
    {
        Console.WriteLine("Caught arbitrary exception: {0}", e);
        return 10;
    }
}

Here we have a task which will throw an IOException, and some code which awaits that task - and has a catch block for IOException.

So, what would you expect this to print? With the code we've got in Eduasync so far, we get this:

Caught arbitrary exception: System.AggregateException: One or more errors occurred. ---> System.IO.IOException: I/O error occurred.
...
Result: 10

If you run the same code against the async CTP, you get this:

Caught IOException: System.IO.IOException: I/O error occurred.
...
Result: 5

Hmm... we're not behaving as per the CTP, and we're not behaving as we'd really expect the normal synchronous code to behave.

The first thing to work out is which boundary we should be fixing. In this case, the problem is between the async method and the task we're awaiting, so the code we need to fix is TaskAwaiter<T>.

Handling AggregateException in TaskAwaiter<T>

Before we can fix it, we need to work out what's going on. The stack trace I hid before actually show this reasonably clearly, with this section:

at System.Threading.Tasks.Task.ThrowIfExceptional(Boolean includeTaskCanceled Exceptions)
at System.Threading.Tasks.Task`1.get_Result()
at Eduasync.TaskAwaiter`1.GetResult() ...\TaskAwaiter.cs:line 40
at Eduasync.Program.<FetchOrDefaultAsync>d__2.MoveNext() ...\Program.cs:line 37

So AggregateException is being thrown by Task<T>.Result, which we're calling from TaskAwaiter<T>.GetResult(). The documentation for Task<T>.Result isn't actually terribly revealing here, but the fact that Task<T>.Exception is of type AggregateException is fairly revealing.

Basically, the Task Parallel Library is built with the idea of multiple exceptions in mind - whereas our async method isn't.

Now the team in Microsoft could have decided that really you should catch AggregateException and iterate over all the exceptions contained inside the exception, handling each of them separately. However, in most cases that isn't really practical - because in most cases there will only be one exception (if any) and all that looping is relatively painful. They decided to simply extract the first exception from the AggregateException within a task, and throw that instead.

We can do that ourselves in TaskAwaiter<T>, like this:

try
{
    return task.Result;
}
catch (AggregateException aggregate)
{
    if (aggregate.InnerExceptions.Count > 0)
    {
        // Loses the proper stack trace. Oops. For workarounds, see
        // See http://bradwilson.typepad.com/blog/2008/04/small-decisions.html
        throw aggregate.InnerExceptions[0];
    }
    else
    {
        // Nothing better to do, really...
        throw;
    }
}

As you can tell from the comment, we end up losing the stack trace using this code. I don't know exactly how the stack trace is preserved in the real Async CTP, but it is. I suspect this is done in a relatively obscure way at the moment - it's possible that for .NET 5, there'll be a cleaner way that all code can take advantage of.

This code is also pretty ugly, catching the exception only to rethrow it. We can check whether or not the task has faulted using Task<T>.Status and extract the AggregateException using Task<T>.Exception instead of forcing it to be thrown and catching it. We'll see an example of that in a minute.

With our new code in place, we can catch the IOException in our async code very easily.

What if I want all the exceptions?

In certain circumstances it really makes sense to collect multiple exceptions. This is particularly true when you're waiting for multiple tasks to complete, e.g. with TaskEx.WhenAll in the Async CTP. This caused me a certain amount of concern for a while, but when Mads came to visit in late 2010 and we talked it over, we realized we could use the compositional nature of Task<T> and the convenience of TaskCompletionSource to implement an extension method preserving all the exceptions.

As we've seen, when a task is awaited, its AggregateException is unwrapped, and the first exception rethrown. So if we create a new task which adds an extra layer of wrapping and make our code await that instead, only the extra layer will be unwrapped by the task awaiter, leaving the original AggregateException. To come up with a new task which "looks like" an existing task, we can simply create a TaskCompletionSource, add a continuation to the original task, and return the completion source's task as the wrapper. When the continuation fires we'll set the appropriate result on the completion source - cancellation, an exception, or the successful result.

You may expect that we'd have to create a new AggregateException ourselves - but TaskCompletionSource.SetException will already do this for us. This makes it looks like the code below isn't performing any wrapping at all, but remember that Task<T>.Exception is already an AggregateException, and calling TaskCompletionSource.SetException will wrap it in another AggregateException. Here's the extension method in question:

public static Task<T> WithAllExceptions<T>(this Task<T> task)
{
    TaskCompletionSource<T> tcs = new TaskCompletionSource<T>();

    task.ContinueWith(ignored =>
    {
        switch (task.Status)
        {
            case TaskStatus.Canceled:
                tcs.SetCanceled();
                break;
            case TaskStatus.RanToCompletion:
                tcs.SetResult(task.Result);
                break;
            case TaskStatus.Faulted:
                // SetException will automatically wrap the original AggregateException
                // in another one. The new wrapper will be removed in TaskAwaiter, leaving
                // the original intact.
                tcs.SetException(task.Exception);
                break;
            default:
                tcs.SetException(new InvalidOperationException("Continuation called illegally."));
                break;
        }
    });

    return tcs.Task;
}

Here you can see the cleaner way of reacting to a task's status - we don't just try to fetch the result and catch any exceptions; we handle each status individually.

I don't know offhand what task scheduler is used for this continuation - it may be that we'd really want to specify the current task scheduler for a production-ready version of this code. However, the core idea is sound.

It's easy to use this extension method within an async method, as shown here:

private static async Task<int> AwaitMultipleFailures()
{
    try
    {
        await CauseMultipleFailures().WithAllExceptions();
    }
    catch (AggregateException e)
    {
        Console.WriteLine("Caught arbitrary exception: {0}", e);
        return e.InnerExceptions.Count;
    }
    // Nothing went wrong, remarkably!
    return 0;
}

private static Task<int> CauseMultipleFailures()
{
    // Simplest way of inducing multiple exceptions
    Exception[] exceptions = { new IOException(), new ArgumentException() };
    TaskCompletionSource<int> tcs = new TaskCompletionSource<int>();
    tcs.SetException(exceptions);
    return tcs.Task;
}

Note that this will work perfectly well with the Async CTP and should be fine with the full release as well. I wouldn't be entirely surprised to find something similar provided by the framework itself by release time, too.

Conclusion

It's worth being aware of the impedance mismatch between the TPL and async methods in C# 5, as well as how this mismatch is handled. I dislike the idea of data loss, but I can see why it's being handled in this way. It's very much in line with the approach of trying to make asynchronous methods look like synchronous ones as far as possible.

We'll probably look at the compositional nature of tasks again later in the series, but this was one simple example of how transparent it can be - a simple extension method can change the behaviour to avoid the risk of losing exception information when you're expecting that multiple things can go wrong.

It's worth remembering that this behaviour is very specific to Task and Task<T>, and the awaiter types associated with them. If you're awaiting other types of expressions, they may behave differently with respect to exceptions.

Before we leave the topic of exceptions, there's one other aspect we need to look at - what happens when an exception isn't observed...

LINQ To Objects and the performance of nested "Where" calls

skeet — Thu, 16 Jun 2011 18:19:12 GMT

This post came out of this Stack Overflow question, which essentially boils down to which is better out of these two options:

var oneBigPredicate = collection.Where(x => Condition1(x)
                                         && Condition2(x)
                                         && Condition3(x));

var multiplePredicates = collection.Where(x => Condition1(x))
                                   .Where(x => Condition2(x))
                                   .Where(x => Condition3(x))

The first case is logically a single "wrapper" sequence around the original collection, with a filter which checks all three conditions (but applying short-circuiting logic, of course) before the wrapper will yield an item from the original sequence.

The second case is logically a set of concentric wrapper sequences, each applying a filter which checks a single condition. Asking the "outer" wrapper for the next item involves that one asking the "middle" wrapper for the next item, which asks the "inner" wrapper for the next item, which asks the original collection for the next item... the item is then passed "outwards" through the wrappers, with the filters being applied as we go, of course.

Now the two will achieve the same result, and I should say up-front that in most realistic cases, it won't make a significant difference which you use. But realistic cases aren't nearly as interesting to investigate as pathological cases, so I decided to benchmark a few different options for the second case. In particular, I wanted to find out how long it took to iterate over a query in the cases where the condition was either "always true" or "always false" - and vary the depth of nesting. Note that I'm not actually testing the first kind of query shown above... I suspect it wouldn't be terribly interesting, at least compared with the results of the second query.

The simplest way of creating a "collection" of a large size is to use Enumerable.Repeat(), and the simplest way of iterating over the whole sequence is to just call Count() on it... so that's what I do, timing how long the Count() call takes. (I don't actually print out the results of Count(), but with an "always false" predicate I'll get 0, and with an "always true" predicate I'll get the size of the input collection.)

Here's the sample code:

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Test
{
    static void Main()
    {
        int size = 10000000;
        Console.WriteLine("Always false");
        RunTests(size, x => false);

        Console.WriteLine("Always true");
        RunTests(size, x => true);

    }

    static void RunTests(int size, Func<string, bool> predicate)
    {
        for (int i = 1; i <= 10; i++)
        {
            RunTest(i, size, predicate);
        }
    }

    static void RunTest(int depth, int size, Func<string, bool> predicate)
    {
        IEnumerable<string> input = Enumerable.Repeat("value", size);

        for (int i = 0; i < depth; i++)
        {
            input = input.Where(predicate);
        }

        Stopwatch sw = Stopwatch.StartNew();
        input.Count();
        sw.Stop();
        Console.WriteLine("Depth: {0} Size: {1} Time: {2}ms",
                          depth, size, sw.ElapsedMilliseconds);
    }
}

You may notice there's no JIT warm-up here - but I've tried that, and it doesn't alter the results much. Likewise I've also tried with a larger size of collection, and the trend is the same - and the trend is the interesting bit.

Time to guess the results...

Before I include the results, I'll explain what I thought would happen. I had the mental model I described before, with multiple sequences feeding each other.

When the condition is always false, I'd expected the call to MoveNext() from Count() to get all the way to the innermost filtering sequence, which would then iterate over all of the input collection, applying the filter on each item and never yielding a result. That innermost MoveNext() call returns false, and that propagates right back to Count(). All the (significant) time is spent in the innermost loop, testing and rejecting items. That shouldn't depend on the depth of the nesting we've got, right? I'd expect it to be linear in terms of the size of the collection, but constant in terms of nesting. We'll see.

When the condition is always true, we're in a much worse situation. We need to propagate every item from the collection through all the filters, out to Count(), checking the condition and accepting the item on each check. Each MoveNext() call has to go all the way to the innermost filter, then the result has to propagate out again. That sounds like it should be roughly linear in the depth of the nesting, as well as still being linear in the size of the collection - assuming a very simplistic execution model, of course.

Before you look at the results, check that you understand my logic, and see if you can think why it might not be the case.

The actual results

Here's what I've actually observed, with all times in milliseconds. The size of the collection is constant - we're only varying the depth

Depth	Time for "always false"	Time for "always true"
1	182	305
2	219	376
3	246	452
4	305	548
5	350	650
6	488	709
7	480	795
8	526	880
9	583	996
10	882	1849

There are a few things to note here:

The "always true" time is going up broadly linearly, as we'd expected
The "always false" time is also going going up broadly linearly, even though we'd expected it to be roughly constant
The "always false" time is still significantly better than the "always true" time, which is somewhat reassuring
The performance at a depth of 10 is significantly worse than at a depth of 9 in both cases

Okay, so that's bizarre. What can possibly be making the time taken by the "inner" filtering sequence go up with the depth of the nesting? It shouldn't know about the rest of the calls to Where - that's not its job. Time to investigate...

Reimplementing Where

As you may have seen before, Where isn't very hard to implement - at least it's not hard to implement if you're not trying to be clever. In order to mess around with things to check that my mental model was correct, I decided to run exactly the same tests again, but against the Edulinq implementation. This time, the results are very different:

Depth	Time for "always false"	Time for "always true"
1	232	502
2	235	950
3	256	1946
4	229	2571
5	227	3103
6	226	3535
7	226	3901
8	232	4365
9	229	4838
10	226	5219

Well look at that... suddenly our "always false" query has the expected characteristics. The "always true" query is basically linear except for the jump in time taken between a depth of 2 and a depth of 3. This may well be the same sort of discontinuity present in the earlier results, but at a different depth. (I'll do more research on that another time, I think.)

So if the naive implementation actually works better in some cases, what's going wrong in the "always false" case in the real LINQ to Objects? We can work this out by taking a stack trace from a predicate. Here's a sample query which will throw an exception:

var query = Enumerable.Repeat("value", 1)
                      .Where(x => { throw new Exception("Bang!"); })
                      .Where(x => true)
                      .Where(x => true)
                      .Where(x => true)
                      .Where(x => true)
                      .Where(x => true)
                      .Where(x => true)
                      .Where(x => true);

When you try to count that query (or do anything else which will iterate over it) you get a stack trace like this:

Unhandled Exception: System.Exception: Bang!
   at Test.<Main>b__0(String x)
   at System.Linq.Enumerable.<>c__DisplayClassf`1.<CombinePredicates>b__e(TSource x)
   at System.Linq.Enumerable.<>c__DisplayClassf`1.<CombinePredicates>b__e(TSource x)
   at System.Linq.Enumerable.<>c__DisplayClassf`1.<CombinePredicates>b__e(TSource x)
   at System.Linq.Enumerable.<>c__DisplayClassf`1.<CombinePredicates>b__e(TSource x)
   at System.Linq.Enumerable.<>c__DisplayClassf`1.<CombinePredicates>b__e(TSource x)
   at System.Linq.Enumerable.<>c__DisplayClassf`1.<CombinePredicates>b__e(TSource x)
   at System.Linq.Enumerable.<>c__DisplayClassf`1.<CombinePredicates>b__e(TSource x)
   at System.Linq.Enumerable.WhereEnumerableIterator`1.MoveNext()
   at System.Linq.Enumerable.Count[TSource](IEnumerable`1 source)
   at Test.Main()

Ooh, look at that stack - we've got 8 Where clauses, and 7 levels of DisplayClassf`1 - which looks like a generated class, perhaps for a lambda expression.

Between this and a helpful email from Eric Lippert, we can basically work out what's going on. LINQ to Objects knows that it can combine two Where clauses by just constructing a compound filter. Just for kicks, let's do the same thing - almost certainly more simplistically than LINQ to Objects - but in a way that will give the right idea:

// We could have an interface for this, of course.
public class FilteredEnumerable<T> : IEnumerable<T>
{
    private readonly IEnumerable<T> source;
    private readonly Func<T, bool> predicate;

    internal FilteredEnumerable(IEnumerable<T> source,
                                Func<T, bool> predicate)
    {
        this.source = source;
        this.predicate = predicate;
    }

    public IEnumerator<T> GetEnumerator()
    {
        foreach (T item in source)
        {
            if (predicate(item))
            {
                yield return item;
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public FilteredEnumerable<T> Where(Func<T, bool> extraPredicate)
    {
        return new FilteredEnumerable<T>(source,
                                         x => this.predicate(x) && extraPredicate(x));
    }
}

public static class Extensions
{
    public static IEnumerable<T> Where<T>(this IEnumerable<T> source,
                                          Func<T, bool> predicate)
    {
        var filtered = source as FilteredEnumerable<T>;
        return filtered == null ? new FilteredEnumerable<T>(source, predicate)
                                : filtered.Where(predicate);
    }
}

Let's run the same tests as before, and see how we do...

Depth	Time for "always false"	Time for "always true"
1	240	504
2	275	605
3	332	706
4	430	797
5	525	892
6	558	980
7	638	1085
8	715	1208
9	802	1343
10	1312	2768

Oh look - it feels like the real LINQ to Objects implementation. A bit slower, certainly, but that's okay. The way it trends is the same. In particular, it's slower than the naive implementation for the "always false" filter, but faster for the "always true" filter.

Could things be improved?

The problem here is the creation of nested delegates. We end up with a large stack (which appears to be causing a bigger problem when it reaches a depth of 10) when really we want to just build another delegate.

The thought occurs that we could potentially use expression trees to do this. Not in a signature-compatible way with LINQ to Objects, but we should be able to combine (a => a == 3) and (b => b != 10) into (x => x == 3 && x != 10) effectively. Then when we're asked to iterate, we just need to compile the expression tree to a delegate, and filter using that single, efficient delegate.

There are three problems with this:

It goes against the normal approach of LINQ to Objects, using delegates instead of expression trees. Heck, with expression trees throughout we could do all kinds of interesting optimizations.
Creating and compiling the expression tree may be more expensive than the iteration - we don't really know. It depends on how large the collection is, etc.
It's somewhat complicated to implement, because we need to rewrite the constituent expressions; note how "a" and "b" both become "x" in the example above. This is the main reason I haven't actually bothered trying this in order to benchmark it :)

There are various other options to do with building a more efficient way of evaluating the predicates. One pretty simple (but repetitive) solution is to have one class per number of predicates, with a field per predicate - FilteredEnumerable1, FilteredEnumerable2 etc. When you get bored (e.g. FilteredEnumberable9) you construct any further ones by combining predicates as per the LINQ to Objects approach. For example, here's an implementation of FilteredEnumerable3:

public class FilteredEnumerable3<T> : IFilteredEnumerable<T>
{
    private readonly IEnumerable<T> source;
    private readonly Func<T, bool> predicate0;
    private readonly Func<T, bool> predicate1;
    private readonly Func<T, bool> predicate2;

    internal FilteredEnumerable3(IEnumerable<T> source,
                                 Func<T, bool> predicate0,
                                 Func<T, bool> predicate1,
                                 Func<T, bool> predicate2)
    {
        this.source = source;
        this.predicate0 = predicate0;
        this.predicate1 = predicate1;
        this.predicate2 = predicate2;
    }

    public IEnumerator<T> GetEnumerator()
    {
        foreach (T item in source)
        {
            if (predicate0(item) &&
                predicate1(item) &&
                predicate2(item))
            {
                yield return item;
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return GetEnumerator();
    }

    public IFilteredEnumerable<T> Where(Func<T, bool> extraPredicate)
    {
        return new FilteredEnumerable4<T>(source,
            predicate0,
            predicate1,
            predicate2,
            extraPredicate);
    }
}

In this case, I'm rather pleased with the results:

Depth	Time for "always false"	Time for "always true"
1	237	504
2	231	551
3	231	599
4	225	625
5	228	703
6	224	787
7	222	876
8	225	966
9	232	1069
10	219	1191

Now that's more like it. Other than a few cells, we're actually outperforming LINQ to Objects - and still compatible with it. The only problem is that the cells where it's slower are the common ones - the top few in the right hand column. And this was just going up to FilteredEnumerable4<T>.

I honestly don't know why my FilteredEnumerable1<T> is slower than whatever's in LINQ to Objects. But it's nice to see the rest going quickly... I suspect there are some downsides as well, and basically I trust the team to make the right decisions for normal cases.

And there's more...

You may be surprised to hear I've kept things simple here - as Eric mentioned to me, it's not just Where and Select that can be transformed in this way. Select works as well - you can combine projections together pretty easily. So imagine that we've effectively got this transformation:

// Normal LINQ query
var query = list.Where(x => Condition1(x))
                .Where(x => Condition2(x))
                .Select(x => Projection1(x))
                .Select(y => Projection2(y));

// After optimization
var query = list.WhereSelect(x => Condition1(x) && Condition2(x),
                             x => Projection2(Projection1(x));

Of course at that point, my FilteredEnumerableX<T> approach becomes even more unwieldy as you have two axes - the number of predicates and the number of projections.

Conclusion

As is so often the case with performance, there's more to Where than there first appears. When I started benchmarking this I had no idea what I was getting myself into. The great thing is that very few people would ever need to know this. It's all hidden by the abstraction.

Still, isn't this sort of thing fun?