Building High-level Debuggers for Concurrent Languages with Truffle: The Missing Bits

Note: This post is meant for people familiar with Truffle. For introductory material, please see for instance this list.

With its debugger support, Truffle provides a rich foundation for custom debugging features for a wide range of language concepts.

However, for our implementation of various breakpoint and stepping semantics for fork/join, threads and locks, software transactional memory, actors, and communicating processes, we needed a number of custom features, which somewhat duplicate part of the framework. One reason is that the debugger’s granularity is on the level of nodes, which can be too coarse-grained and requires restructuring the node implementations. Another reason is that some important aspects of concurrency are dealt with outside of the AST, for instance, in an event loop like JavaScript has it.

This post details our experience with Truffle and discusses the custom mechanisms that we implemented to deal with tradeoffs such as implementation complexity and fine-grained breakpoint semantics. Specifically, I am going into:

  1. custom breakpoint checks
  2. support for additional sequential stepping strategies
  3. support for activity-specific stepping strategies
  4. expression breakpoints
  5. Java conditions for breakpoints

Examples for High-level Breakpoints and Stepping

Before I go into what we did and what Truffle could still provide, I briefly give some examples of what wanted to achieve.

Languages such as JavaScript or Newspeak have the notion of event loops. Event loops provide a convenient abstraction to handle lightweight concurrency, for instance to react to events generated in a user interface or from external sources. However when debugging such applications, the callback-based programming style, with or without promises, inverts the control flow, and it becomes hard to reason about programs in a natural way.

In a debugger, it would thus be nice to be able to step through the callbacks in a promise chain and focus on their execution and effects. In our debugger, we offer such a mechanism with step to resolution, which breaks execution when callbacks are executed following the current promise being resolved with a value. On the operation that resolves the promise, we can also set a corresponding breakpoint. Thus, whenever we resolve a promise from the lexical location, we trigger the debugger as soon as the callbacks are executed.

Let’s look at a JavaScript example:

1
2
3
4
5
6
7
8
9
10
11
12
let rootPromise = new Promise((resolve, _) => {
  console.log("chance to capture resolve() and execute it");
  resolve("Promise done");
});

rootPromise.then(msg => {
  console.log("Step 1");
  return "Next step";
}).then(msg => {
  console.log("Step 2");
  return "Final step";
});

Ideally, we would be able to set a breakpoint on the resolve() call in line 3, which says that we want to break whenever a callback on the rootPromise is triggered. In this case, it would only be the one on line 7. Once reaching execution there, we might want to simply step to the next callback, which is triggered by resolving the promise that’s returned by then(), i.e., the one on line 10.

So, what exactly do we need in a Truffle language implementation to realize such breakpoints and stepping operations?

1. Custom Breakpoint Checks

One of the features not provided by Truffle is the ability to check for breakpoint information within a language implementation. The main reason is that everything should be done with wrapper nodes of the instrumentation API.

Unfortunately, there are some cases where that is not convenient, because we would need to restructure AST nodes. Or more importantly, it is not sufficient, because we need the information that a breakpoint was set at another point in the execution, and triggering it at the lexical location would not be useful. This is for instance the case for the example with the promises above.

To realize such promise breakpoints and stepping in SOMns, we set a flag for the breakpoint on the ‘message’ that is going to lead to the promise resolution. This looks something like this:

@Child BreakpointNode promiseResolverBreakpoint;

@Specialization
void sendPromiseMessage(Object[] args, Promise rcvr) {
  PromiseSendMessage msg = new PromiseSendMessage(args, rcvr,
      promiseResolverBreakpoint.executeShouldHalt());
  msg.send();
}

The key here is promiseResolverBreakpoint, which is an instance of our own BreakpointNode. The BreakpointNode works similar to Truffle’s builtin breakpoints and specializes itself on whether the breakpoint is set or not. So that at run time, there would not be any overhead for checking it, since it merely needs to return true or false as a compile-time constant.

One important difference to normal Truffle breakpoints is that our breakpoint nodes do not only have a source location, but also a type. This enables us to distinguish various different types of breakpoints for the same source location, which is important if one wants more complex operations than single stepping and line breakpoints.

