Memoising Scope Graph Query Resolution

Abstract

The Statix meta-language is a domain-specific language that is used to describe specifications for type systems using high-level declarative inference rules. Type checkers
can be automatically generated from these rules, saving one from the burden of writing
it manually. One of the problems with these generated type checkers is performance;
handwritten type checkers usually outperform the generated ones. Statix uses the formalism of scope graphs to represent name binding, and querying these scope graphs is
known to be the main performance bottleneck. Improving the performance of queries
means improving the performance of the type checkers generated by Statix.

In this thesis, we propose a memoised variant of the current state-of-the-art query
resolution algorithm that memoises data encountered during graph traversal, reducing
future queries to a cache lookup. We also identify common patterns in real-world scope
graphs and link those to the name binding structure that created them. We construct a
synthetic dataset with these patterns that is used to evaluate query resolution algorithms
with microbenchmarks. This gives us more granular information on what name binding
structures benefit most, if at all, from memoisation.

The results of these benchmarks are the performance differences between the memoised algorithm and the current state-of-the-art algorithm per identified pattern. They
show that our proposed algorithm breaks even in terms of performance after only two
queries for most patterns. Furthermore, we demonstrate that our proposed algorithm
and the current state-of-the-art provide identical efficacy. The tradeoffs are twofold: the
cache increases the memory usage of query resolution significantly and the query resolution parameters were tweaked to make caching possible, but less versatile. The changed
query parameters’ limitations should only be theoretical however, the Statix specification
for Java 1.5 has 23 out of 25 fully compatible queries.