Comparing R Bytecode Compilers Written in R, Java, and Rust

R is a dynamic language mainly used by statisticians, which targets numerical computations more than tree traversals. In R, integers, real numbers or strings are actually vectors, e.g. 1 is an integer vector of size 1.

R is implemented in C and interoperates well with it, serving as glue for performance sensitive functions in native code. To boost actual R code performance, among other R optimization projects [9, 8], based on a JIT [11, 12, 5], the R interpreter added a bytecode interpreter [13] to its AST interpreter. The bytecode compiler is itself written in R, not in C, which presents unique challenges in terms of performance and expressivity.

As part of our ongoing effort to build a compilation service for R, we have implemented the R bytecode compiler in both Java and Rust. The goal is to output the very same bytecode as the original R compiler (byte-to-byte compatible), as a first step before adding optimizations, to make sure the new compilers are correct. However, unlike the R compiler, the alternative versions are separated from the rest of the R VM.¹¹1The R VM connects to a compile service through gRPC (https://grpc.io/) which also caches the compiled bytecode. We compare the designs of the 3 compilers, and show performance numbers. Unsurprisingly, the Java and Rust versions win over the R implementation.

When running R code, the source code is parsed into an AST represented as a R value, a SEXP. Then, the compiler may transform a SEXP into a bytecode object. The R bytecode is then executed by a stack-based VM entirely written in C.

Bytecode objects are bulky: they contain a bytecode instructions and a constant pool. Bytecode instructions are represented by a vector of integers. The constant pool stores the constant values in the bytecode instructions, the AST of the compiled expression and of subexpressions, and source locations for each instruction. There are over 129 fat instructions and some of them perform a lot of work including calling back to the AST interpreter.

The compiler is single pass and does very few optimizations: constant folding and inlining. If a call cannot be inlined, it emits it as a call to a closure, which might or might not be bytecode compiled.

Constant folding.

It is applied directly on the AST, not on the generated bytecode. Only some types (e.g. numbers, booleans and strings) and when they are less than a predefined maximal size, and only some predefined functions, e.g. math operators, are folded.

Inlining.

It is crucial because most syntax in R, even if and {, is a function. Without inlining, most code is actually passed to the AST interpreter to be run. As the user can modify any functions, the compiler inserts a guard that checks wether the target function has been masked at runtime. Only a fixed set of functions, including control flow, math, stats, assignments and vector operations, can be inlined.

Function bodies can be explictly compiled with cmpfun or cmpfile. Functions that are “large enough” are also JIT-compiled after 1 or 2 invocations. Upon installation of a package, all its functions are compiled.

As we want to get the same bytecode as the R compiler, the Rust and Java 22 versions roughly follow the same single pass design, but use different language features and data structures.

To check the correctness of the bytecode compilers, we compare the outputs of the Rust and Java versions to the R version. We use snapshot testing: the R interpreter is run to generate the bytecode for crafted R functions, and functions from base, utils, graphics, methods, and stats packages. For the Java version, we developed our own snapshot testing framework, and for Rust, we use insta.³³3https://insta.rs/

The R version has 2 919 lines of codes, where the Java version has 8 811 lines and the Rust one, 6 690, as shown on Fig 1. However, the Java and Rust versions required to write the SEXP and serialization handling, which already exists in the R version.

We compile all functions in base, utils, compiler, tools, and stats packages, in total 97K lines, and measure the time to compile, excluding deserialization, repeating the measurement 10 times. Some packages have functions that compile to many opcodes (utils, tools, stats) while others to fewer opcodes, i.e. compiler, the R bytecode compiler itself, or base, which for many functions just performs a call to a C binding (Table 1). For the Java version, for each of those 10 iterations, we compile all the functions a first time and then repeat to warmup the JIT.

On an Apple M4 Pro with 12 cores and 24 GB of RAM, the R version takes about 17 seconds to compile all the functions. The Java version is around 33x quicker than the R version, and the Rust version is around 48x quicker than the R version, as seen on Fig. 2.

We also measure the peak heap memory usage of each of the compilers. For R, we call the gc() and for Java, we use the Runtime class, which give information about the memory usage with their respective GCs. For Rust, we use valgrind[10] with the massif heap profiler. Rust has the highest peak heap memory usage, with 1GB, as the arenas are not freed until the end. The Java version has a peak memory usage of 200MB in average, and the R version has a peak memory usage of 300MB.