Context-guided splitting: optimising method dispatch in dynamic languages

Dynamic languages are widely used, for instance on the server, in the browser, as well as for machine learning and scientific computing. Languages such as Ruby are attractive to developers, because they offer a diverse set of dynamic features, such as late binding, dynamic typing, and meta-programming capabilities. While these features grant a high degree of expressiveness, they also bring extra complexity to the runtime systems to achieve good performance. For instance, a common optimisation invented almost half a century ago minimises the run-time overhead of dynamic dispatch by using lookup caches. Splitting and inlining achieve similar goals. TruffleRuby is a modern runtime using these optimisations. It is built on top of GraalVM, a meta-compilation system that aims at re-using complex run-time components such as a just-in-time compiler between several language implementations.

In this dissertation, I investigate dynamic dispatch and method splitting in dynamic languages and aim to reduce their run-time overhead. As a first step, I investigate whether the long-held assumptions they use about call behaviour are still valid today and find that they indeed largely are. However, the analysis also uncovers that around 90% of splitting in TruffleRuby might be redundant. As a solution to this oversplitting, I propose Context-Guided Splitting, an alternative splitting heuristic that guides splitting decisions using contextual insight, i.e., the types of the current arguments of a call. It aims to reduce memory usage and compilation time by re-using previously split methods.

I evaluate the effectiveness of Context-Guided Splitting by comparing it with other splitting strategies on a diverse set of 37 Ruby benchmarks running on top of TruffleRuby, ranging from micro-benchmarks to larger, industry-inspired workloads. I show that Context-Guided Splitting successfully monomorphises 100% of megamorphic call-sites, and 99.3% (min. 96.8%, max. 100%) of polymorphic call-sites on average. Compared to the standard splitting approaches, it benefits polymorphic, and especially megamorphic benchmarks most, for which we observe a decrease of 56.6% of the time spent in garbage collection, and a decrease of run time compilation time by 37.5% (min. -78.9%, max. 2.39×). Across the benchmark set as a whole, it decreases the AST size by 5.3% (min. -52.4%, max. 74.3%). With these results, we believe that Context-Guided Splitting will benefit large, real-world applications running on top of meta-compilation systems, making these systems more suitable for use in practice.