Tag Archives: VMs

JIT Data Structures, Fully Reflective VMs, and Meta-Circular Meta-Tracing

The year leading up to SPLASH has been pretty busy. Beside my own talks on Tracing vs. Partial Evaluation and Optimizing Communicating Event-Loop Languages with Truffle, there are going to be three other presentations on work I was involved in.

Just-In-Time Data Structures

On Thursday, Mattias De Wael is going to present his work on Just-in-Time Data Structures at Onward!. For me this work is exciting, because I hope that this could make programming with standard data structures quite a bit simpler in the long run. Today, ‘scripting’ languages like Ruby and Python provide a small set of very versatile data structures they call lists or arrays that can be used for many many different use cases. But instead of having a one-size-fits-all implementation, a runtime system can ideally identify a specific ‘strategy’ to be used dynamically, and even change it over the course of a program. So, in a nice language, we would merely declare a few fundamental properties such as being ordered, and how to compare items, and the runtime system will figure out whether to use a hash, tree, array, or other kind of implementation. Well, that’s at least my vision. Abstract below:

Today, software engineering practices focus on finding the single right data representation (i.e., data structure) for a program. The right data representation, however, might not exist: relying on a single representation of the data for the lifetime of the program can be suboptimal in terms of performance. We explore the idea of developing data structures for which changing the data representation is an intrinsic property. To this end we introduce Just-in-Time Data Structures, which enable representation changes at runtime, based on declarative input from a performance expert programmer. Just-in-Time Data Structures are an attempt to shift the focus from finding the “right’’ data structure to finding the right sequence of data representations. We present JitDS-Java, an extension to the Java language, to develop Just-in-Time Data Structures. Further, we show two example programs that benefit from changing the representation at runtime.

  • Just-In-Time Data Structures. Mattias De Wael, Stefan Marr, Joeri De Koster, Jennifer B. Sartor, and Wolfgang De Meuter. Proceedings of the 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, ACM, (October 2015)

Towards Fully Reflective Environments

On Friday, Guido Chari is going to present his work Towards Fully Reflective Environments also at Onward!. This is a first step in the direction of bringing all parts of a runtime system to life. While classic systems such as Smalltalk and CLOS go pretty far in reifying language elements and enabling us to interact with them on a meta-level, they typically exclude important aspects of the runtime system such as GC, object representation, interpreter semantics, and JIT compilation. Some of these aspects can be observed via debugging interfaces, but what we have in mind here is to have a complete meta-circular runtime system where each and every aspect is reified and can be adapted at runtime. What Guido is going to present is only a first step, especially since performance is not yet addressed. But, we are working on it.

Modern development environments promote live programming (LP) mechanisms because it enhances the development experience by providing instantaneous feedback and interaction with live objects. LP is typically supported with advanced reflective techniques within dynamic languages. These languages run on top of Virtual Machines (VMs) that are built in a static manner so that most of their components are bound at compile time. As a consequence, VM developers are forced to work using the traditional edit-compile-run cycle, even when they are designing LP-supporting environments. In this paper we explore the idea of bringing LP techniques to the VM domain for improving their observability, evolution and adaptability at run-time. We define the notion of fully reflective execution environments (EEs), systems that provide reflection not only at the application level but also at the level of the VM. We characterize such systems, propose a design, and present Mate v1, a prototypical implementation. Based on our prototype, we analyze the feasibility and applicability of incorporating reflective capabilities into different parts of EEs. Furthermore, the evaluation demonstrates the opportunities such reflective capabilities provide for unanticipated dynamic adaptation scenarios, benefiting thus, a wider range of users.

  • Towards Fully Reflective Environments. Guido Chari, Diego Garbervetsky, Stefan Marr, and Stéphane Ducasse. Proceedings of the 2015 ACM International Symposium on New Ideas, New Paradigms, and Reflections on Programming & Software, ACM, (October 2015)

A Formal Foundation for Trace-Based JIT Compilers

Last but not least, and already on Monday at the WODA workshop, Maarten Vandercammmen is going to present A Formal Foundation for Trace-Based JIT Compilers. The bit that I find most interesting in that work is the meta-circular meta-tracer for a little Scheme, which is hiding in there. The focus of the work changed over time, but initially he was working on identifying the essence of meta-tracing. And he now got a pretty small and manageable framework to experiment with meta-tracing, and even execute multiple levels of interpreters that are all traced through. I’d say that’s a pretty neat foundation for future research, more approachable than a huge practical system such as RPython, but of course, also not without drawbacks. For instance, a proper optimizer is missing so far. But let’s see where this gets us in the future!