The breakpoint node is roughly implemented as follows, skipping the breakpoint type here for brevity:

public abstract class BreakpointNode {

  protected final BreakpointEnabling bE;

  protected BreakpointNode(final BreakpointEnabling breakpoint) {
    this.bE = breakpoint;
  }

  public abstract boolean executeShouldHalt();

  @Specialization(assumptions = "bEUnchanged", guards = "!bE.enabled")
  public final boolean breakpointDisabled(
      @Cached("bE.unchanged") final Assumption bEUnchanged) {
    return false;
  }

  @Specialization(assumptions = "bEUnchanged", guards = "bE.enabled")
  public final boolean breakpointEnabled(
      @Cached("bE.unchanged") final Assumption bEUnchanged) {
    return true;
  }
}

public final class BreakpointEnabling {
  public boolean              enabled;
  public transient Assumption unchanged;

  BreakpointEnabling() {
    this.unchanged = Truffle.getRuntime().createAssumption("unchanged breakpoint");
    this.enabled = breakpointInfo.isEnabled();
  }

  public synchronized void setEnabled(final boolean enabled) {
    if (this.enabled != enabled) {
      this.enabled = enabled;
      this.unchanged.invalidate();
      this.unchanged = Truffle.getRuntime().createAssumption("unchanged breakpoint");
    }
  }
}

With this node in place, we can efficiently determine whether a breakpoint is set. When scheduling a callback, we can now check the flag on the message to see whether a breakpoint was set at the sending side. Triggering the breakpoint is however a little bit more involved, because we want it to trigger in the right position, but such callbacks are handled by event loops outside of a Truffle AST. This is going to be detailed in the next section.

For other types of breakpoints, it might be simpler, because we might already be at the right place in the AST. For these cases, we simple construct a node marked with Truffle’s AlwaysHalt tag, which ensures the debugger will trigger a breakpoint for us. After checking the condition, we simply execute the node like this:

@Specialization
Object doSomethingComplex(...) {
  // ...
  if (obj.breakpointWasSet) {
    suspendExec.executeGeneric(frame); // tagged with AlwaysHalt, triggers debugger
  }
  // ...
}

This ensures that Truffle triggers the breakpoint and uses its normal facilities to obtain information about current stack and local variables in the debugger.

2. Support for Additional Sequential Stepping Strategies

Back to the example of breaking when a callback is triggered from a promise.

As mentioned before, the main problem here is that we have the relevant information outside of the Truffle AST. This means, we cannot really trigger a debugger, and even if we could, the available state would possibly be confusing and not very helpful for the developers. What we do instead is to use a stepping strategy to execute the callback until it reaches a useful point. Fortunately, Truffle already has the notion of a RootTag to mark the first node of method that belongs to what a developer would consider the body of a method, i.e., ignoring possible pro- and epilogues.

We added a corresponding stepping strategy to Truffle to be able to say: execute this method until you reach the first node tagged with RootTag.

This is implemented in the following class:

class StepUntilNextRootNode extends SteppingStrategy {
  @Override
  boolean step(DebuggerSession s, EventContext ctx, SteppingLocation location) {
    return location == SteppingLocation.BEFORE_ROOT_NODE;
  }
}

For other kind of breakpoints, we also like to be able to step to the point after executing the root node. For that case we added a StepAfterNextRootNode strategy. This one is a little bit more complex, because we need to remember the first root found, and only trigger a suspension when we are in the AFTER_ROOT_NODE location for the same root node, and for the same stack height. This is necessary to account for recursion. Note, the AFTER_ROOT_NODE location is also a custom addition and comes with the corresponding AFTER_STATEMENT location, which allow us to set breakpoints or step to the point after which a node is executed.

Overall, I find stepping strategies a rather useful way of expressing what the debugger should do, and stopping after the execution of a node seems also useful. Unfortunately, the current design in Truffle does not support any extension by tools. While we only desired to step before and after (root) nodes for sequential debugging so far, general stepping strategies are another topic.

3. Activity-specific Stepping Strategies

To implement stepping from one turn of the event loop to the next, we use an entirely custom approach to stepping strategies. But the next turn is only one possible point we are interested in. Others could be more specific to a promise or a message to break at a corresponding callback or when the message is received.

