BT

Facilitating the Spread of Knowledge and Innovation in Professional Software Development

Write for InfoQ

Topics

Choose your language

InfoQ Homepage Articles A Bottom-Up View of Kotlin Coroutines

A Bottom-Up View of Kotlin Coroutines

This item in japanese

Key Takeaways

  • The JVM does not provide native support for coroutines
  • Kotlin implements coroutines in the compiler via transformation to a state machine
  • Kotlin uses a single keyword for the implementation, the rest is done in libraries
  • Kotlin uses Continuation Passing Style (CPS) to implement coroutines
  • Coroutines use Dispatchers, so are used slightly differently in JavaFX, Android, Swing, etc

Coroutines are a fascinating subject, although hardly a new one. As has been documented elsewhere coroutines have been rediscovered many times over the years, typically when there is a need for some form of lightweight threading and/or a solution to ‘callback hell’.

Recently, on the JVM, coroutines have become popular as an alternative to Reactive Programming. Frameworks such as RxJava or Project Reactor provide a way for clients to incrementally process incoming information, with extensive support for throttling and parallelism. But you must restructure your code around functional operations on reactive streams, and in many cases the costs outweigh the benefits.

This is why there was demand within (for example) the Android community for a simpler alternative. The Kotlin language introduced coroutines as an experimental feature to meet this need, and after some refinement they became an official feature in version 1.3 of the language. Adoption of Kotlin coroutines has grown beyond UI development to server side frameworks (such as the support added in Spring 5) and even functional frameworks like Arrow (via Arrow Fx).

The Challenge of Understanding Coroutines

Unfortunately, understanding coroutines is not an easy task. Despite the existence of numerous coroutine talks by Kotlin experts, many of which are enlightening and informative a single view of what a coroutine is (or how it should be used) is not easy to converge on. You might say that coroutines are the monads of parallel programming :slightly_smiling_face:.

Part of the problem is the underlying implementation. In Kotlin coroutines the compiler implements only the suspend keyword, with everything else being handled by the coroutine library. Kotlin coroutines are extremely powerful and flexible as a result, but also somewhat amorphous. This presents a barrier to learning for novices, who learn best with solid guidelines and rigid principles. This article presents a view of coroutines from the bottom up, in the hope that this will provide such a foundation.

Our Sample Application (Server Side)

Our application will build on the canonical problem of safely and efficiently making multiple calls to a RESTful service. We will play a textual version of Where's Waldo - in which users follow a chain of names till they reach ‘Waldo’.

Here is the complete RESTful service, written using Http4k. Http4k is the Kotlin version of the functional server architecture described in the well known paper written by Marius Eriksen. Implementations exist in many other languages, including Scala (Http4s) and Java 8 or above (Http4j).

There is a single endpoint, which implements a chain of names via a Map. Given a name we return either the matching value and a 200 status code or a 404 and an error message.

fun main() {
   val names = mapOf(
       "Jane" to "Dave",
       "Dave" to "Mary",
       "Mary" to "Pete",
       "Pete" to "Lucy",
       "Lucy" to "Waldo"
   )

   val lookupName = { request: Request ->
       val name = request.path("name")
       val headers = listOf("Content-Type" to "text/plain")
       val result = names[name]
       if (result != null) {
           Response(OK)
               .headers(headers)
               .body(result)
       } else {
           Response(NOT_FOUND)
               .headers(headers)
               .body("No match for $name")
       }
   }

   routes(
       "/wheresWaldo" bind routes(
           "/{name:.*}" bind Method.GET to lookupName
       )
   ).asServer(Netty(8080))
       .start()
}

Essentially we want our client to make the following chain of requests:


Our Sample Application (Client Side)

Our client application will be based around the JavaFX library for creating desktop user interfaces. But to simplify our task and avoid unnecessary details we will use TornadoFX, which puts a Kotlin DSL on top of JavaFX.

Here’s the complete definition of the client view:

class HelloWorldView: View("Coroutines Client UI") {
   private val finder: HttpWaldoFinder by inject()
   private val inputText = SimpleStringProperty("Jane")
   private val resultText = SimpleStringProperty("")

