Tag Archives: concurrency

SOMns 0.2 Release with CSP, STM, Threads, and Fork/Join

Since SOMns is a pure research project, we aren’t usually doing releases for SOMns yet. However, we added many different concurrency abstractions since December and have plans for bigger changes. So, it seems like a good time to wrap up another step, and get it into a somewhat stable shape.

The result is SOMns v0.2, a release that adds support for communicating sequential processes, shared-memory multithreading, fork/join, and a toy STM. We also improved a variety of things under the hood.

Note, SOMns is still not meant for ‘users’. It is however a stable platform for concurrency research and student projects. If you’re interested to work with it, drop us a line, or check out the getting started guide.

0.2.0 – 2017-03-07 Extended Concurrency Support

Concurrency Support

  • Added basic support for shared-memory multithreading and fork/join
    programming (PR #52)

    • object model uses now a global safepoint to synchronize layout changes
    • array strategies are not safe yet
  • Added Lee and Vacation benchmarks (PR #78)

  • Configuration flag for actor tracing, -atcfg=
    example: -atcfg=mt:mp:pc turns off message timestamps, message parameters and promises

  • Added Validation benchmarks and a new Harness.

  • Added basic Communicating Sequential Processes support.
    See PR #84.

  • Added CSP version of PingPong benchmark.

  • Added simple STM implementation. See s.i.t.Transactions and PR #81 for details.

  • Added breakpoints for channel operations in PR #99.

  • Fixed isolation issue for actors. The test that an actor is only created
    from a value was broken (issue #101, PR #102)

  • Optimize processing of common single messages by avoiding allocation and
    use of object buffer (issue #90)

Interpreter Improvements

  • Turn writes to method arguments into errors. Before it was leading to
    confusing setter sends and ‘message not understood’ errors.

  • Simplified AST inlining and use objects to represent variable info to improve
    details displayed in debugger (PR #80).

  • Make instrumentation more robust by defining number of arguments of an
    operation explicitly.

  • Add parse-time specialization of primitives. This enables very early
    knowledge about the program, which might be unreliable, but should be good
    enough for tooling. (See Issue #75 and PR #88)

  • Added option to show methods after parsing in IGV with
    -im/--igv-parsed-methods (issue #110)

Communicating Sequential Processes for Newspeak/SOMns

One possible way for modeling concurrent systems is Tony Hoare’s classic approach of having isolated processes communicate via channels, which is called Communicating Sequential Processes (CSP). Today, we see the approach used for instance in Go and Clojure.

While Newspeak’s specification and implementation come with support for Actors, I want to experiment also with other abstractions, and CSP happens to be an interesting one, since it models systems with blocking synchronization, also know as channels with rendezvous semantics. I am not saying CSP is better in any specific case than actors. Instead, I want to find out where CSP’s abstractions provide a tangible benefit.

But, the reason for this post is another one. One of my biggest quibbles with most CSP implementations is that they don’t take isolation serious. Usually, they provide merely lightweight concurrency and channels, but they rarely ensure that different processes don’t share any mutable memory. So, the door for low-level race conditions is wide open. The standard argument of language or library implementers is that guaranteeing isolation is not worth the performance overhead that comes with it. For me, concurrency is hard enough, so, I prefer to have the guarantee of proper isolation. Of course, another part of the argument is that you might need shared memory for some problems, but, I think we got a more disciplined approach for those problems, too.

Isolated Processes in Newspeak

Ok, so how can we realize isolated processes in Newspeak? As it turns out, it is pretty simple. Newspeak already got the notion of values. Values are deeply immutable objects. This means values can only contain values themselves, which as a consequence means, if you receive some value from a concurrent entity, you are guaranteed that the state never changes.

In SOMns, you can use the Value mixin to mark a class as having value semantics. This means that none of the fields of the object are allowed to be mutable, and that we need to check that fields are only initialized with values in the object’s constructor. Since Newspeak uses nested classes pretty much everywhere, we also need to check that the outer scope of a value class does not have any mutable state. Once that is verified, an object can be a proper deeply immutable value, and can be shared with out introducing any data races between concurrent entities.

Using this as a foundation, we can require that all classes that represent CSP processes are values. This gives us the guarantee that a process does not have access to any shared mutable state by itself. Note, this is only about the class side. The object side can actually be a normal object an have mutable state, which means, within a process, we can have normal mutable state/objects.

Using the value notion of Newspeak feels like a very natural solution to me. Alternative approaches could use a magic operator that cuts off lexical scope. This is something that I have seen for instance in AmbientTalk with its isolates. While this magic isolate keyword gives some extra flexibility, it is also a new concept. Having to ensure that a process’ class is a value requires that its outer lexical scope is a value, and thus, restricts a bit how we structure our modules, but, it doesn’t require any new concepts. One other drawback is here that it is often not clear that the lexical scope is a value, but I think that’s something where an IDE should help and provide the necessary insights.

In code, this looks then a bit like this:

class ExampleModule = Value ()(
  class DoneProcess new: channelOut = Process (
  | private channelOut = channelOut. |
  )(
    public run = ( channelOut write: #done )
  )
  
  public start = (
    processes spawn: DoneProcess
               with: {Channel new out}
  )
)
So, we got a class DoneProcess, which has a run method that defines what the process does. Our processes module allows us to spawn the process with arguments, which is in this case the output end of a channel.

Channels

The other aspect we need to think about is how can we design channels so that they preserve isolation. As a first step, I’ll only allow to send values on the channel. This ensure isolation and is a simple efficient check whether the provided object is a value.

However, this approach is also very restrictive. Because of the deeply immutable semantics of values, they are quite inflexible in my experience.

When thinking of what it means to be a value, imagine a bunch of random objects: they all can point to values, but values can never point back to any mutable object. That’s a very nice property from the concurrency perspective, but in practice this means that I often feel the need to represent data twice. Once as mutable, for instance for constructing complex data structures, and a second time as values so that I can send data to another process.

A possible solution might be objects with copy-on-transfer semantics, or actual ownership transfer. This could be modeled either with a new type of transfer objects, or a copying channel. Perhaps there are other options out there. But for the moment, I am already happy with seeing that we can have proper CSP semantics by merely checking that a process is constructed from values only and that channels only pass on values.

Since the implementation is mostly a sketch, there are of course more things that need to be done. For instance, it doesn’t yet support any nondeterminism, which requires an alt or select operation on channels.

Language Research with Truffle at the SPLASH’16 Conference

Next weekend starts one of the major conferences of the programming languages research community. The conference hosts many events including our Meta’16 workshop on Metaprogramming, SPLASH-I with research and industry talks, the Dynamic Languages Symposium, and the OOPSLA research track.

This year, the overall program includes 9 talks on Truffle and Graal-related topics. This includes various topics including optimizing high-level metaprogramming, low-level machine code, benchmarking, parallel programming. I posted a full list including abstracts here: Truffle and Graal Presentations @SPLASH’16. Below is an overview and links to the talks:

Sunday, Oct. 30th

AST Specialisation and Partial Evaluation for Easy High-Performance Metaprogramming (PDF)
Chris Seaton, Oracle Labs
Meta’16 workshop 11:30-12:00

Towards Advanced Debugging Support for Actor Languages: Studying Concurrency Bugs in Actor-based Programs (PDF)
Carmen Torres Lopez, Stefan Marr, Hanspeter Moessenboeck, Elisa Gonzalez Boix
Agere’16 workshop 14:10-14:30

Monday, Oct. 31st

Bringing Low-Level Languages to the JVM: Efficient Execution of LLVM IR on Truffle (PDF)
Manuel Rigger, Matthias Grimmer, Christian Wimmer, Thomas Würthinger, Hanspeter Mössenböck
VMIL’16 workshop 15:40-16:05

Tuesday, Nov. 1st

Building Efficient and Highly Run-time Adaptable Virtual Machines (PDF)
Guido Chari, Diego Garbervetsky, Stefan Marr
DLS 13:55-14:20

Optimizing R Language Execution via Aggressive Speculation
Lukas Stadler, Adam Welc, Christian Humer, Mick Jordan
DLS 14:45-15:10

Cross-Language Compiler Benchmarking—Are We Fast Yet? (PDF)
Stefan Marr, Benoit Daloze, Hanspeter Mössenböck
DLS 16:30-16:55

Thursday, Nov. 3rd

GEMs: Shared-memory Parallel Programming for Node.js (DOI)
Daniele Bonetta, Luca Salucci, Stefan Marr, Walter Binder
OOPSLA conference 11:20-11:45

Efficient and Thread-Safe Objects for Dynamically-Typed Languages (PDF)
Benoit Daloze, Stefan Marr, Daniele Bonetta, Hanspeter Mössenböck
OOPSLA conference 13:30-13:55

Truffle and Graal: Fast Programming Languages With Modest Effort
Chris Seaton, Oracle Labs
SPLASH-I 14:20-15:10

Domains: Sharing State in the Communicating Event-Loop Actor Model

It has been a while since we started working on how to extended the Actor model with mechanisms to safely share state. Our workshop paper on Tanks was published in 2013. And now finally, an extended version of this work was accepted for publication. Below you can find the abstract with a few more details on the paper, and of course a preprint of the paper itself.

Abstract

The actor model is a message-passing concurrency model that avoids deadlocks and low-level data races by construction. This facilitates concurrent programming, especially in the context of complex interactive applications where modularity, security and fault-tolerance are required. The tradeoff is that the actor model sacrifices expressiveness and safety guarantees with respect to parallel access to shared state.

In this paper we present domains as a set of novel language abstractions for safely encapsulating and sharing state within the actor model. We introduce four types of domains, namely immutable, isolated, observable and shared domains that each are tailored to a certain access pattern on that shared state. The domains are characterized with an operational semantics. For each we discuss how the actor model’s safety guarantees are upheld even in the presence of conceptually shared state. Furthermore, the proposed language abstractions are evaluated with a case study in Scala comparing them to other synchonisation mechanisms to demonstrate their benefits in deadlock freedom, parallel reads, and enforced isolation.

  • Domains: Sharing State in the Communicating Event-Loop Actor Model; Joeri De Koster, Stefan Marr, Tom Van Cutsem, Theo D’Hondt; Computer Languages, Systems & Structures (2016)
  • Paper: PDF
  • BibTex: BibSonomy

Open PostDoc Position on Programming Technology for Complex Concurrent Systems

We, or more specifically our colleagues from the Software Languages Lab in Brussels are looking for a post-doctoral researcher to work on a collaborative research project with us.

Head over to their page for the details.

For a bit more context on the position, have a look at the recently posted preprint titled “Towards Meta-Level Engineering and Tooling for Complex Concurrent Systems“. This position paper outlines some of the research challenges we want to work on.