TL;DR
This paper introduces Lingua Franca (LF), a programming language that enables high-performance, deterministic concurrency by leveraging a reactor model. LF demonstrates that determinism doesn't sacrifice performance, outperforming popular actor frameworks like Akka and CAF on benchmark suites by up to 1.86x and 1.42x respectively.
What Problem Does This Paper Address?
Modern concurrent systems, especially those leveraging actor frameworks, often introduce nondeterminism. While this can be useful for expressiveness, it significantly complicates understanding, debugging, and testing programs. This nondeterminism arises from the inherent nature of message passing and the lack of a strict temporal model in many actor systems. The authors argue that this nondeterminism is often not necessary for achieving good performance on parallel hardware and that a deterministic approach can be both performant and easier to manage. They aim to provide a model that offers the benefits of concurrency without the pitfalls of nondeterminism.
Methods
The core of the paper is the Lingua Franca (LF) language, which is built upon the reactor model. Reactors are described as deterministic actors with explicit ports and connections, operating on a logical timeline. LF's approach to determinism is rooted in its timed semantics, which ensures that events are ordered consistently, preventing nondeterministic race conditions.
Key methodological contributions include:
- Reactor Model: A formal model for concurrent computation that emphasizes determinism through a logical timeline and explicit dependencies.
- Coordination Language: LF acts as a coordination layer, allowing programmers to compose components written in various target languages (C++, Python, etc.) while managing their concurrency.
- Optimized C++ Runtime: A custom runtime system designed to efficiently exploit parallelism on multi-core processors by analyzing the program's dependency graph (APG) and scheduling reactions in parallel where possible.
- Scalable Connection Patterns: LF provides syntax extensions for concisely defining complex inter-reactor connections, enabling programs to scale easily.
Datasets
The primary dataset used for evaluation is the Savina benchmark suite. This suite is designed for actor languages and frameworks and includes a variety of micro, concurrency, and parallelism benchmarks. The authors ported 22 of the 30 Savina benchmarks to the C++ target of LF. They note that some benchmarks were omitted due to fundamental differences in the actor and reactor models or issues with the benchmarks themselves (e.g., requiring dynamic actor creation, which LF's current mutation support doesn't fully cover).
Key Insights and Ideas
- Determinism Doesn't Mean Slow: The most significant insight is that a deterministic concurrency model, enforced by LF's reactor semantics, does not inherently lead to performance degradation. In fact, it can enable more efficient execution by avoiding the overhead of explicit synchronization often required in nondeterministic actor models.
- Logical Time is Key: LF's use of a logical timeline, rather than relying solely on physical time, is crucial for achieving determinism. This allows for predictable ordering of events, even when physical execution times might vary.
- Explicit Dependencies Enable Parallelism: By statically declaring dependencies between reactors and reactions, LF's compiler can construct an acyclic precedence graph (APG). This graph precisely defines the order in which reactions must execute, while also identifying reactions that can run in parallel without compromising determinism.
- Coordination vs. Computation: LF focuses on the coordination aspect, allowing programmers to leverage existing languages and libraries for the actual computation, thus benefiting from mature ecosystems.
Key Results
The paper presents a comprehensive performance evaluation using the Savina benchmarks, comparing LF's C++ runtime against Akka and CAF.
- Overall Speedup: On average, for 20 worker threads, LF achieved a speedup of 1.85x over Akka and 1.42x over CAF. These speedups were calculated using the geometric mean across individual benchmarks.
- Concurrency Benchmarks: LF significantly outperformed CAF and Akka in concurrency benchmarks, highlighting the efficiency of its deterministic model in handling complex interactions.
- Parallelism Benchmarks: LF performed comparably to Akka and CAF in parallelism benchmarks, demonstrating its ability to scale with more threads.
- Optimizations Impact: A comparison with an unoptimized LF runtime showed an average speedup of 2.18x for the optimized C++ runtime, underscoring the effectiveness of their scheduling and data structure optimizations.
Limitations and Future Work
- Mutation Support: LF's current implementation does not fully support mutations, which are necessary for dynamically changing reactor topologies. This prevented the porting of certain benchmarks that rely on dynamic actor creation. Future work will focus on implementing robust mutation support.
- Scheduling Heuristics: The current scheduling algorithm uses a heuristic that, while effective, can lead to non-optimal execution in some cases (e.g., pipeline parallelism). The authors plan to explore more advanced scheduling strategies to further exploit parallelism.
- Runtime Overhead: While LF generally outperforms actor frameworks, the paper notes that for very simple sequential programs, the optimizations for parallel execution might introduce a slight overhead.
- Benchmarking Limitations: The authors acknowledge that the Savina suite, while comprehensive, has some issues and that the comparison between C++ and Scala (Akka) involves factors like JVM performance.
Future work also includes exploring more advanced scheduling algorithms, implementing the remaining Savina benchmarks, and potentially integrating techniques for fault tolerance in distributed LF programs.
Summary updated