For the various stepping operations, we have a thread-local field with the strategy, which then can be checked, depending on the type of strategy, either in the event loop or in the BreakpointNode.

In our event loop, we currently check for instance for the stepping to the next turn and to return to a promise resolution, which corresponds to following execution to the next promise chained to a then(.) in the JavaScript example from the beginning. In these cases, we set flags on the activity or promise objects to indicate a breakpoint later on.

For other stepping operations, for instance step to next promise resolution, we rely on a check in the BreakpointNode.

The previously shown code of BreakpointNode ignored this detail. So, it should look more like this:

@Specialization(assumptions = "bpUnchanged", guards = "!bp.enabled")
public final boolean breakpointDisabled(
    @Cached("bp.unchanged") final Assumption bpUnchanged) {
  return breakpoint.getSteppingType().isSet();
}

This means, if the breakpoint is disabled, we check whether the thread-local field with the stepping strategy is set to the type of the current breakpoint. This check is conditional on whether debugging is enabled, but has an overhead on the peak performance during a debugging session.

This seems to duplicate quite some of the mechanisms already included in Truffle for stepping. However, since we need different types of stepping strategies, it did not seem possible to integrate it into Truffle without approaching the question of how to design it in an extensible way.

4. Expression Breakpoints

After talking about the dynamics of breakpoints let’s briefly switch to setting breakpoints from a user interface. As you might imagine, that’s somewhat relevant to support fancy breakpoints in an IDE and expose them to users.

The biggest gap Truffle currently has here is that it misses an API to set breakpoints on expressions. Its Breakpoint.Builder currently only supports setting breakpoints on lines. If we consider the earlier JavaScript example with promises, we might want to set breakpoints on the then(.) or resolve(.) method calls, and perhaps chose what type of breakpoint to set. We could break just before executing the methods or when their consequences take effect.

We actually take two different approaches to the problem. For some use cases, for instance breaking before a call to resolve(.), we use a custom extension of the Breakpoint.Builder that supports filtering by source section in terms of line number, column, and section length, as well as a specific tag for the source section. So, in this case, we just rely on Truffle’s breakpoints with a more fine-grained way of setting them.

For other cases, we completely manage the breakpoints ourselves with the aforementioned BreakpointNode as discussed in sec. 1.

5. Java Conditions for Breakpoints

One final mechanism we rely on is the ability to set simple Java conditions on breakpoints. Currently, Truffle only supports setting conditions from the language itself. Thus, I could set a JavaScript condition to break on a line if some condition holds, for instance a variable has a certain value. However, there is no corresponding support to set conditions inside the implementation.

Our use case is to set breakpoints on functions that are triggered by messages, or in JavaScript it would correspond to set a breakpoint specifically for the case that a function is directly executed from the even loop, i.e., as a callback. This can be helpful for stepping or to trigger a breakpoint only for the case one is specifically interested in.

To realize this, we extended Breakpoint with a simple callback that returns a boolean. We use it to check whether the calling method is of a specific type, which signifies in SOMns that a method/function was activated via a message send, i.e., from the event loop.

Conclusion

In this post, I discussed a number of things we need to do in SOMns to get advanced breakpoints for various concurrency models. Some of these duplicate mechanisms in Truffle, which could perhaps just be leveraged if they would be designed to be more extensible. This includes the notion of breakpoints, which should allow the notion of different types on the same line/expression. It also includes nodes that allow run-time queries of a breakpoint status to propagate it as part of the application, and stepping strategies that can be queried and acted upon outside the Truffle AST, i.e., for instance as part of an event loop.

The other things I am missing in Truffle could be offered by extending the existing implementation. This includes additional sequential stepping strategies and locations, expression breakpoints, and simple condition on breakpoints.

These facilities could make a major difference for people interested in building better debuggers for dynamic languages. Looking at other people’s debuggers, for instance IntelliJ IDEA’s Java support or Chrome’s step into async, their extensions look cool and very helpful, but with the power we have in Truffle, they are more than trivial! It’s a shame to leave all the potential unused. Dynamic languages such as Ruby, JavaScript, Python, or R could really benefit from great debuggers, because most productive development is done in the debugger, where you see what you do.

