Awaitable/awaiter pattern and logical micro-threading in C#

TL;DR

We’ll focus on the extensibility points of the C# compiler to customize the behavior of async methods and task-like types. As result, we will be able to write linear, concise, and composable code with the possibility to have control over task scheduling. 🤓

I recommend reading the original blog post: https://nikiforovall.github.io/csharp/compcsi/dotnet/2020/10/20/awaitable-pattern.html

C# 💜 patterns

Numerous C# features are based on duck-typing and patterns inferred by the compiler. Basically, it means that a developer doesn’t need to implement interfaces or inherit classes explicitly to achieve some pluggable behavior. Instead, we could follow some well-known conventions inferred by the compiler to plug or glue some functionality together. Duck-typing is great when strongly-typed approach impedes too many limitations or you want to keep your code clean and tidy. So if you’ve got a pattern right, than, the compiler will do its magic and generate some code for you. Let’s see examples of such patterns in C#.

Foreach

Implement GetEnumerator method to make you custom type work with foreach.

LINQ Queries

Implement SelectMany, Select, Where, GroupBy, OrderBy, ThenBy, Join. C# compiler creates a series of method calls. As long as these methods are found, you are good.

Deconstructors

Implement the Deconstruct method with a bunch out parameters. The result of deconstruction could be consumed as ValueTuple or as separately initialized variables.

Dynamic

The C# compiler invokes a whole reflection machinery which by default can invoke methods, properties, and fields. As soon as the object implements IDynamicMetaObjectProvider the object gets runtime control on what is invoked.

Async/Await

The only thing required is a GetAwaiter method which returns an object having an IsComplete and GetResult() method and implementing the INotifyCompletion interface.

🚀 Let’s see how we can use this in something that I call logical micro-threading.

Problem: Largest series product

Occasionally, I use coding platforms to practice my craft. I really like the idea of doing Katas to hone coding skills, because you truly know something when you’ve implemented it and get hands-on experience. Katas is part of the thing. 🐱‍👤

A code kata is an exercise in programming which helps programmers hone their skills through practice and repetition.

Let’s solve this one: exercism.io/tracks/csharp/exercises/largest-series-product.

Given a string of digits, calculate the largest product for a contiguous substring of digits of length n.

The problem itself is really straightforward and we could solve it by iterating over the input array and calculating the local maximum every time the window has a length of a given value (span).

Here is my first take on it: largest-series-product/solution.

I hate to read code like this 🤮. It takes you quite some time and effort to really figure out what is going on. With great confidence, we can describe this code as write-only.

Write-only code code is source code so arcane, complex, or ill-structured that it cannot be reliably modified or even comprehended by anyone with the possible exception of the author.

Let’s formulate how we could tackle the complexity of relatively simple problems in an utterly hyperbolical manner.

My goal is to share with you the technique. I deliberately chose a simple problem so we could try to understand the micro-threading approach without delving into details.

Micro-threading

C# 5 language made a huge step forward by introducing async/await. Async/await helps to compose tasks and gives the user an ability to use well-known constructs like try/catch, using etc. A regular method has just one entry point and one exit point. But async methods and iterators are different. In the case of async method, a method caller get the (e.g. Task-like type or Task) result immediately and then "await" the actual result of the method via the resulting task-like type.

Async machinery

Methods marked by async are undergoing subtle transformations performed by the compiler. To make everything work together, the compiler makes use of:

1. Generated state machine that acts like a stack frame for an asynchronous method and contains all the logic from the original async method
2. AsyncTaskMethodBuilder<T> that keeps the completed task (very similar to TaskCompletionSource<T> type) and manages the state transition of the state machine.
3. TaskAwaiter<T> that wraps a task and schedules continuations of it if needed.
4. MoveNextRunner that calls IAsyncStateMachine.MoveNextmethod in the correct execution context.

The fascinating part is you use extensibility points the C# compiler provides for customizing the behavior of async methods:

1. Provide your own default async method builder in the System.Runtime.CompilerServices namespace.
2. Use custom task awaiters.
3. Define your own task-like types. Starting from C# 7.2.

Later, we will see how the last two options could be used in more detail.

Let’s get back to kata problem, shall we?

If we take a look from the different angle we can spot different states in which the sliding window can be: “reduced”, “expanded”, and “shifted”.

So, the idea is to move the window from left to right and calculate local product every time the window is “expanded” or “shifted”.

Solution of the largest series product with awaitable/awaiter patten

My goal is to come up with the solution write highly composable and linear code and at the same time have control of how building blocks are executed and scheduled.

Full source code: /exercism-playground/csharp/largest-series-product

Core

In order to use async/await for task-like types we need to introduce a bunch of extensibility points.

A strategy represents a discrete and composable algorithm.

We want to make it awaitable and you do it like this await myAwesomeStrategy

As mentioned before, C# compiler could do it’s magic if we implement awaitable/awaiter patter.

This works like this:

1. Driver do the .Tick()
2. AsyncTicker runs a fresh strategy/task. (run())
3. Code executes normally until first await
4. GetAwaiter unwraps task-like type
5. AsyncMethodBuilder initializes state machine
6. AsyncTicker runs continuation (continue())
7. stateMachine.MoveNext() is invoked
8. If StrategyTask is completed, the result is returned and control flow is resumed

I suggest you to spin up the debugger and investigate on your own 😉.

Let’s say we want to define a top-level strategy that is based on sliding windows giving us a valid span for every type we await a sub-strategy to slide:

A valid slide could look something like this:

And the building blocks:

And now, when we have the solution assembled, we can write a “Driver” code to trigger task machinery. Control flow is returned to the driver every time we await something. This means, that we can change the way strategies are scheduled without modification of the actual algorithm. We may say that scheduling is moved out to a separate layer and adheres Open-Closed Principle (OCP) in this regard.

Having this layer we can enhance the solution with:

• Interception logic
• Fine-grained control over strategy scheduling
• Cancellation logic without the necessity to throw an Exception

If we run we can see the output based on simple interceptor logic:

Let’s parallelize our solution by adding new strategy that will make use of existing building blocks:

We could take another route and parallelize based on “Driver”

The beautiful thing is that we don’t need to change the actual implementation of the algorithm to have control over execution and scheduling. Which you may or may not find useful, but I find the approach interesting.

Conclusion

This is a tremendous over-engineering for such a simple problem. But I hope you’ve got this idea and how we could use custom task-like types to build our own async machinery.

Reference

https://www.theurlist.com/awaitable-pattern

Originally published at https://nikiforovall.github.io/csharp/compcsi/dotnet/2020/10/20/awaitable-pattern.html on October 20, 2020.