Sound, Fine-Grained Traversal Fusion for Heterogeneous Trees - Extended Version
| Autor: | Sakka, Laith, Sundararajah, Kirshanthan, Newton, Ryan R., Kulkarni, Milind |
|---|---|
| Rok vydání: | 2019 |
| Předmět: | |
| Druh dokumentu: | Working Paper |
| Popis: | 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. Comment: Extended version of "Sound Fine-Grained Traversal Fusion for Heterogeneous Trees" Sakka et al., PLDI 2019 |
| Databáze: | arXiv |
| Externí odkaz: |
|