#bikexit17, Hello England, Goodbye EU?

Academics are infamous for their project names and abbreviations, so, let’s call this #bikexit17…

As some people already know, I am starting a new position in October. I will be a lecturer at the University of Kent as part of the Programming Languages and Systems group. While I am pretty excite about the opportunity to work with a very interesting group, it reminded me of all the little annoying things I went through when moving from Lille to Linz. One of them was shipping my bicycle. Last time, I was already thinking, well, why not ride it instead of shipping it?

And that’s where we are this time around. I got a few holidays I have to take anyway. And, I could use a real offline holiday for a change. Especially, since I suspect the start in Canterbury to be a bit stressful.

It should be possible to do the whole trip with about 11 days of cycling. Currently, my plan is as follows:

  • Day 1: Linz -> Passau, a brief 90km to warm up (Sept. 9)
  • Day 2: Passau -> Regensburg, ca. 140km (Sept. 10)
  • Day 3: Regensburg -> Ansbach, ca. 140km (Sept. 11)
  • Day 4: Ansbach -> Mosbach, ca. 130km (Sept. 12)
  • Day 5: Mosbach -> Heidelberg -> Mannheim -> Worms, somesightseeing and ca. 90km (Sept. 13)
  • probably a day of rest

  • Day 6: Worms -> Koblenz, ca. 150km (Sept. 15)
  • Day 7: Koblenz -> Bonn or Cologne, ca. 70-100km (Sept. 16)
  • Day 8: Bonn/Cologne Maastricht, ca. 140km (Sept. 18)
  • Day 9: Maastricht -> Brussels, ca. 100km (Sept. 19)
  • spending a couple of days in Brussels and around

  • Day 10: Brussels -> Lille, ca. 130km (Sept. 21)
  • perhaps another day in Lille
  • Day 11: Lille -> Canterbury, ca. 130km (Sept. 23)

If I am passing by your region, I’d be happy to have some company along the way. Will probably start out with a friend to go to Passau, and might have company around Bonn. Flanders should also be a very nice area for cycling 😉

Since this is my first trip of this magnitude, I am also happy for any tips, recommendations, does/dont’s, you might be willing to share. Got already some, but wouldn’t mind more.

And, just to be clear: such adventures are drastically simplified by being able to travel without passport, or roaming charges. So, thank you EU. Thank you very much!

A 10 Year Journey, Stop 5: Growing the SOM Family

SOM, the Simple Object Machine, has been a steady companion for much of my research. As mentioned earlier, all this work on virtual machines started for me with CSOM, a C-based implementation of a simple Smalltalk language. From the beginning, SOM was meant as a vehicle for teaching language implementation techniques as well as doing research on related topics. As such, it is keep simple. The interpreter implementations do not aim to be fast. Instead, concepts are supposed to be expressed explicitly and consistent, so that the code base is accessible for students. Similarly, the language is kept simple and includes dynamic typing, objects, classes, closures, and non-local returns. With these features the core of typical object-oriented languages is easily covered. One might wonder about exceptions, but their dynamic semantics very similar to non-local returns and thus covered, too.

Originally, SOM was implemented in Java. Later, CSOM, SOM++ (a C++-based implementation), AweSOM (a Smalltalk-based implementation) joined the family. Some of this history is documented on the old project pages at the HPI, where much of this work was done.

When I picked up maintaining the SOM family for my own purposes, I added PySOM, a Python-based implementation, and JsSOM implemented in JavaScript. As part of the work on building a fast language implementation, I also added TruffleSOM, a SOM implementation using the Truffle framework on top of the JVM. As well as RPySOM, an RPython-based bytecode interpreter for SOM, and RTruffleSOM, a Truffle-like AST interpreter implemented in RPython.

A Fast SOM

For TruffleSOM and RTruffleSOM, the focus was on performance. This means, the clarity and simplicity got somewhat compromised. In the code base, that’s usually visible in form of concepts being implemented multiple times to cover different use cases or special cases. Otherwise, the language features haven’t really changed. The only thing that got extended is the set of basic operations implemented for SOM, which we call primitives, i.e., builtin operations such as basic mathematical operations, bit operations, and similar things that either cannot be expressed in the language, or are hard to express efficiently.