   override val root = form {
       fieldset("Lets Find Waldo") {
           field("First Name:") {
               textfield().bind(inputText)
               button("Search") {
                   action {
                       println("Running event handler".addThreadId())
                       searchForWaldo()
                   }
               }
           }
           field("Result:") {
               label(resultText)
           }
       }
   }
   private fun searchForWaldo() {
       GlobalScope.launch(Dispatchers.Main) {
           println("Doing Coroutines".addThreadId())
           val input = inputText.value
           val output = finder.wheresWaldo(input)
           resultText.value = output
       }
   }
}

We will also use the following helper function as an extension of the String type:

fun String.addThreadId() = "$this on thread ${Thread.currentThread().id}"

This is what the UI looks like when run:

When the user clicks the button we launch a new coroutine and access the RESTful Endpoint via a service object of type ‘HttpWaldoFinder’.

Kotlin coroutines exist within a ‘CoroutineScope’, which in turn is associated with some Dispatcher that represents the underlying concurrency model. The concurrency model is typically a thread pool but varies.

Which Dispatchers are available depends on the environment within which your Kotlin code is running. The Main Dispatcher represents the event handling thread of a UI library and hence (on the JVM) is only available in Android, JavaFX and Swing. In the beginning Kotlin Native did not support multithreading at all for Coroutines, but this is changing. On the server-side you can introduce coroutines yourself, but increasingly they are available by default, such as in Spring 5.

We have to have a Coroutine, a ‘CoroutineScope’ and a ‘Dispatcher’ in place before we can start to call suspending methods. If this is the initial call (as in the code above) we can kick-start the process via ‘coroutine builder’ functions such as ‘launch’ and ‘async’.

Calling either a coroutine builder function, or a scoping function like ‘withContext’ always creates a new ‘CoroutineScope’. Within this scope tasks are represented by a hierarchy of ‘Job’ instances.

These have some interesting properties, namely:

  • Jobs wait for all coroutines within their block to complete before completing themselves.
  • Cancelling a Job leads to the cancellation of all of its children.
  • Failure or cancellation of a child is propagated up to the parent.  

This design is intended to avoid common issues in concurrent programming, such as killing a parent job without ending its children.

The Service to Access the REST Endpoint

Here is the full code for our HttpWaldoFinder service:

class HttpWaldoFinder : Controller(), WaldoFinder {
   override suspend fun wheresWaldo(starterName: String): String {
       val firstName = fetchNewName(starterName)
       println("Found $firstName name".addThreadId())

       val secondName = fetchNewName(firstName)
       println("Found $secondName name".addThreadId())

       val thirdName = fetchNewName(secondName)
       println("Found $thirdName name".addThreadId())

       val fourthName = fetchNewName(thirdName)
       println("Found $fourthName name".addThreadId())

       return fetchNewName(fourthName)
   }
   private suspend fun fetchNewName(inputName: String): String {
       val url = URI("http://localhost:8080/wheresWaldo/$inputName")
       val client = HttpClient.newBuilder().build()
       val handler = HttpResponse.BodyHandlers.ofString()
       val request = HttpRequest.newBuilder().uri(url).build()

       return withContext<String>(Dispatchers.IO) {
           println("Sending HTTP Request for $inputName".addThreadId())
           client
               .send(request, handler)
               .body()
       }
   }

}

The ‘fetchNewName’ function takes a known name and queries the endpoint for the associated one. This is done using the ‘HttpClient’ type, which comes as standard from Java 11 onwards. The actual HTTP GET is being run in a new child coroutine which uses the IO Dispatcher. This represents a pool of threads optimised for long running activities such as network calls.

The ‘wheresWaldo’ function follows the chain of names five times in order to (hopefully) find Waldo. Because we will be disassembling the generated bytecode we have made the implementation as simple as possible. What interests us is that each call to ‘fetchNewName’ will result in the current coroutine being suspended whilst the child coroutine runs. In this particular case the parent is running on the Main Dispatcher whilst the child is run on the IO Dispatcher. So whilst the child is executing the HTTP request the UI event-handling thread is freed up to handle other user interactions with the view. This is illustrated below.

IntelliJ will show us when we are making a suspending call, and therefore transferring control between coroutines. Note that if we were not switching Dispatcher then making the call would not necessarily result in a new coroutine being created. When one suspend function call another it is possible to continue in the same coroutine, indeed this is the behavior we would want if we were staying on the same thread.

