TASTYTRUFFLE: Just-in-Time Specialization of Parametric Polymorphism

Parametric polymorphism allows programmers to express algorithms independently of the types of values that they operate on. The approach used to implement parametric polymorphism can have important performance implications. One popular approach, erasure, uses a uniform representation for generic data, which entails primitive boxing and other indirections that harm performance. Erasure destroys type information that could be used by language implementations to optimize generic code. We present TASTYTRUFFLE, an implementation for a subset of the Scala programming language. Instead of JVM bytecode, TASTYTRUFFLE interprets Scala's TASTy intermediate representation, a typed representation wherein generic types are not erased. TASTy's precise type information empowers TASTYTRUFFLE to implement generic code more effectively. In particular, it allows TASTYTRUFFLE to reify types as run-time objects that can be passed around. Using reified types, TASTYTRUFFLE supports heterogeneous box-free representations for generic values. TASTYTRUFFLE also uses reified types to specialize generic code, producing monomorphic copies of generic code that can be easily and reliably optimized by its just-in-time (JIT) compiler. Empirically, TASTYTRUFFLE is competitive with standard JVM implementations on a small set of benchmark programs; when generic code is used with multiple types, TASTYTRUFFLE consistently outperforms the JVM. The precise type information in TASTy enables TASTYTRUFFLE to find additional optimization opportunities that could not be uncovered with erased JVM bytecode.