Abstract | ||
---|---|---|
Applications in many domains are based on a series of traversals of tree structures, and fusing these traversals together to reduce the total number of passes over the tree is a common, important optimization technique. In applications such as compilers and render trees, these trees are heterogeneous: different nodes of the tree have different types. Unfortunately, prior work for fusing traversals falls short in different ways: they do not handle heterogeneity; they require using domain-specific languages to express an application; they rely on the programmer to aver that fusing traversals is safe, without any soundness guarantee; or they can only perform coarse-grain fusion, leading to missed fusion opportunities. This paper addresses these shortcomings to build a framework for fusing traversals of heterogeneous trees that is automatic, sound, and fine-grained. We show across several case studies that our approach is able to allow programmers to write simple, intuitive traversals, and then automatically fuse them to substantially improve performance. |
Year | Venue | DocType |
---|---|---|
2019 | arXiv: Programming Languages | Journal |
Volume | Citations | PageRank |
abs/1904.07061 | 0 | 0.34 |
References | Authors | |
0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Laith Sakka | 1 | 6 | 2.15 |
Kirshanthan Sundararajah | 2 | 3 | 2.07 |
Ryan Newton | 3 | 802 | 70.80 |
Milind Kulkarni | 4 | 744 | 45.29 |