Asynchrony in C# 5.0 part Four: It's not magic

Asynchrony in C# 5.0 part Four: It's not magic

Rate This
  • Comments 31

Today I want to talk about asynchrony that does not involve any multithreading whatsoever.

People keep on asking me "but how is it possible to have asynchrony without multithreading?" A strange question to ask because you probably already know the answer. Let me turn the question around: how is it possible to have multitasking without multiple CPUs? You can't do two things "at the same time" if there's only one thing doing the work! But you already know the answer to that: multitasking on a single core simply means that the operating system stops one task, saves its continuation somewhere, switches to another task, runs it for a while, saves its continuation, and eventually switches back to continue the first task. Concurrency is an illusion in a single-core system; it is not the case that two things are really happening at the same time. How is it possible for one waiter to serve two tables "at the same time"? It isn't: the tables take turns being served. A skillful waiter makes each guest feel like their needs are met immediately by scheduling the tasks so that no one has to wait.

Asynchrony without multithreading is the same idea. You do a task for a while, and when it yields control, you do another task for a while on that thread. You hope that no one ever has to wait unacceptably long to be served.

Remember a while back I briefly sketched how early versions of Windows implemented multiple processes? Back in the day there was only one thread of control; each process ran for a while and then yielded control back to the operating system. The operating system would then loop around the various processes, giving each one a chance to run. If one of them decided to hog the processor, then the others became non-responsive. It was an entirely cooperative venture.

So let's talk about multi-threading for a bit. Remember a while back, in 2003, I talked a bit about the apartment threading model? The idea here is that writing thread-safe code is expensive and difficult; if you don't have to take on that expense, then don't. If we can guarantee that only "the UI thread" will call a particular control then that control does not have to be safe for use on multiple threads. Most UI components are apartment threaded, and therefore the UI thread acts like Windows 3: everyone has to cooperate, otherwise the UI stops updating.

A surprising number of people have magical beliefs about how exactly applications respond to user inputs in Windows. I assure you that it is not magic. The way that interactive user interfaces are built in Windows is quite straightforward. When something happens, say, a mouse click on a button, the operating system makes a note of it. At some point, a process asks the operating system "did anything interesting happen recently?" and the operating system says "why yes, someone clicked this thing."  The process then does whatever action is appropriate for that. What happens is up to the process; it can choose to ignore the click, handle it in its own special way, or tell the operating system "go ahead and do whatever the default is for that kind of event."  All this is typically driven by some of the simplest code you'll ever see:

while(GetMessage(&msg, NULL, 0, 0) > 0)
{
  TranslateMessage(&msg);
  DispatchMessage(&msg);
}

That's it. Somewhere in the heart of every process that has a UI thread is a loop that looks remarkably like this one. One call gets the next message. That message might be at too low a level for you; for example, it might say that a key with a particular keyboard code number was pressed. You might want that translated into "the numlock key was pressed". TranslateMessage does that. There might be some more specific procedure that deals with this message. DispatchMessage passes the message along to the appropriate procedure.

I want to emphasize that this is not magic. It's a while loop. It runs like any other while loop in C that you've ever seen. The loop repeatedly calls three methods, each of which reads or writes a buffer and takes some action before returning. If one of those methods takes a long time to return (typically DispatchMessage is the long-running one of course since it is the one actually doing the work associated with the message) then guess what? The UI doesn't fetch, translate or dispatch notifications from the operating system until such a time as it does return. (Or, unless some other method on the call chain is pumping the message queue, as Raymond points out in the linked article. We'll return to this point below.)

Let's take an even simpler version of our document archiving code from last time:

void FrobAll()
{
    for(int i = 0; i < 100; ++i)
        Frob(i);
}

Suppose you're running this code as the result of a button click, and a "someone is trying to resize the window" message arrives in the operating system during the first call to Frob. What happens? Nothing, that's what. The message stays in the queue until everything returns control back to that message loop. The message loop isn't running; how could it be? It's just a while loop, and the thread that contains that code is busy Frobbing. The window does not resize until all 100 Frobs are done.

Now suppose you have

async void FrobAll()
{
    for(int i = 0; i < 100; ++i)
    {
        await FrobAsync(i); // somehow get a started task for doing a Frob(i) operation on this thread
    }
}

What happens now?

Someone clicks a button. The message for the click is queued up. The message loop dispatches the message and ultimately calls FrobAll.

FrobAll creates a new task with an action.

The task code sends a message to its own thread saying "hey, when you have a minute, call me". It then returns control to FrobAll.

FrobAll creates an awaiter for the task and signs up a continuation for the task.

Control then returns back to the message loop. The message loop sees that there is a message waiting for it: please call me back. So the message loop dispatches the message, and the task starts up the action. It does the first call to Frob.

