null
(Ed.)
A compiler’s optimizer operates over abstract syntax trees
(ASTs), continuously applying rewrite rules to replace sub-
trees of the AST with more efficient ones. Especially on large
source repositories, even simply finding opportunities for
a rewrite can be expensive, as optimizer traverses the AST
naively. In this paper, we leverage the need to repeatedly find
rewrites, and explore options for making the search faster
through indexing and incremental view maintenance (IVM).
Concretely, we consider bolt-on approaches that make use
of embedded IVM systems like DBToaster, as well as two
new approaches: Label-indexing and TreeToaster, an AST-
specialized form of IVM. We integrate these approaches into
an existing just-in-time data structure compiler and show
experimentally that TreeToaster can significantly improve
performance with minimal memory overheads.
more »
« less
