Taking Structured Concurrency Seriously

[c42f]

In julia 1.3 the threadsafe runtime for truly parallel tasks has arrived which will greatly increase the interest in concurrent computation in Julia's core numerical and technical computing community. For the moment, Threads.@spawn is experimental, but now is a good time to think about APIs for expressing concurrent computation in a safe and composable way with the aim to use such an API as an ecosystem gets built on top of the new functionality.

There's been a lot of recent excitement and hard work on libraries to support so-called structured concurrency, with the claim that this is fundamentally a better model for composable concurrent computation.

I'm convinced that people are onto something here and that the overall ideas are an excellent fit for the Julia language. However, there's a lot of prior art to absorb so I have started a document with the aim to do two things:

• Survey existing ideas and implementations
• Explore how these ideas fit within the Julia language and runtime.

Click here to read the WIP document

Meta note

I'm using this julep as a guinea pig to try out a go-proposals style workflow, as discussed at #33239. So let's try discussing this here (non-substantive procedural comments to go to the Juleps repo.

[tkf]

I'm copying some comments I made in https://github.com/c42f/Juleps

Discuss "black box rule" and robust cancellation separately?

I think it might be better to emphasize that structured concurrency has a few sub-concepts.

My understanding is that what njs calls "black box rule" is a sub-concept of structured concurrency and it's more fundamental than robust cancellation. So, I'd suggest to introduce "black box rule" and cancellation as different sub-concepts from the get-go. I think this is particularly important in Julia because many compute-intensive task don't need cancellation and people may not want to have runtime and conceptual overhead of robust cancellation. An alternative term may be call tree.

One counter-example to my argument that "black box rule" is more fundamental is Go's errgroup and context. errgroup is the implementation of the "black box rule" while context is the implementation of robust cancellation. errgroup is implemented on top of context and it may contradict with my argument that "black box rule" (errgroup) is more fundamental than robust cancellation (errgroup). But I think the fact that they are implemented in separate packages in Go at least backs up my argument that those are different concepts.

So, maybe it is a good idea to organize the sections like this?

• Structured Concurrency
  • Background terminology
  • The black box rule
  • Robust task cancellation
  • ...

A benefit of having different color

I suggested to add the following paragraph at the end of Syntax section c42f/Juleps#2

On the other hand, a syntax such as async/await is a useful visual marker that emphasise when the cancellation can happen (await) and what functions are cancellable (async). Note that this does not have to be implemented at language level. For example, Go's context and errgroup enforces reader to recognize where the cancellation can happen (listening to the Done channel) and what function can be cancelled (accept Context as an argument).

Also quoting another comment:

I just noticed that you touched this already in "The challenge of preemptive cancellation" but with relation to preemptive cancellation. But maybe it's useful to touch it a bit here in a different context?

Are go statements harmful?

Copying comment from c42f/Juleps#3

OK... I think this can be very controversial. But I suggest to add:

It is important to emphasize that, as absence of goto statement that can cross function boundaries is the major feature of modern languages, the absence of "go statement" (@spawn in Julia 1.3) is the major feature of the structured concurrency. This is because it is impossible for caller to know that a function follows structured concurrency without the language-level guarantee.

To emphasize that it has large impact in Julia than (say) Python, I also added:

Note that the situation in Julia is more serious compared to other languages which has functions with "two-colors" (see below) and plugable eventloop (e.g., Python) where it is possible to enforce the absence of "go statement" at the library level.

[c42f]

Are go statements harmful?

I'm convinced they are harmful. But luckily this isn't a matter of opinion if we can agree that

1. Structured concurrent programs are simpler to reason about because they are more restricted in form and have many benefits in composability.
2. There is no significant penalty for giving up the flexibility of an unstructured approach.

The first of these doesn't seem controversial to me.

Lucky for us, the second can be attacked empirically due to the efforts in Trio: @njsmith has repeatedly stated that they've found no reason to back off from their insistence that all tasks are started from a nursery. The Kotlin people seem to agree (though they do have a nod to backward compatibility with the global coroutine scope). I think the other empirical answer we can have to this is to try implementing a suite of standard concurrency patterns ourselves in Awaits.jl or equivalent prototype.

[c42f]

A benefit of having different color

syntax such as async/await is a useful visual marker that emphasise when the cancellation can happen (await) and what functions are cancellable (await)

I agree this can be seen as a benefit and I've updated the document. In a cooperatively concurrent system it also marks where task switching can happen which can otherwise be a source of timing bugs, for example JuliaWeb/HTTP.jl#382 (comment)

[tkf]

Lucky for us, the second can be attacked empirically due to the efforts in Trio

I also add that Trio convinced Python core devs to add structured concurrency in Python itself: Yury Selivanov - Asyncio in Python 3 7 and 3 8 - YouTube. (Although it says asyncio.TaskGroup (≈ nursery) is likely to be in Python 3.8, I don't think it is added yet.)

when the cancellation can happen (await) and what functions are cancellable (await)

Oops, the second await should be async. Thanks for fixing it in the Julep :)

In a cooperatively concurrent system it also marks where task switching can happen which can otherwise be a source of timing bugs

Just to be clear, we are already in Go/Kotlin group as there is no async/await. We can still take Go's context approach to pass around cancellation tokens (it's the Done channel in Go's context). This would clarify cancellable functions from the call signature (you can't call it unless you pass the cancellation token). However, we can't use this mechanism for I/O functions because existing I/O functions do not have this signature and their color is the same as synchronous functions.