Now, suppose another message, say, a resize event, occurs at this point. What happens? Nothing. The message loop isn't running. We're busy Frobbing. The message goes in the queue, unprocessed.

The first Frob completes and control returns to the task. It marks itself as completed and sends another message to the message queue: "when you have a minute, please call my continuation". (*)

The task call is done. Control returns to the message loop. It sees that there is a pending window resize message. That is then dispatched.

You see how async makes the UI more responsive without having any threads? Now you only have to wait for one Frob to finish, not for all of them to finish, before the UI responds. 

That might still not be good enough, of course. It might be the case that every Frob takes too long. To solve that problem, you could make each call to Frob itself spawn short asynchronous tasks, so that there would be more opportunities for the message loop to run. Or, you really could start the task up on a new thread. (The tricky bit then becomes posting the message to run the continuation of the task to the right message loop on the right thread; that's an advanced topic that I won't cover today.)

Anyway, the message loop dispatches the resize event and then checks its queue again, and sees that it has been asked to call the continuation of the first task. It does so; control branches into the middle of FrobAll and we pick up going around the loop again. The second time through, again we create a new task... and the cycle continues.

The thing I want to emphasize here is that we stayed on one thread the whole time. All we're doing here is breaking up the work into little pieces and sticking the work onto a queue; each piece of work sticks the next piece of work onto the queue. We rely on the fact that there's a message loop somewhere taking work off that queue and performing it.

UPDATE: A number of people have asked me "so does this mean that the Task Asynchrony Pattern only works on UI threads that have message loops?" No. The Task Parallel Library was explicitly designed to solve problems involving concurrency; task asynchrony extends that work. There are mechanisms that allow asynchrony to work in multithreaded environments without message loops that drive user interfaces, like ASP.NET. The intention of this article was to describe how asynchrony works on a UI thread without multithreading, not to say that asynchrony only works on a UI thread without multithreading. I'll talk at a later date about server scenarios where other kinds of "orchestration" code works out which tasks run when.

Extra bonus topic: Old hands at VB know that in order to get UI responsiveness you can use this trick:

Sub FrobAll()
  For i = 0 to 99
    Call Frob(i)
    DoEvents
  Next
End Sub

Does that do the same thing as the C# 5 async program above? Did VB6 actually support continuation passing style?

No; this is a much simpler trick. DoEvents does not transfer control back to the original message loop with some sort of "resume here" message like the task awaiting does. Rather, it starts up a second message loop (which, remember, is just a perfectly normal while loop), clears out the backlog of pending messages, and then returns control back to FrobAll. Do you see why this is potentially dangerous?

What if we are in FrobAll as a result of a button click? And what if while frobbing, the user pressed the button again? DoEvents runs another message loop, which clears out the message queue, and now we are running FrobAll within FrobAll; it has become reentrant. And of course, it can happen again, and now we're running a third instance of FrobAll...

Of course, the same is true of task based asynchrony! If you start asynchronously frobbing due to a button click, and there is a second button click while more frobbing work is pending, then you get a second set of tasks created. To prevent this it is probably a good idea to make FrobAll return a Task, and then do something like:

async void Button_OnClick(whatever)
{
    button.Disable();
    await FrobAll();
    button.Enable();
}

so that the button cannot be clicked again while the asynchronous work is still pending.

Next time: Asynchrony is awesome but not a panacea: a real life story about how things can go terribly wrong.

------------

