Domains: Safe Sharing Among Actors

The actor model is a pretty nice abstraction to reason about completely independent entities that interact purely by exchanging messages. However, for software development, some see the pure actor model as too fine-grained and too restrictive exposing many of the low-level issues such as data races again on a higher level again, and thereby forgoing some of its conceptual benefits.

We see the actor model also as a nice way to think about problems. However, we consider them in a more coarse-grained version. For us, actors are not on the level of objects but rather on the level of groups of objects like in the communicating event loop model as proposed by the E language and AmbientTalk. On this level, actors represent larger components, or subsystems if you will, and on multicore systems the question arises how parallelism and resource sharing can be achieved in a safe and efficient manner, without sacrificing the actor model’s (and communicating event loop model’s) nice properties such as freedom of deadlocks and low-level data races.

With the recently published paper below, Joeri took the lead on developing a first idea in the direction of managing shared state in the context of a language based on communicating event loops. The paper is an extension of an earlier workshop paper, and since then, we developed the ideas already further and devised complementary solutions to cover a wider set of uses cases. Still, I think the paper is interesting in its own right, and also defines the semantics of the approach in a formal, and thereby less ambiguous manner.

Abstract

The actor model is a concurrency model that avoids issues such as deadlocks and data races by construction, and thus facilitates concurrent programming. While it has mainly been used for expressing distributed computations, it is equally useful for modeling concurrent computations in a single shared memory machine. In component based software, the actor model lends itself to divide the components naturally over different actors and use message-passing concurrency for the interaction between these components. The tradeoff is that the actor model sacrifices expressiveness and efficiency with respect to parallel access to shared state.

This paper gives an overview of the disadvantages of the actor model when trying to express shared state and then formulates an extension of the actor model to solve these issues. Our solution proposes domains and synchronization views to solve the issues without compromising on the semantic properties of the actor model. Thus, the resulting concurrency model maintains deadlock-freedom and avoids low-level data races.

  • Domains: Safe Sharing Among Actors; Joeri De Koster, Stefan Marr, Theo D’Hondt, Tom Van Cutsem; Science of Computer Programming, 2014, to appear.
  • Paper: PDF
  • BibTex: BibSonomy

Towards Composable Concurrency Abstractions

One of the big questions that came up during my PhD was: ok, now you got your fancy ownership-based metaobject protocol, and you can implement actors, agents, communicating sequential processes, software transactional memory, and many others, but now what? How are you going to use all of these in concert in one application? Finding a satisfying answer is unfortunately far from trivial.

Since I am far from the first person thinking about these problems, we, that is Tom, Joeri, and most notably Janwillem put out heads together to figure out what the main issues are, and what the solutions are others have come up with. Janwillem took the lead and started to write down our first preliminary findings in a paper for the PLACES workshop, co-located with ETAPS in April.

Below, you can find the preprint and abstract of the paper. It is only a first small step, but I hope it won’t be the last one because in the end, the OMOP is only going to be useful if we actually can figure out how to combine the various concurrent programming models it enables in a safe and efficient manner.

Abstract

In the past decades, many different programming models for managing concurrency in applications have been proposed, such as the actor model, Communicating Sequential Processes, and Software Transactional Memory. The ubiquity of multi-core processors has made harnessing concurrency even more important. We observe that modern languages, such as Scala, Clojure, or F#, provide not one, but multiple concurrency models that help developers manage concurrency. Large end-user applications are rarely built using just a single concurrency model. Programmers need to manage a responsive UI, deal with file or network I/O, asynchronous workflows, and shared resources. Different concurrency models facilitate different requirements. This raises the issue of how these concurrency models interact, and whether they are composable. After all, combining different concurrency models may lead to subtle bugs or inconsistencies.

