Just-in-time performance without warm-up

Scala has been developed as a language that deeply integrates with the Java ecosystem. It offers seamless interoperability with existing Java libraries. Since the Scala compiler targets Java bytecode, Scala programs have access to high-performance runtimes including the HotSpot virtual machine.

HotSpot provides impressive performance results achieved via just-in-time compilation. It starts program execution in interpreter mode, collecting profile feedback about called methods. This information allows HotSpot to identify hot spots in the program, which are then compiled on the fly to native code. This compilation scheme enables high peak performance at the cost of warmup time required to collect the profile data and perform just-in-time compilation.

This is a good example of the traditional tradeoff between ahead-of-time (AOT) and just-in-time (JIT) compilation. With AOT, compilers have less information, but the runtime story is reasonably straightforward. With JIT, compilers have more information, which enables advanced optimizations, but the runtime story becomes complicated.

In this dissertation, we present the design and implementation of Scala Native, an optimizing compiler for Scala. With Scala Native, Scala programs are compiled ahead of time, which avoids runtime compilation and enables instant startup times. On the other hand, Scala Native is able to match and supersede the peak performance of HotSpot on our benchmarks. In addition to that, Scala Native is a general-purpose Scala compiler - programs compiled by Scala Native closely match the behavior of programs compiled by the Scala compiler.

First, we introduce NIR, an intermediate representation designed with ahead-of-time compilation in mind. NIR represents programs in the single-static assignment form and has support for object-oriented features such as virtual dispatch and multiple inheritance. This representation is a key enabler of our compilation and optimization pipeline.

Secondly, we present Interflow, a link-time optimizer that takes advantage of the closed-world assumption to optimize the whole program at once. Our optimizer employs a number of techniques including partial evaluation, allocation sinking, and method duplication. The combination of these techniques allows Scala Native to outperform HotSpot on the majority of our benchmarks.

Finally, we describe how to improve runtime performance even further based on profile feedback. We propose a technique that splits methods apart isolating key hot paths that are then optimized more aggressively than the cold parts of the program. This provides a further performance advantage over HotSpot.

Surgical Precision JIT Compilers

Hassan Chafi, Tiark Rompf

Just-in-time (JIT) compilation of running programs provides more optimization opportunities than offline compilation. Modern JIT compilers, such as those in virtual machines like Oracle's HotSpot for Java or Google's V8 for JavaScript, rely on dynamic profiling as their key mechanism to guide optimizations. While these JIT compilers offer good average performance, their behavior is a black box and the achieved performance is highly unpredictable. In this paper, we propose to turn JIT compilation into a precision tool by adding two essential and generic metaprogramming facilities: First, allow programs to invoke JIT compilation explicitly. This enables controlled specialization of arbitrary code at run-time, in the style of partial evaluation. It also enables the JIT compiler to report warnings and errors to the program when it is unable to compile a code path in the demanded way. Second, allow the JIT compiler to call back into the program to perform compile-time computation. This lets the program itself define the translation strategy for certain constructs on the fly and gives rise to a powerful JIT macro facility that enables "smart" libraries to supply domain-specific compiler optimizations or safety checks. We present Lancet, a JIT compiler framework for Java bytecode that enables such a tight, two-way integration with the running program. Lancet itself was derived from a high-level Java bytecode interpreter: staging the interpreter using LMS (Lightweight Modular Staging) produced a simple bytecode compiler. Adding abstract interpretation turned the simple compiler into an optimizing compiler. This fact provides compelling evidence for the scalability of the staged-interpreter approach to compiler construction. In the case of Lancet, JIT macros also provide a natural interface to existing LMS-based toolchains such as the Delite parallelism and DSL framework, which can now serve as accelerator macros for arbitrary JVM bytecode.

Assoc Computing Machinery2014

Interflow: interprocedural flow-sensitive type inference and method duplication

Martin Odersky, Denys Shabalin

Scala heavily relies on a number of object-oriented abstractions to support its feature-rich collections library. There are known techniques that optimize those abstractions away in just-in-time (JIT) compilers, but applying them in the ahead-of-time (AOT) setting is problematic. Profile-guided optimization (PGO) lets AOT compilers apply some of the same optimizations that JIT compilers employ, but it comes at a high complexity cost. In this paper, we introduce Interflow, an alternative approach towards ahead-of-time optimization of Scala programs which relies on interprocedural flow-sensitive type inference and method duplication. Our evaluation shows that an Interflow-based optimizing compiler built on top of the Scala Native toolchain outperforms existing PGO-based optimizing compilers for Scala. Moreover, we demonstrate that Interflow and PGO can be combined to achieve further improvements. On our benchmarks, with both Interflow and PGO enabled, the Scala Native toolchain approaches the performance of the HotSpot JVM.

2018

Compiling scala for the Java virtual machine

Michel Schinz

Scala is a new programming language developed at EPFL and incorporating the most important concepts of object-oriented and functional languages. It aims at integrating well with the Java and .NET platforms: their respective libraries are accessible without glue code, and the compiler can produce programs for both virtual machines. This thesis focuses on the compilation of two important concepts of Scala : mixin inheritance and run time types. The compilation techniques are presented in the context of the Java virtual machine, but could be adapted easily to other similar environments. Mixin inheritance is a relatively recent form of inheritance, offering new capabilities compared to single inheritance, without the complexity of multiple inheritance. We propose two implementation techniques for mixin inheritance: code copying and delegation. The implementation used in the Scala compiler is then presented and justified. Run time types make it possible for a program to examine the type of its values during execution. This possibility is interesting in itself, offering new capabilities to the programmer. Furthermore, run time types are also required to implement other high level concepts, like pattern matching, type-safe serialisation and reflection. We propose an implementation technique based on the representation of types as values, and show how to use the run time types of the underlying virtual machine to implement those of Scala. The techniques presented in this thesis have been implemented in our Scala compiler, scalac. This enabled us to evaluate these techniques, in particular their impact on the performances of programs. This evaluation was performed on several real, non-trivial programs.

EPFL2005

Surgical Precision JIT Compilers

Hassan Chafi, Tiark Rompf

Assoc Computing Machinery2014