Trace-based JIT compilers identify frequently executed program paths at run-time and subsequently record, compile and optimize their execution. In order to improve the performance of the generated machine instructions, JIT compilers heavily rely on dynamic analysis of the code. Existing work treats the components of a JIT compiler as a monolithic whole, tied to particular execution semantics. We propose a formal framework that facilitates the design and implementation of a tracing JIT compiler and its accompanying dynamic analyses by decoupling the tracing, optimization, and interpretation processes. This results in a framework that is more configurable and extensible than existing formal tracing models. We formalize the tracer and interpreter as two abstract state machines that communicate through a minimal, well-defined interface. Developing a tracing JIT compiler becomes possible for arbitrary interpreters that implement this interface. The abstract machines also provide the necessary hooks to plug in custom analyses and optimizations.

  • A Formal Foundation for Trace-Based JIT Compilers Maarten Vandercammen, Jens Nicolay, Stefan Marr, Joeri De Koster, Theo D’Hondt, and Coen De Roover. Proceedings of the 13th International Workshop on Dynamic Analysis. Pittsburgh, PA, USA, ACM, (October 2015)

Are We There Yet? Simple Language-Implementation Techniques for the 21st Century

The first results of my experiments with self-optimizing interpreters was finally published in IEEE Software. It is a brief and very high-level comparison of the Truffle approach with a classic bytecode-based interpreter on top of RPython. If you aren’t familiar with either of these approaches, the article is hopefully a good starting point. The experiments described in it use SOM, a simple Smalltalk.

Since writing things down, the work on the different SOM implementations has continued resulting in better overall performance. This reminds me: thanks again to the communities around PyPy/RPython and Truffle/Graal for their continues support!

The preprint of the paper is available as PDF and HTML version. For the experiments, we also prepared an online appendix with a few more details and made the experimental setup available on GitHub.

Abstract

With the rise of domain-specific languages (DSLs), research in language implementation techniques regains importance. While DSLs can help to manage the domain’s complexity, it is rarely affordable to build highly optimizing compilers or virtual machines, and thus, performance remains an issue. Ideally, one would implement a simple interpreter and still reach acceptable performance levels. RPython and Truffle are two approaches that promise to facilitate language implementation based on simple interpreters, while reaching performance of the same order of magnitude as highly optimizing virtual machines. In this case study, we compare the two approaches to identify commonalities, weaknesses, and areas for further research to improve their utility for language implementations.

  • Are We There Yet? Simple Language Implementation Techniques for the 21st Century.; Stefan Marr, Tobias Pape, Wolfgang De Meuter; IEEE Software 31, no. 5, pp. 60-67.
  • Paper: PDF, HTMLonline appendix
  • DOI: 10.1109/MS.2014.98
  • BibTex: BibSonomy

Supporting Concurrency Abstractions in High-level Language Virtual Machines

Last Friday, I defended my PhD dissertation. Finally, after 4 years and a bit, I am done. Finally. I am very grateful to all the people supporting me along the way and of course to my colleagues for their help.

My work focused on how to build VMs with support for all kind of different concurrent programming abstractions. Since you don’t want to put them into a VM just one by one, I was looking for a unifying substrate that’s up to the task. Below, you’ll find the abstract as well as the slides.

In addition to the thesis text itself, the implementations and tools are available. Please see the project page for more details.

Abstract

During the past decade, software developers widely adopted JVM and CLI as multi-language virtual machines (VMs). At the same time, the multicore revolution burdened developers with increasing complexity. Language implementers devised a wide range of concurrent and parallel programming concepts to address this complexity but struggle to build these concepts on top of common multi-language VMs. Missing support in these VMs leads to tradeoffs between implementation simplicity, correctly implemented language semantics, and performance guarantees.

Departing from the traditional distinction between concurrency and parallelism, this dissertation finds that parallel programming concepts benefit from performance-related VM support, while concurrent programming concepts benefit from VM support that guarantees correct semantics in the presence of reflection, mutable state, and interaction with other languages and libraries.

Focusing on these concurrent programming concepts, this dissertation finds that a VM needs to provide mechanisms for managed state, managed execution, ownership, and controlled enforcement. Based on these requirements, this dissertation proposes an ownership-based metaobject protocol (OMOP) to build novel multi-language VMs with proper concurrent programming support.

This dissertation demonstrates the OMOP’s benefits by building concurrent programming concepts such as agents, software transactional memory, actors, active objects, and communicating sequential processes on top of the OMOP. The performance evaluation shows that OMOP-based implementations of concurrent programming concepts can reach performance on par with that of their conventionally implemented counterparts if the OMOP is supported by the VM.

