An Efficient Implementation of Guard-Based Synchronization for an Object-Oriented Programming Language
Shucai Yao, Emil Sekerinski · 2025
Read An Efficient Implementation of Guard-Based Synchronization for an Object-Oriented Programming Language by Shucai Yao, Emil Sekerinski (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-20850.txt.
Introduction
Guarded commands are a tidy way to write concurrent programs: a block runs atomically only when its guard condition holds. Shucai Yao and Emil Sekerinski show in 2025 that this clean model, long thought too slow to run, can in fact run fast.
Their implementation for an experimental object-oriented language, Lime, mixes coroutines, operating system worker threads, and careful management of object queues and stacks. Guards attach to objects, which keeps the bookkeeping local. On synthetic benchmarks the result compared well with hand-tuned concurrency in C with threads, and with Go, Erlang, Java, and Haskell. The authors argue specification-friendly concurrency does not have to tax performance.
Catalog record
| CREATOR | Shucai Yao, Emil Sekerinski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 24 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-20850
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Efficient Implementation of Guard-Based Synchronization for an Object-Oriented Programming Language Thanks: Work performed while affiliated with McMaster University. Shucai Yao, Emil Sekerinski Abstract In the shared variable model of concurrency, guarded atomic actions restrict the possible interference between processes by regions of atomic execution. The guard specifies the condition for entering an atomic region. That is a convenient model for the specification and verification of concurrent programs, but it has eschewed efficient execution so far. This article shows how guarded atomic actions, when attached to objects, can be implemented highly efficiently using a combination of coroutines, operating-system worker threads, and dedicated management of object queues and stacks. The efficiency of an experimental language, Lime, is shown to compare favourably with that of C/Pthreads, Go, Erlang, Java, and Haskell on synthetic benchmarks. 1 Introduction For concurrency based on shared variables , there is a long history of specifying synchronization and atomicity by atomic guarded commands ( atomic actions ), e.g. in conditional critical regions [ 21 ] , the Owicki-Gries theory [ 30 ] , Unity [ 12 ] , action systems [ 6 ] , TLA [ 27 ] , Seuss [ 28 ] , as well as in model checkers for concurrent programs. Atomic guarded commands are also used in verification tools, e.g. Event-B [ 2 ] and CIVL [ 33 ] . While an implementation of conditional critical regions by software transactional memory [ 19 ] was proposed, Occam [ 25 ] , Ada [ 24 , 10 ] , and Go [ 17 ] allow limited forms of atomic guarded commands: none of these supports guarded commands g\to S where the guard g being true initiates the execution of S . The common wisdom is that guarded commands cannot be implemented efficiently: “the price that must be paid for this automatic scheme is performance” [ 9 ] . Instead, mainstream languages offer semaphores [ 14 , 15 ] , monitors [ 22 ] , and variations thereof. Given the suitability—and today’s ubiquity—of object-oriented languages for modelling program domains, the notion that objects are naturally “units of concurrency” emerged early on [ 7 , 26 ] . The actor model [ 3 ] with asynchronous message passing stems from early work on (rule-based) AI systems [ 20 ] . Erlang is the first inherently concurrent programming language that implements the actor model [ 5 ] . The actor model has since then been used by Scala and other programming languages. The Eiffel programming language differs from that by using method calls for synchronous communication and re-interprets preconditions as method guards [ 34 ] . Yet another form of concurrent objects is proposed in [ 16 ] . CSP extends the notion of a guarded command by allowing the guard to contain synchronous communication with other processes of a program [ 23 ] . CSP influenced the designs of Occam [ 25 ] and Go [ 17 ] . In these languages, the structure of programs is dominated by processes (called goroutines in Go) and the object structure is de-emphasized. Processes are created explicitly, rather than being implicitly started by guarded commands of the form g\to S . Work on the correctness and refinement of action systems led to natural object-oriented extensions [ 8 , 11 , 31 ] : objects communicate by method calls, synchronize by guarded methods, and have atomic actions that specify concurrent execution. As actions are atomic, execution would need backtracking if an object with a blocking method is called: if an action with body S\mathbin{;}x.m()\mathbin{T} is called and method m blocks, the effect of S has to be reversed as the action must either be executed to completion or not executed. If S contains method calls, the effect of that call has to be reversed. While the model is simple, no efficient implementations exist. This work explores how guarded commands can be implemented highly efficiently when viewing objects as the “unit of concurrency”. Object-oriented action systems are taken as the basis and modified to allow execution without backtracking. The following section introduces our experimental language, Lime, through examples and defines it in terms of guarded commands with parallel composition and atomicity brackets. Section 3 discusses the scheme for guard evaluation, the implementation with cooperative scheduling of user-level coroutines, and the runtime system with object queues local to worker threads and global queues. Section 4 presents three synthetic benchmarks with fine-grained concurrency. 2 An Action-based Object-oriented Programming Language ⬇ class Doubler var x : int init () this . x := 0 method store ( u : int ) this . x := 2 * u method retrieve (): int return this . x class DelayedDoubler var y : int var d : bool init () this . y , this . d := 0, true method store ( u : int ) this . y , this . d := u , false method retrieve () : int when this . d do return this . y action double when not this . d do this . y , this . d := 2 * y , true Figure 1: Delayed doubler in Lime Lime uses indentation for bracketing. The guarded command g\to S is written as when g do S , where g is a Boolean expression and S is a statement. Methods and actions can be guarded. When a method is called and its guard is false, the call is suspended; it can be resumed when the guard becomes true. Actions are repeatedly executed by selection an action with a true guard nondeterministically. Actions have a name, but cannot be called. Only one method or action in an object can execute at a time, but multiple objects can execute concurrently. The class Doubler in Figure 1 allows an integer to be stored and its double value to be retrieved [ 13 , 31 ] . The class DelayedDoubler performs the same functionality but doubles “in the background”: method store sets field d to false , which blocks calls to retrieve until the action double performs doubling and sets d to false . Thus, a call to store can return quickly. This example is representative of calls that enable a background activity, like storing data in files, sending data over a network, or requesting remote data. The methods and actions in an object are executed atomically up to method calls . Since Doubler and DelayedDoubler do not contain method calls, all methods and actions are executed atomically. Here, x\bmod 2=0 is an invariant of Doubler and DelayedDoubler refines Doubler through the relation d\Rightarrow y=2*u . In Lime, only an object’s own fields can be accessed; thus, we leave out this in subsequent examples. Method and action guards must be only over the fields of an object. Figure 2: Possible state of a priority queue after adding 4, 5, 7, 6 ⬇ class PriorityQueue var m , p : int var l : PriorityQueue var a , r : bool init () l , a , r , m := nil , false , false , 0 method empty () : bool when not r do return l = nil method add (