Scala AST Persistence | EPFL Graph Search

The Scala compiler uses ASTs (abstract syntax trees) as an intermediate representation before generating bytecode. With the development of Scala macros which expand trees at compile time, being able to access, modify and recompose ASTs within the compilation scope is becoming more and more important. One of the common scenarios of using macros is inspecting abstract syntax trees within reach in order to learn more about the code being transformed, to apply more powerful optimizations, etc. However, arguments to macros can depend on third-party libraries, which are precompiled as bytecode and don't have their ASTs available. It would therefore be great to have a way to publish ASTs along with the bytecode. The publishing of those ASTs should be a choice of the programmer and should take as little space as possible in order to be transparent to the user.

Two approaches to portable macros

Eugene Burmako, Fengyun Liu

For any programming language that supports macros and has multiple implementations (each with different AST definitions), there is a common problem: how to make macros that operate on ASTs portable among different compiler implementations? Implementing portable macros is especially important for statically typed languages like Scala, as IDE vendors usually have different implementations of the language in order to support rich IDE features. Unportable macros compromise IDE features and degrade programming experience. We describe two approaches to the portability problem based on two different views on macros: (1) the tree-based approach, which views macros as operations on abstract syntax trees, solves the problem by defining standard abstract syntax trees; (2) the syntax-based approach, which views macros as operations on abstract syntax, solves the problem by defining standard abstract syntax. We show that the latter has significant practical advantages, especially in supporting semantic macros that use type information of ASTs to transform user code. Based on the idea, we implemented a new macro system, Gestalt, for the experimental Scala compiler, Dotty. The new implementation solves several long-standing problems of the current Scala macro system and demonstrates advantages over alternative approaches. Our solution has been adopted in the official new Scala macro system.

2017

Just-in-time performance without warm-up

Denys Shabalin

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.

EPFL2020

Just-in-time performance without warm-up

Denys Shabalin

EPFL2020