I requested to add that paragraph because I thought it was important to recognize the pros and cons of having async/await syntax to assess the advantage and disadvantage that already exist in Julia. I think the main discussion point might be "Should we pass around cancellation tokens explicitly?"

[tkf]

By the way, it'd be nice to have a list of compute-intensive applications that require cancellation.

One example I found/implemented was stoppable reduce in Transducers.jl. It can be used to implement parallel findfirst.

[c42f]

The following thread about how Rust's new async/await relates to SC needs a careful read. There's many interesting points related to cancellation and zero cost abstractions.

https://trio.discourse.group/t/structured-concurrency-in-rust/73

[c42f]

We can still take Go's context approach to pass around cancellation tokens (it's the Done channel in Go's context). This would clarify cancellable functions from the call signature (you can't call it unless you pass the cancellation token). However, we can't use this mechanism for I/O functions because existing I/O functions do not have this signature and their color is the same as synchronous functions.

We could add versions of IO which use this mechanism and make deprecating the old ones a long term (Julia 2.0) goal. So I think it's worth considering, if only to understand which points in the design space we're giving up on. Actually a full implementation of SC seems to be a julia 2.0 goal in any case because we already have bare @async and it would certainly be breaking to change how that works.

The action of passing around a context could be wrapped up with macros to form the expected lexically scoped chain of custody for cancellation without much syntactic overhead. This would indeed give us colored functions (colored by calling convention), but at least the syntactic price would be no worse than python and there's no language change required.

Here's a related question: are there any systems which don't have colored functions, and which also have a compelling cancellation story?

• Modern Go has them with Contexts
• Kotlin has them with suspend functions and coroutine builders
• Python has them with async/await

[c42f]

Over on the Julep, @vchuravy notes about the Tapir PR:

Note that this is primarily about:

• Compiler representation of tasks
• Experimenting with Cilk-style semantics (e.g. may happen in parallel or what I have taken to call structured parallelism)

My thought was that the outcome of the Tapir effort could be visible to users if we find that restricting semantics in a targeted way would greatly improve optimization opportunities. For example, maybe it could enable us to transform symmetric coroutines into lightweight state machines in some cases?

@vchuravy I think it would be really valuable if you could provide a summary of how you see this effort fitting into the bigger picture.

[tkf]

We could add versions of IO which use this mechanism and make deprecating the old ones a long term (Julia 2.0) goal.

I didn't think of this. That's an interesting possibility.

we already have bare @async

Good point. I forgot about it. I still think we can pretend to have structured concurrency before 2.0 since it is very likely that people are lured to @spawn (or whatever the API we'll have) because of the potential performance benefits.

The action of passing around a context could be wrapped up with macros to form the expected lexically scoped chain of custody for cancellation without much syntactic overhead.

That's actually the strategy I used in Awaits.jl.

are there any systems which don't have colored functions, and which also have a compelling cancellation story?

The only thing somewhat related to this I know is thredo (built on top of curio which is an async I/O library that inspired trio). In EuroPython 2018 (David Beazley - Die Threads - YouTube), the author talked about designing a threading library from scratch, motivated by the two-color problem and also robust cancellation (the talk is mostly demo of thredo). thredo API does not enforce the "black box rule" but it has cancellation and also has (optional) ThreadGroup (≈ nursery). The cancellation can happen only if you use thread building blocks like Queue, Lock, etc. imported from thredo. But it seems that this is treated as limitation rather than a feature for marking cancellable functions. For example, it has a monkey-patching helper to replace stdlib sockets used in third-party libraries with the thredo implementation. It also has implication in the CPU-intensive code as it's cancellable only when it hits curio's eventloop. He is mentioning that this is actually a desirable feature and I guess we all agree randomly inserting checkpoint would be awful for performance-oriented language like Julia.

But I've never played with it and I don't know if there is a discussion on structured concurrency aspect of thredo. AFAICT this is an experimental library and I don't think it's used in the wild. I'm just mentioning it since it seems to fill the design space of "cancellation without color."

[tkf]

are there any systems which don't have colored functions, and which also have a compelling cancellation story?

Java's Thread.interrupt was mentioned as an unsuccessful story in https://trio.discourse.group/t/structured-concurrency-in-rust/73/25