Building structured, composable, and high-performance concurrency on top of Reagents?

[tkf]

Here's my motivation behind Reagents.

In Julia, we have various demands for concurrent programming.

High-performance. Julia users always crave for performance. For shared-memory parallelism (threading), it is likely we will have more and more nonblocking algorithms, now that Julia 1.7 supports atomics. On the other hand, as the flat combining technique indicate, synchronization also play a key role in improving the performance.

Composability. Composability is the magic sauce of Julia ecosystem we have a big success in the sequential programming world. However, concurrent programs are notoriously hard to compose (e.g., locking order, atomicity guarantee, ...). The successful composability stories in Julia have depended on the flexible interfaces (e.g., the Array interface). Can we bring it in the concurrent programming?

Structured concurrency. Concurrent programs have to deal with multiple things at once. Since this is hard, it is helpful to keep the concurrent program structured. For example, a useful property in the sequential programming is that the side-effects "end" by the time a function returns. Such a seemingly innocent property does not hold in many concurrent programming models. Maintaining this idea is one of the main ingredients of structured concurrency which let us write clean concurrent programs.

However, long story short, we need to be able to cancel all possibly blocking operations reliably to support structured concurrency. One way to implement this is to implement something like Go's select which can be used to execute ("select") exactly one of the given set of concurrent operations. This can be used for cancellation since each concurrent operation can be listed in a select with additional event listening to the cancellation signal (the Done channel idiom). Thus, we can implement structured concurrency by automating this idiom. However, this strategy is not compatible with the demand for composability; i.e., we will not be able to cancel user-defined concurrent algorithms, if select only is defined for a fixed set of primitives like channels. Concurrent ML provides a more extensible approach by providing a way to compose concurrent operations separately from how they are synchronized (= Go's select). Indeed, Racket implements kill-safe abstraction (user-definable and cancellable abstraction) on top of Concurrent ML's protocol. However, since Concurrent ML is (old and so) designed without parallelism in mind, it is not clear how to incorporate this with high-performance demand that Julia has. This is why reagent is attractive. It is inspired by Concurrent ML but is specifically designed to enable nonblocking algorithms.

This points to a rough idea in how to build a concurrency framework for Julia:

• Create reagent for Julia (a proof-of-concept done in this repository). (→ Composability)
  • The most challenging part might be to make sure that the abstraction can be optimized away in Julia (→ High-performance)
  • Some formulation may be required to be tweaked to fit well in Julia.
• Extend it to support some Concurrent ML features as required.
• Implement Racket's kill-safe abstraction on top of these. (→ Structured concurrency)

Some open questions

• How to support performance specialization and clearly define the method dispatch pipeline?
  • e.g., Reagents.Ref is not enough for linear probing concurrent dictionary as it needs to access array elements atomically. But can the concurrent dictionary still expose the reagent API?
• How do reagents relate to the generic nonblocking dual data structures? Can we integrate some ideas?
• How does "kill safety" of nonblocking algorithms itself help? Can some of the "manger threads" be eliminated?

Resources

• Turon, Aaron. 2012. “Reagents: Expressing and Composing Fine-Grained Concurrency.” In Proceedings of the 33rd ACM SIGPLAN Conference on Programming Language Design and Implementation, 157–168. PLDI ’12. New York, NY, USA: Association for Computing Machinery. https://doi.org/10.1145/2254064.2254084.

• Michael Sperber - Concurrent ML - The One That Got Away - Code Mesh 2017 - YouTube

• LDN Functionals #8 KC Sivaramakrishnan: OCaml multicore and programming with Reagents - YouTube

• Reagent implementation for OCaml: https://github.com/ocaml-multicore/reagents

• Flatt, Matthew, and Robert Bruce Findler. 2004. “Kill-Safe Synchronization Abstractions.” ACM SIGPLAN Notices 39 (6): 47–58. https://doi.org/10.1145/996893.996849.

• 1.1.15 Custodians (The Racket Reference)

• Izraelevitz, Joseph, and Michael L. Scott. 2017. “Generality and Speed in Nonblocking Dual Containers.” ACM Transactions on Parallel Computing 3 (4): 22:1–22:37. https://doi.org/10.1145/3040220.

• Michael Scott — Dual data structures - YouTube (Hydra 2019)

[c42f]

Reagents.Ref is not enough for linear probing concurrent dictionary as it needs to access array elements atomically. But can the concurrent dictionary still expose the reagent API?

I found the following which claims that kCAS is hard to use for searches across data structures https://mc.uwaterloo.ca/cs798/lec13.v1.pdf. So maybe no? (The page at https://mc.uwaterloo.ca/cs798/ is a goldmine of interesting concurrent datastructures.)

However, the following thesis seems interesting and related. It shows how to implement a lock free AVL tree with kCAS. https://uwspace.uwaterloo.ca/bitstream/handle/10012/15813/Sigouin_William.pdf?sequence=5&isAllowed=y I wonder whether similar techniques could be used for atomically updating the linear probing chain of a hash map?

Is it true that any lock free data structure implemented in terms of kCAS should be expressible with reagents?

[tkf]

I think the main point of the slide is rather that kCAS does not make the safety argument of nonblocking data structures easy. This is true even when you need only one CAS at the linearization point. But it's still possible to provide reagent API for nonblocking algorithm of the search-then-CAS form (e.g., MS queue https://tkf.github.io/Reagents.jl/dev/tutorials/msqueue/).

After played with reagents a bit more after writing the OP, I think it's possible to expose reagent API for a linear probing concurrent dictionary (that I implemented in ConcurrentCollections.jl). (An obvious simple "solution" is to fill an array with Reagents.Ref.) I think the question is more like if we can eliminate the overhead.

The thesis PDF you mentioned sounds interesting but I can't download the PDF...

Is it true that any lock free data structure implemented in terms of kCAS should be expressible with reagents?

Yeah, kCAS can be expressed as CAS(ref1, old1, new1) ⨟ CAS(ref2, old2, new2) ⨟ ... ⨟ CAS(refk, oldk, newk). So it should be straightforward to translate the algorithm.

[tkf]

There's now https://github.com/tkf/Julio.jl, a structured concurrency library for Julia, implemented on top of Reagents.jl. I needed to extend the protocol and fill the gaps of the original reagent framework but it's now powerful enough for implementing a structured concurrency library. I think this shows that the scenario proposed in the OP is a promising direction.

An interesting (though obvious in hindsight) thing I noticed while playing with Reagents.jl is that, since a synchronization requires dynamically combining continuations ("thunks") from various tasks, a naive implementation (i.e., current status) invokes quite a lot of dynamic dispatches. But I'm optimistic about the issue since it probably can be solved by something like opaque closure which is an interesting direction.