To conclude, the OMOP proposed in this dissertation provides a unifying and minimal substrate to support concurrent programming on top of multi-language VMs. The OMOP enables language implementers to correctly implement language semantics, while simultaneously enabling VMs to provide efficient implementations.

  • Supporting Concurrency Abstractions in High-level Language Virtual Machines, Stefan Marr. Software Languages Lab, Vrije Universiteit Brussel, Pleinlaan 2, B-1050 Brussels, Belgium, PhD Dissertation, January 2013. ISBN 978-90-5718-256-3.
  • Download: PDF.
  • BibTex: BibSonomy

Slides

Modularity and Conventions for Maintainable Concurrent Language Implementations: A Review of Our Experiences and Practices

Modularity: AOSD’12 will be in Potsdam at the end of March, and I am looking forward especially to the MISS’12 workshop.

My understanding of the workshop’s format is that its goal is to encourage the participants to actively interact. Far to often, workshops are just a collection of semi-related presentations, without a common problem and without a common goal. I fear a bit, the MISS workshop will have a similar problem. Being part of the program committee, I have seen all the submissions and the author do tend to prefer business as usual over actual position papers. From my perspective, this is really a pity. It is a lost chance to really exchange ideas actively and perhaps start collaborations with interesting people. A technical paper, with a few ideas and a work-in-progress prototype does not qualify as a position paper in my opinion. Usually, that kind of work only encourages discussion between people that have been working on similar things already. But let’s see how it turns out.

Our contribution to the workshop is a little experience report on how concurrency and modularity are related to each other in interpreter implementations. And, to make it short: modularity does matter to manage concurrency invariants, but things like AOP are far less important than some people might hope.

Abstract

In this paper, we review what we have learned from implementing languages for parallel and concurrent programming, and investigate the role of modularity. To identify the approaches used to facilitate correctness and maintainability, we ask the following questions: What guides modularization? Are informal approaches used to facilitate correctness? Are concurrency concerns modularized? And, where is language support lacking most?

Our subjects are AmbientTalk, SLIP, and the RoarVM. All three evolved over the years, enabling us to look back at specific experiments to understand the impact of concurrency on modularity.

We conclude from our review that concurrency concerns are one of the strongest drivers for the definition of module boundaries. It helps when languages offer sophisticated modularization constructs. However, with respect to concurrency, other language features like single-assignment are of greater importance. Furthermore, tooling that enables remodularization taking concurrency invariants into account would be of great value.

  • Modularity and Conventions for Maintainable Concurrent Language Implementations: A Review of Our Experiences and Practices, Stefan Marr, Jens Nicolay, Tom Van Cutsem, Theo D’Hondt, Proceedings of the 2nd Workshop on Modularity In Systems Software (MISS’2012), ACM (2012), to appear.
  • Paper: PDF
    ©ACM, 2012. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. To appear.
  • BibTex: BibSonomy

Towards an Actor-based Concurrent Machine Model

Already quite a while ago, I was involved in writing a workshop paper about an actor model for virtual machines. Actually, the main idea was to find a concurrency model for a VM which supports multi-dimensional separation of concerns. However, AOP is not that interesting for me at the moment, so I am focussing on the concurrency, especially the actor-based VM model.

After one year, I am back looking at that paper, and it still looks like a great model. Think, I will incorporate it into my manycore VM now 🙂

Abstract

In this position paper we propose to extend an existing delegation-based machine model with concurrency primitives. The original machine model which is built on the concepts of objects, messages, and delegation, provides support for languages enabling multi-dimensional separation of concerns (MDSOC). We propose to extend this model with an actor-based concurrency model, allowing for both true parallelism as well as lightweight concurrency primitives such as coroutines. In order to demonstrate its expressiveness, we informally describe how three high-level languages supporting different concurrency models can be mapped onto our extended machine model. We also provide an outlook on the extended model’s potential to support concurrency-related MDSOC features.

  • Towards an Actor-based Concurrent Machine Model, Hans Schippers, Tom Van Cutsem, Stefan Marr, Michael Haupt, Robert Hirschfeld, Proceedings of the fourth workshop on the Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS), New York, NY, USA, ACM (2009), p. 4–9.
  • Paper: PDF
    ©ACM, 2009. This is the author’s version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ICOOOLPS’09 July 6, 2009, Genova, Italy. http://doi.acm.org/10.1145/1565824.1565825
  • BibTex: BibSonomy