The main reason to extend SOM’s set of primitives was to support a wide set of benchmarks. With the Are We Fast Yet project, I started a project to compare the performance of a common set of object-oriented languages features across different programming languages. One of the main goals was for me to be able to understand how fast TruffleSOM and RTruffleSOM are, for instance compared to state-of-the-art Java or JavaScript VMs.

Well, let’s have a look at the results:

Performance Overview of SOM Implementations
Performance Overview of SOM Implementations

The figure shows the performance of various SOM implementations relative to Java 1.8, i.e., the HotSpot C2 compiler. To be specific, it shows the peak performance discounting warmup and compilation cost. As another reference point for a common dynamic language, I also included Node.js 8.1 as a JavaScript VM.

As the numbers show, TruffleSOM and RTruffleSOM reach about the same performance on the used benchmarks. Compared to Java, they all are about 2-4x slower. Looking at the results for Node.js, I would argue that I managed to reach the performance of state-of-the-art dynamic language VMs with my little interpreters.

The simple SOM implementations are much slower however. SOM and SOM++ are about 500x slower. That is quite a bit slower than the performance reached by the Java interpreter, which is only about 10-50x slower than just-in-time compiled and highly optimized Java. The slowness of SOM and SOM++ are very much expected because of their focus on teaching. Beside many of the little design choices that are not optimal for performance, there is also the used bytecode set, which is designed to be fairly minimal and thus causes a high overhead compared to the optimized bytecode sets used by Java, Ruby, or Smalltalk 80.

Making SOM++ Fast with Eclipse OMR

As shown with TruffleSOM and RTruffleSOM, meta-compilation approaches are one possible way to gain state-of-the-art performance. Another promising approach is the reuse of existing VM technology in the form of components to improve existing systems. One of the most interesting systems in that field is currently Eclipse OMR. The goal of this project, which is currently driven by IBM, is to enable languages such as Ruby or Python to use the technology behind IBM’s J9 Java Virtual Machine. At some point, they decided to pick up SOM++ as a show case for their technology. They first integrated their garbage collector, and later added some basic support for their JIT compiler. My understanding is that it currently compiles each bytecode of a SOM method into the J9 IR using the JitBuilder project, allowing a little bit of inlining, but not doing much optimizations. And the result is a 4-5x speedup over the basic SOM++ interpreter. For someone implementing languages, such a speedup is great, and not to snub at, even if we start from a super slow system. But as a result, you reach the performance of optimized interpreters, while still maintaining a minimal bytecode set and the general simplicity of the system. Of course, minus the complexity of the JIT compiler itself.

To reach the same performance as TruffleSOM and RTruffleSOM, there is quite a bit more work to be done. I’d guess, SOM++ OMR would need more profiling information to guide the JIT compiler. And, it probably will also need a few other tricks like an efficient object model and stack representation to really achieve the same speed. But anyway, to me it is super cool to see someone else picking up SOM for their purposes and built something new with it 🙂.

Other Uses of SOM

And while we are at it, over the years, some other projects spawned off from SOM. There was NXTalk for the Lego Mindstorm system. My own ActorSOM++, which implemented a simple Actor language as part of SOM. And more recently, SOMns, a Newspeak implementation derived from TruffleSOM. You might have noticed, it’s actually a bit faster than TruffleSOM itself :) And, it supports all kind of concurrency models, from actors over CSP, STM, fork/join, to classic threads and locks.

Similar to SOM++ OMR, the Mu Micro VM project picked up a SOM implementation to showcase their own technology. Specifically, they used RPySOM, an RPython-based bytecode interpreter for their experiments.

Guido Chari forked TruffleSOM to built TruffleMate and experiment with making really all parts of a language runtime reflectively accessible, while maintaining excellent performance.

And last, but not least, Richard Roberts is currently working on a Grace implementation on top SOMns.

So there are quite a few things happening around SOM and the various offspring. I hope, the next 10 years are going to be as much fun as the last.

And with that, I’ll end this series of blog posts. If you’re interested to learn more, check out the community section on the SOM homepage, ask me on Twitter @smarr, or sent me an email.

Older Posts

Subscribe via RSS