High-performance Deterministic Concurrency Using <scp>Lingua Franca</scp>

Christian Menard, Marten Lohstroh, Soroush Bateni, Matthew Chorlian, Arthur Deng, Peter Donovan, Clément Fournier, Shaokai Lin, Felix Suchert, Tassilo Tanneberger, Hokeun Kim, Jerónimo Castrillón, Edward A. Lee

TL;DR

This paper introduces Lingua Franca (LF), a programming language that enables high-performance, deterministic concurrent systems by leveraging a reactor model. LF demonstrates that determinism doesn't sacrifice performance, outperforming popular actor frameworks like Akka and CAF on a suite of benchmarks.

What Problem Does This Paper Address?

Building concurrent systems for modern multi-core processors is crucial for performance, but it often comes at the cost of nondeterminism. Nondeterministic programs are notoriously difficult to understand, debug, and test because their behavior can vary even with the same inputs. This arises from the inherent nature of many concurrency models, such as actor frameworks, where the order of message processing isn't strictly defined. While nondeterminism can be useful in some niche applications, most programming tasks benefit from predictable, repeatable behavior. The paper addresses the challenge of achieving high performance in concurrent systems without sacrificing this essential determinism.

Methods

The core of the paper is the Lingua Franca (LF) language and its associated runtime. LF is built upon the reactor model, which provides a deterministic concurrency paradigm. Reactors are described as deterministic actors with a discrete event execution semantics and explicitly declared ports and connections. A key aspect is the use of a logical timeline to order events and ensure deterministic execution. LF programs are composed of these reactors, which can be hierarchically and bilaterally connected.

The paper highlights several key technical contributions:

  • Reactor Model for Deterministic Concurrency: LF leverages the reactor model, which inherently enforces determinism by defining a clear execution order based on event tags and dependencies.
  • Language Extension for Scalability: LF includes syntax extensions for creating multiple reactor instances and connections efficiently, allowing programs to scale to different problem sizes without recompilation.
  • Optimized C++ Runtime: A significant contribution is the development of an optimized C++ runtime for LF. This runtime features a scheduler that tracks future events, controls logical time advancement, and invokes triggered reactions. Crucially, it aims to exploit parallelism while minimizing synchronization overhead.
  • Lock-Free Data Structures: To combat contention in the shared runtime data structures (queues, etc.), the implementation utilizes lock-free data structures.
  • Coordinated Worker Threads: The runtime employs a strategy where worker threads can also act as schedulers, reducing synchronization overhead.

Datasets

The evaluation of LF's performance is conducted using the Savina benchmark suite. This suite is designed for actor languages and frameworks and includes implementations for Akka and CAF. The authors ported 22 out of the 30 Savina benchmarks to LF's C++ target. They note that some benchmarks were omitted due to fundamental differences between actor and reactor models, or because they relied on dynamic actor creation, which is not yet fully supported by LF's mutation features.

Key Insights and Ideas

  • Determinism Doesn't Mean Slow: The most significant insight is that a deterministic concurrency model, like the one provided by LF's reactors, does not inherently lead to performance degradation. In fact, it can enable more efficient implementations by avoiding the need for explicit, potentially costly, synchronization mechanisms often found in actor-based systems.
  • Explicit Synchronization is Often Unnecessary: Many actor-based benchmarks require explicit synchronization (e.g., acknowledgments) to achieve determinism. LF's reactor model, with its inherent ordering and dependency tracking, often makes these explicit synchronization steps unnecessary, leading to cleaner and faster code.
  • Logical Time is Key: The concept of logical time in the reactor model is crucial for achieving determinism, even in applications that don't require precise physical timing. This logical timeline ensures that events are processed in a consistent order, regardless of the underlying physical execution speeds.
  • Scalability Through Declarative Connections: LF's syntax for creating multiple connections and reactor instances simplifies the development of scalable applications, allowing for easy adaptation to different problem sizes.

Key Results

The paper presents strong quantitative results demonstrating LF's performance:

  • Outperforms Actor Frameworks: On average, LF's C++ runtime achieves a speedup of 1.86x over Akka and 1.42x over CAF for 20 worker threads, calculated using the geometric mean of benchmark speedups.
  • Competitive Microbenchmarks: For microbenchmarks designed to expose protocol overhead, LF shows comparable performance to Akka and CAF, and in some cases, significantly outperforms Akka.
  • Strong Performance on Concurrency Benchmarks: LF significantly outperforms CAF and Akka on concurrency benchmarks, highlighting the efficiency of its deterministic approach for these workloads.
  • Good Scalability: LF implementations scale well with an increasing number of worker threads, demonstrating their ability to leverage multi-core hardware effectively.
  • Optimization Impact: A comparison with an unoptimized LF runtime shows that the implemented optimizations (lock-free data structures, coordinated worker threads) provide an average speedup of 2.18x.

Limitations and Future Work

The authors acknowledge several limitations and suggest future directions:

  • Limited Mutation Support: LF currently has limited support for mutations, which are necessary for dynamically changing reactor topologies. This prevented the implementation of certain benchmarks from the Savina suite. Future work will focus on full runtime support for mutations.
  • Scheduler Optimizations: The current scheduler, while effective, is described as a simple heuristic. The authors believe more complex DAG-scheduling strategies could further improve performance by exploiting more parallelism, especially in cases where reactions could be executed in parallel but are currently serialized due to the scheduler's limitations.
  • Exploration of Advanced Scheduling: Future work will explore advanced scheduling algorithms to exploit more parallelism at runtime.
  • Benchmarking More Savina Benchmarks: The authors plan to implement the remaining Savina benchmarks that require mutations.
  • Federated Execution: The paper mentions that pipeline parallelism can be hindered by the scheduler's limitation of only executing reactions at the same tag. This can be overcome by using a federated execution strategy, which is suggested for future exploration.

Summary updated

Abstract

Actor frameworks and similar reactive programming techniques are widely used for building concurrent systems. They promise to be efficient and scale well to a large number of cores or nodes in a distributed system. However, they also expose programmers to nondeterminism, which often makes implementations hard to understand, debug, and test. The recently proposed reactor model is a promising alternative that enables deterministic concurrency. In this article, we present an efficient, parallel implementation of reactors and demonstrate that the determinacy of reactors does not imply a loss in performance. To show this, we evaluate Lingua Franca (LF), a reactor-oriented coordination language. LF equips mainstream programming languages with a deterministic concurrency model that automatically takes advantage of opportunities to exploit parallelism. Our implementation of the Savina benchmark suite demonstrates that, in terms of execution time, the runtime performance of LF programs even exceeds popular and highly optimized actor frameworks. We compare against Akka and CAF, which LF outperforms by 1.86× and 1.42×, respectively.
BibTeX
@article{menard2023high,
  author = {Christian Menard and Marten Lohstroh and Soroush Bateni and Matthew Chorlian and Arthur Deng and Peter Donovan and Clément Fournier and Shaokai Lin and Felix Suchert and Tassilo Tanneberger and Hokeun Kim and Jerónimo Castrillón and Edward A. Lee},
  title = {{High-performance Deterministic Concurrency Using <scp>Lingua Franca</scp>}},
  journal = {ACM Transactions on Architecture and Code Optimization},
  year = {2023},
  doi = {10.1145/3617687},
}
Figure