In this paper, we perform an in-depth study of the concurrency abstractions provided by the Clojure language. We study all pairwise combinations of the abstractions, noting which ones compose without issues, and which do not. We make an attempt to abstract from the specifics of Clojure, identifying the general properties of concurrency models that facilitate or hinder composition.

  • Towards Composable Concurrency Abstractions; Janwillem Swalens, Stefan Marr, Joeri De Koster, Tom Van Cutsem; Proceedings of the workshop on Programming Language Approaches to Concurrency and Communication-cEntric Software, 2014, co-located with ETAPS.
  • Paper: PDF
  • BibTex: BibSonomy

Parallel Gesture Recognition with Soft Real-Time Guarantees

More than three years ago, Lode and I started thinking about parallel event processing for realtime systems. The main use case back then was gesture and motion detection based on cameras such as the Kinect. Thierry created the first fully functional prototype called PARTE, and in addition to his master thesis, we wrote a workshop paper about it. Now, we finally got also the revised and extended version of this paper accepted.

Below, you can find preprint and abstract:

Abstract

Using imperative programming to process event streams, such as those generated by multi-touch devices and 3D cameras, has significant engineering drawbacks. Declarative approaches solve common problems but so far, they have not been able to scale on multicore systems while providing guaranteed response times.

We propose PARTE, a parallel scalable complex event processing engine that allows for a declarative definition of event patterns and provides soft real-time guarantees for their recognition. The proposed approach extends the classical Rete algorithm and maps event matching onto a graph of actor nodes. Using a tiered event matching model, PARTE provides upper bounds on the detection latency by relying on a combination of non-blocking message passing between Rete nodes and safe memory management techniques.

The performance evaluation shows the scalability of our approach on up to 64 cores. Moreover, it indicates that PARTE’s design choices lead to more predictable performance compared to a PARTE variant without soft real-time guarantees. Finally, the evaluation indicates further that gesture recognition can benefit from the exposed parallelism with superlinear speedups.

  • Parallel Gesture Recognition with Soft Real-Time Guarantees; Stefan Marr, Thierry Renaux, Lode Hoste, Wolfgang De Meuter; Science of Computer Programming, 2014, to appear.
  • Paper: PDF
  • BibTex: BibSonomy

OMOP Ported to Opal on top of Pharo 3

To prepare some experiments with Pharo’s new compiler infrastructure and a simple AST interpreter, I ported my implementation of the Ownership-based Metaobject Protocol (OMOP) to the Pharo 3. Loading the OMOP into an image will give you an STM implementation, a basic actor system, communicating sequential processes, Clojure-like agents, and active objects. Eventually, the goal is to provide a more extensive set of such concurrent programming mechanisms on top of the OMOP, but for now these five should already give an impression of how the OMOP itself works.

To try it out, it can be loaded into a recent Pharo 3 image with the following code snippet:

Gofer new
	squeaksource3: 'Omni';
	configuration; load.
(Smalltalk classNamed: 'ConfigurationOfOmni') load: #(ST Isolate)

How to get a JIT Compiler for Free: Implementing SOM Smalltalk with RPython and Truffle

Today at FOSDEM, I gave a brief talk on implementing SOM, a little Smalltalk, with RPython and Truffle. RPython, probably best known for the PyPy implementation, uses meta-tracing JIT compilation to make simple interpreters fast. Truffle, a research project of Oracle Lab, is an approach for building self-optimizing interpreters and in combination with Graal, it gives a JIT compiler for AST-like interpreters. In the talk, I briefly sketch both of them, without going into many details.

The slides are embedded below. Please note that the performance numbers given in the slides are preliminary. They reflect the current snapshot and your on results may very drastically. Further, TruffleSOM has much remaining optimization potential, as does RPySOM. So, these numbers should not be considered benchmarks for the potential of Truffle+Graal or RPython themselves.

Acknowledgments: I would like to thank Carl Friedrich Bolz and Tobias Pape for their help on RPySOM (cf. commit log), especially for making it fast. And, I would like to thank Oracle Labs and the Truffle+Graal community for guidance, support, and fixing bugs. Among others, and in alphabetic order: Andreas Wöß, Chris Seaton, Christian Humer, Christian Wimmer, Gilles Duboscq, Michael Haupt, Thomas Würthinger, Wei Zhang.