When we execute the client this is the output written to the console:

We can see that, in this particular case, the Main Dispatcher / UI Event Handler was running on thread 17, whilst the IO Dispatcher was running on the pool that includes threads 24 and 26.

Beginning Our Investigation

Using the bytecode disassembly tool that comes with IntelliJ we can peek at what is actually going on. Note that we could also have used the standard ‘javap’ tool that is provided with the JDK.

We can see that the methods of ‘HttpWaldoFinder’ have had their signature changed, so that they accept a continuation object as an extra parameter, and return some general object.

public final class HttpWaldoFinder extends Controller implements WaldoFinder {

  public Object wheresWaldo(String a, Continuation b)
  final synthetic Object fetchNewName(String a, Continuation b)
}

Now let’s dive into the code that has been added into these methods, and explain both what the ‘Continuation’ is and what is now being returned.

The Continuation Passing Style (CPS)

As documented in the Kotlin standardisation process (aka. KEEP) proposal for coroutines, the implementation of coroutines is based around the Continuation Passing Style. A continuation object is used to store the state required by a function during the period when it is suspended.

Essentially every local variable of your suspending function becomes a field of the continuation. Fields also need to be created for any parameters and for the current object  (if the function is a method). So a suspending method with four parameters and five local variables will have a continuation with at least ten fields.

In the case of our ‘wheresWaldo’ method in ‘HttpWaldoFinder’ there is a single parameter and four local variables, so we expect the continuation implementation type to have six fields. If we disassemble the bytecode emitted by the Kotlin compiler as Java source we can see this is indeed the case:

$continuation = new ContinuationImpl($completion) {
  Object result;
  int label;
  Object L$0;
  Object L$1;
  Object L$2;
  Object L$3;
  Object L$4;
  Object L$5;

  @Nullable
  public final Object invokeSuspend(@NotNull Object $result) {
     this.result = $result;
     this.label |= Integer.MIN_VALUE;
     return HttpWaldoFinder.this.wheresWaldo((String)null, this);
  }
};

Since all the fields are of type Object its not immediately obvious how they are intended to be used. But as we venture further we will see that:

  • ‘L$0’ holds the reference to the ‘HttpWaldoFinder’ instance. This is always present.
  • ‘L$1’ holds the value of the ‘starterName’ parameter. This is always present.
  • ‘L$2’ to ‘L$5’ hold the values of the local variables. These will be incrementally filled in as the code executes. ‘L$2’ will hold the value of ‘firstName’ and so on.

We also have additional fields for the final result and the intriguing integer called ‘label’.

To Suspend Or Not To Suspend - That Is The Question

As we examine the generated code, we need to bear in mind that it must cope with two use cases. Every time a suspending function calls into another it may either suspend the current coroutine (so that another may run on the same thread) or continue the execution of the current coroutine.

Consider a suspend function which reads a value from a data store. Most likely it will suspend as I/O takes place, but it may also cache the result. Subsequent calls could return the cached value synchronously, without any suspension. The code generated by the Kotlin compiler must allow for both paths.

The Kotlin compiler adjusts the return type from each suspending function so that it may return either the actual result or the special value COROUTINE_SUSPENDED. In the latter case the current coroutine is suspended. This is why the return type from a suspending function is changed from the result type to ‘Object’.

In our sample application ‘wheresWaldo’ is going to repeatedly call ‘fetchNewName’. In theory each of these calls may or may not suspend the current coroutine. Since we wrote ‘fetchNewName’ we know that suspension will always occur. However to make sense of the generated code we must remember that it needs to be able to handle all the possibilities.

The Big Switch Statement and Labels

If we look further through the disassembled code we will find a switch statement buried within multiple nested labels. This is the implementation of a state machine to control the different suspension points within our wheresWaldo() method. Here is the high level structure:

// listing one: the generated switch statement and labels
String firstName;
String secondName;
String thirdName;
String fourthName;
Object var11;
Object var10000;
label48: {
  label47: {
     label46: {
        Object $result = $continuation.result;
        var11 = IntrinsicsKt.getCOROUTINE_SUSPENDED();
        switch($continuation.label) {
        case 0:
            // code omitted
        case 1:
            // code omitted
        case 2:
            // code omitted
        case 3:
            // code omitted
        case 4:
            // code omitted
        case 5:
            // code omitted
        default:
           throw new IllegalStateException(
                "call to 'resume' before 'invoke' with coroutine");
        } // end of switch
        // code omitted
    } // end of label 46
    // code omitted
  } // end of label 47
  // code omitted
} // end of label 48
// code omitted