(*) Or, it invokes the continuation right then and there. Whether the continuation is invoked aggressively or is itself simply posted back as more work for the thread to do is user-configurable, but that is an advanced topic that I might not get to.

  • In fact, windows will spin it's own message loop in certain situations, such as while the user is moving or resizing a window (in DefWindowProc()) or while DialogBox() or ShowMessage() is running. This means you can't do any magic in your message loop, if you care about dropped messages, such as implementing a UI thread dispatcher!

    The best way I've found to handle implementing a message loop dispatcher is a WM_APP_DISPATCH message posted to the main window (or a not shown message-only window), callback in LPARAM, param in WPARAM. Of course, now I need a global HWND to post these to, which kinda sucks, and I need to worry about lifetimes of windows vs. messages, or I need a extra window. A possible alternative is PostThreadMessage() combined with SetWindowsHookEx(WH_GETMESSAGE), which seems slightly cleaner, but I'm not confident enough that I'm not going to miss some messages in some screwball situation. What do the Forms / WPF Dispatchers do?

  • That's why the name Task is kind of unfortunate, perhaps Future (like it was called in the CTP) or Promise would have been more explicit (Task seems to indicate it can only be CPU bound).

  • Eric, could you further elaborate on the pros&cons of doing UI asynchrony either as continuations or as DoEvents? Your button-disabling example isn't solved any differently with DoEvents.

  • On the general subject of the new syntax enhancements, I'm a little irritated by the obvious equivalence of awaiting in an async method and yielding in an iterator. As I see it, the following two code snippets should be equivalent:

    //first

    async Foo AsyncMethod() {

    //... do some (potentially async) stuff

    someValue = await taskExpression;

    //...

    return whatever;

    }

    //second

    Task<Foo> AsyncByHand() {

    TaskCompletionSource<Foo> tcs = new TaskCompletionSource<Foo>();

    IEnumerator<Task> enumerator = IteratorHelper(tcs); //does not execute any "real" code

    Action<Task> continuation = null;

    continuation = (unused) => { //needs Task parameter to serve as continuation in Task.ContinueWith

    if (enumerator.MoveNext())

       enumerator.Current.ContinueWith(continuation); //enumerator.Current is the yielded task

    }

    continuation(null); //execute first part of asynchronous operation

    return tcs.Task;

    }

    IEnumerator<Task> IteratorHelper(TaskCompletionSource<Foo> tcs) {

    //do exactly the same "usual" operations

    var task = taskExpression;

    yield return task;

    someValue = task.Result;

    //...

    tcs.SetResult(whatever);

    yield break;

    }

    In the second snippet, yielding a task works just like awaiting - it saves the current state and signs up everything left to do as a continuation. Granted, we now need three lines instead of one if we are interested in the result of the awaited task, but this is a rather small tax to pay. The boilerplate code in AsyncByHand could easily be factored out into a generic helper method taking a Func<TaskCompletionSource<T>, IEnumerator<Task>> (although argument passing to the iterator may require overloads to this helper); throwing in hypothetical anonymous iterators would get rid of the additional method.

    Sure, you could argue that awaiting is more general than what I just hacked together because of the Awaiter approach, but this is marginal because one could always replace Task by a different ("smaller") interface.

    So what's left of all the new sugar? Not much you couldn't accomplish using the existing sugar (iterators) in very few more lines. Don't get me wrong, I truly appreciate the effort of taking C# to new areas, but I'm wondering how this feature achieved the proverbly 100 points necessary to be implemented. Asynchronous programming (and especially I/O) is quite important, but I think the largest impediment to its more widespread use is not syntax, but rather awareness among programmers.

  • @Apollonius

    Good luck with task compositions using yields...

  • @Apollonious

    await taskExpression returns inmediately. The continuation is saved and called when taskExpression finishes. Thats the whole point of the async approach.

    yield taskExpression does not return until said method has finished. The continuation saved is the iterator block state for further iterations. You are effectively blocking any other execution from happening until taskExpression finished so I'm not sure how you're proposing to manage asynchronousity with yields...

    I might be missing something...

  • Yes, you are missing something. await taskExpression will evaluate taskExpression just as yield return taskExpression does; the whole point of both is that taskExpression evaluates to a Task, i.e. a promise for a value, not the value itself. Note how yielding the task will make AsyncByHand sign up the next iterator round (i.e. everything left to do) as a continuation of the task. This behaviour is identical to that of await!

    Regarding Focus' comment: You apparently don't understand that task compositions do not really have much to do with the language feature. Task composition is just the process of creating a new task from old tasks, which is already possible today (see System.Threading.Tasks.TaskFactory.ContinueWhenAll/ContinueWhenAny). There is no reason why this wouldn't work with my solution.

  • @Apollonius

    (might be a repost, mi posts don't seem to show up)

    1. Is your example asynchronous or is it multithreaded?

    2. I see your point, but you are just restating what Eric has proved in the whole past series. Its not so much about programming asynchronous code (which we can since C# 1.0), its about making it easy.

    With all due respect, your code reads like a nightmare compared to the async / await pattern that looks almost exactly the same as good old synchronous code. That, IMHO is a major step forward.

    LINQ, dynamics, named parameters, etc. are all features that weren't necessary in the language, you could very well do everything these features do before but it was in most cases extremely painful to do so. I guess the C# team is following the same line of thought with asynchronous programming.

  • What I provided is not an "example". It is a rough sketch of how to translate the "await" feature to an iterator. As such, it is "just async, not multithreaded", whatever you mean by that.

    To your second point: I acknowledge that there are different opinions on this one, but I think that once you take out the body of AsyncByHand - which, as I said, could be refactored into a library method - you end up with almost the same code as with await. I am simply doubting that introducing a fairly large changes - new keywords in the language, new rewriting passes in the compiler - is worth the benefits which I personally consider quite small. (I know, I keep repeating myself.)

    But note also that I'm not so much restating what Eric said but rather contradicting him in a way; the C# team apparently seeks the easiest possible syntax as the key to promoting asynchronicity, while I am actually content with a fairly easy syntax and think awareness is more important. (Apologies to Eric if I have incorrectly stated "his opinion" on this stance, and for highjacking the comment discussion on his blog)

    Honestly, this is just my opinion; it's not binding for anyone, just a counterweight to the "Huh, that's awesome" comments posted earlier.

  • I've only recently been able to keep up with all the recent articles on this matter.

    One question that popped in mind was -- what does this all mean about DEBUGGING my application?

    Suppose i am following the execution path line by line, all of a sudden will be jumping back and forth to some continuation? how is it possible to debug such a scenario? or did i get it all wrong ?

  • Is it possible to specificically start the async task in a new thread ?

    something like- awaitNewThread FrobAsync(i);

    instead of - await FrobAsync(i);

  • On a side note regarding your example of disabling the button prior to starting FrobAll, what happens if there are already multiple button click messages in the queue before the first button click is processed.    Will disabling the button cause any pending messages for that button in the queue to be discarded (in GetMessage or DispatchMessage maybe)  or will they be delivered?

  • I haven't yet read the rest of this series, so I may be jumping ahead, but there's a really important point here that Eric seems to be getting right up to without saying it outright.

    In this post he made it very clear that this is *logical concurrency* without *threads* - and, furthermore, that running threads doesn't imply that things will be literally happening at the same time anyway - as the single CPU example makes clear.

    In otherwords multithreading is a way to abstract concurrency away from physical CPUs/ Cores, just as the new Task Parallel Library is. As Eric said, before we had pre-emptive multitasking this was, conceptually, how we did it anyway (IIRC we had yield() statements that actually performed a similar job to DoEvents() - so not quite the same).

    So?

    OS scheduled threading has some serious disadvantages:

    1. You can't predict when a context is going to switch - it might happen while you're updating something.

    2. As a consequence of (1) we have to use locks and semaphores and events and other thread sync primitives to protect shared state.

    3. It can be harder than you think to identify shared state.

    4. (2) can be very tricky to get right - even harder to make efficient safely. It's easy to introduce deadlocks, get the locking granularity wrong, or not lock something you should (I use the word "lock", here, to encompas mutexes, critical sections, semaphores, etc).

    5. There is a cost associated with locking (in addition to the cost already associated with thread context switching). You pay this cost whether you needed it at the time or not - locking is a defensive technique.

    6. Communication between threads is hard and must be done with protected shared state or some ad-hoc composition of threading primitives. Framework/ library support tends to be either very low-level (if existent) or very heavyweight.

    That's just off-the-top-of-my-head!

    I'm probably preaching to the converted here - but I wanted to stress the above so we have the right mindset.

    Now.

    With the co-operative model (on a single thread) *pretty much all of this boils away*! As Eric says, it's not a panacea - but it *is* a different model of working, and most of the problems I listed are a result of the pre-emptive model. They arise precisely because we don't have control over when a context switch will occur. With the co-operative model we get that control back.

    In some ways it's as if you write your code as a sequence of critical sections. Within a CS you know that you have exclusive access to all shared state until the end of the CS. The same with an async task. No need for any addition locks. The locks and the context switch get rolled into one.

    Now I glossed over one important caveat there: This is only possible when running on one thread. That means limiting yourself to one CPU/ core. Doesn't that make this all pointless?

    Not really. For many applications that's *all* you need. Threading is often only introduced to improve response times (as Eric's original example bore out). And with platform support tasks such as reading files or waiting for network packets can be defined as async and running physically concurrently - still without introducing application threads (think back to Eric's example in the previous series on continuations).

    Furthermore, it's often more practical to keep physical concurrency at the process level. Running four, isolated, processes that use async tasks internally on a quad-core CPU will give you maximum utilisation *with no threading required*. Grid computing tends to work this way already.

    But there are still many applications that would benefit from physical concurrency in-process. Even in these cases it can be simpler to keep the physically concurrent parts seperate from the logically concurrent parts. Keep communication between threads limited in scope and through isolation interfaces such as queues or message passing facilities. I.e. what we're already doing - but we can narrow the scope and impact drastically further.

    I think all this is why we should be very excited about the TPL - as well as technologies like Grand Central Dispatch on the Mac (which goes some way towards the same goals).

    Let Moore's law "continue"...

  • The async void FrobAll seems to be awaited in Button_OnClick, if I understand it right. But in the Visual Studio 11 preview, async void methods really do return void (not Task). So you can't await them.

    I'm pretty sure it must have worked in the original CTP because I wrote a blog post that mused on taking a different approach to the problem of ensuring two button clicks don't launch two simultaneous "Frobs":

    smellegantcode.wordpress.com/.../c-5-0-asyncawait-and-gui-events

    Of course it could be fixed by changing your async void method to return Task<bool> or something.

    But would I be right if I took a strong hint from this change: that side-effecting asyncs should not be freely composed in the same way as value-returning asyncs? Is there something dangerous about doing this?

  • I see that changing "async void FrobAll()" to "async Task FrobAll()" restores the ability to await, so I guess it's not frowned upon after all.

Page 2 of 3 (31 items) 123