Lock-free programming for the masses

Efficient concurrent programming libraries are essential for taking advantage of fine-grained parallelism on multicore hardware. In this post, I will introduce reagents, a composable, lock-free concurrency library for expressing fine-grained parallel programs on Multicore OCaml. Reagents offer a high-level DSL for experts to specify efficient concurrency libraries, but also allows the consumers of the libraries to extend them further without knowing the details of the underlying implementation.

Motivation

Designing and implementing scalable concurrency libraries is an enormous undertaking. Decades of research and industrial effort has led to state-of-the-art concurrency libraries such as java.util.concurrent (JUC) for the JVM andSystem.Collections.Concurrent (SCC) for the .NET framework. These libraries are often written by experts and have subtle invariants, which makes them hard to maintain and improve. Moreover, it is hard for the library user to safely combine multiple atomic operations. For example, while JUC and SCC provide atomic operations on stacks and queues, such atomic operations cannot be combined into larger atomic operations.

On the other hand software transactional memory (STM) offers composability, but STM based data structures are generally less efficient than their lock-free counterparts, especially when there is moderate to high levels of contention. Aaron Turonintroduced reagents, an expressive and composable library which retains the performance and scalability of lock-free programming. Reagents allow isolated atomic updates to shared state, as well as message passing communication over channels. Furthermore, reagents provide a set of combinators for sequential composition à la STM, parallel composition à laJoin calculus, and selective communication à la Concurrent ML, while being lock-free. Reagents occupy this sweet-spot between expressivity and performance, and we believe it could serve as a great default1 for writing fine-grained concurrent programs in Multicore OCaml.

http://kcsrk.info/ocaml/multicore/2016/06/11/lock-free/

Advertisements