We can now see the purpose of the ‘label’ field in the continuation. As we complete the different stages of ‘wheresWaldo’ we will alter the value in ‘label’. The nested label blocks contain the blocks of our code between suspension points in the original Kotlin code. This ‘label’ value allows this code to be reentered, jump to the point at which it last suspended (the appropriate case statement) to extract some data from the continuation and then break to the correct labeled block.

However, the entire block could be executed synchronously if all of our suspension points do not actually suspend. In the generated code we frequently find this fragment:

// listing two - deciding if the current coroutine should suspend
if (var10000 == var11) {
  return var11;
}

As we saw above ‘var11’ has been set to the CONTINUATION_SUSPENDED value, whilst ‘var10000’ holds the return value from a call to another suspending function. So, when suspension occurs the code returns (to be reentered later) and if no suspension occurs the code continues to the next part of the function by breaking to an appropriate labeled block.

Once again, please remember that the generated code cannot assume that all the calls will suspend, or that all the calls will continue with the current coroutine. It must be able to cope with any possible combination.

Tracing the Execution

When we begin our execution the value of ‘label’ in the continuation is set to zero. Here is the corresponding branch of the switch statement:

// listing three - the first branch of the switch
case 0:
  ResultKt.throwOnFailure($result);
  $continuation.L$0 = this;
  $continuation.L$1 = starterName;
  $continuation.label = 1;
  var10000 = this.fetchNewName(starterName, $continuation);
  if (var10000 == var11) {
     return var11;
  }
  break;

We store the instance and the parameter into the continuation object, and then pass the continuation object into ‘fetchNewName’. As discussed the version of ‘fetchNewName’ generated by the compiler will return either the actual result or the COROUTINE_SUSPENDED value.

If the coroutine is being suspended then we return from the function, and when we resume jump to the ‘case 1’ branch. If we are continuing with the current coroutine then we break out of the switch to one of the labelled blocks, to the code below:

// listing four - calling ‘fetchNewName’ for the second time
firstName = (String)var10000;
secondName = UtilsKt.addThreadId("Found " + firstName + " name");
boolean var13 = false;
System.out.println(secondName);
$continuation.L$0 = this;
$continuation.L$1 = starterName;
$continuation.L$2 = firstName;
$continuation.label = 2;
var10000 = this.fetchNewName(firstName, $continuation);
if (var10000 == var11) {
  return var11;
}

Because we know that ‘var10000’ contains our desired return value we can cast it to the correct type and store it in the local variable ‘firstName’. The generated code then uses the variable ‘secondName’ to store the result of concatenating the thread id, which is then printed.

We update the fields within the continuation, adding the value we have retrieved from the server. Note that the value of ‘label’ is now 2. We then invoke ‘fetchNewName’ for the third time.

The Third Call to ‘fetchNewName’ - Without Suspension

Once again we have to make a choice, based on the value returned from ‘fetchNewName’ if the value returned was COROUTINE_SUSPENDED then we return from the current function. When we are next called we will follow the ‘case 2’ branch of the switch.

If we are continuing with the current coroutine then the block below is executed. As you can see it is identical to the one above, except that we now have more data to store in the continuation.

// listing four - calling ‘fetchNewName’ for the third time
secondName = (String)var10000;
thirdName = UtilsKt.addThreadId("Found " + secondName + " name");
boolean var14 = false;
System.out.println(thirdName);
$continuation.L$0 = this;
$continuation.L$1 = starterName;
$continuation.L$2 = firstName;
$continuation.L$3 = secondName;
$continuation.label = 3;
var10000 = this.fetchNewName(secondName, (Continuation)$continuation);
if (var10000 == var11) {
  return var11;
}

This pattern repeats for all the remaining calls (assuming that COROUTINE_SUSPENDED is never returned) until we reach the end.

The Third Call to ‘fetchNewName’ - With Suspension

Alternatively, if the coroutine had been suspended, then this is the case block we would have run:

// listing five - the third branch of the switch
case 2:
  firstName = (String)$continuation.L$2;
  starterName = (String)$continuation.L$1;
  this = (HttpWaldoFinder)$continuation.L$0;
  ResultKt.throwOnFailure($result);
  var10000 = $result;
  break label46;

We extract the values from the continuation into local variables of the function. A labelled break is then used to jump execution to listing four above. So ultimately we will end up in the same place.

Summarising the Execution

We can now revisit our listing of the structure of the code and give a high level description of what is going on in each section:

// listing six - the generated switch statement and labels in depth
String firstName;
String secondName;
String thirdName;
String fourthName;
Object var11;
Object var10000;
label48: {
  label47: {
     label46: {
        Object $result = $continuation.result;
        var11 = IntrinsicsKt.getCOROUTINE_SUSPENDED();
        switch($continuation.label) {
       case 0:
            // set label to 1 and make the first call to ‘fetchNewName’
            // if suspending return, otherwise break from the switch
        case 1:
            // extract the parameter from the continuation
            // break from the switch
        case 2:
            // extract the parameter and first result from the continuation
            // break to outside ‘label46’
        case 3:
            // extract the parameter, first and second results from the
            //   continuation
            // break to outside ‘label47’
        case 4:
            // extract the parameter, first, second and third results from
            //   the continuation
            // break to outside ‘label48’
        case 5:
            // extract the parameter, first, second, third and fourth
            //   results from the continuation
            // return the final result
        default:
           throw new IllegalStateException(
                "call to 'resume' before 'invoke' with coroutine");
        } // end of switch
        // store the parameter and first result in the continuation
        // set the label to 2 and make the second call to ‘fetchNewName’
        // if suspending return, otherwise proceed
    } // end of label 46
        // store the parameter, first and second results in the
        //   continuation
        // set the label to 3 and make the third call to ‘fetchNewName’
        // if suspending return, otherwise proceed
  } // end of label 47
        // store the parameter, first, second and third results in the   
        //   continuation
        // set the label to 4 and make the fourth call to ‘fetchNewName’
        // if suspending return, otherwise proceed
} // end of label 48
// store the parameter, first, second, third and fourth results in the continuation
// set the label to 5 and make the fifth call to ‘fetchNewName’
// return either the final result or COROUTINE_SUSPENDED

Conclusions

This is not an easy codebase to understand. We are examining Java code disassembled from bytecode produced by a code generator within the Kotlin compiler. The output of this code generator was designed for efficiency and minimalism rather than intelligibility.

However we can draw some useful conclusions:

  1. There is no magic. When developers first learn about coroutines it is easy to assume that there is some special ‘magic’ being used to tie everything together. As we can see the generated code uses only the basic building blocks of procedural programming, such as conditionals and labelled breaks.
  2. The implementation is continuation based. As documented in the original KEEP proposal the way functions are suspended and resumed is by caching the state of the function within an object. So for each suspend function the compiler will create a continuation type with N fields, where N is the number of parameters plus the number of fields plus three. These final three hold the current object, the final result and an index.
  3. Execution always follows a standard pattern. If we are resuming from a suspension then we use the ‘label’ field of the continuation to jump to the appropriate branch of a switch statement. In this branch we retrieve the data that has been found so far from the continuation object, and then use a labelled break to jump to the code we would have executed directly had a suspension not occurred.

About the Authors

Garth Gilmour is the Head of Learning at Instil. He gave up full time development back in 1999 to first teach C++ to C coders, then Java to C++ coders, then C# to Java coders and now teaches everything to everybody, but prefers to work in Kotlin. If he counted deliveries it would have gone past 1000 some time ago. He is the author of over 20 courses, speaks frequently at meetups, presents at conferences both National and International and co-organises the Belfast BASH series of developer events and the recently formed Kotlin Belfast User Group. When not at the whiteboard he coaches Krav Maga and lifts heavy weights.

Eamonn Boyle has over 15 years working as a developer, architect and team lead. For about the last 4 years he’s been working as a full time trainer and coach, authoring and delivering courses on a range of topics to a broad range of delegates. These include paradigms and technologies from core language skills, Frameworks to tools and processes. He has also spoken and given workshops at a number of conferences, events and meetups including Goto and KotlinConf.

Rate this Article

Adoption
Style

BT