License
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ECOOP.2017.26
URN: urn:nbn:de:0030-drops-72737
URL: http://drops.dagstuhl.de/opus/volltexte/2017/7273/
Go to the corresponding LIPIcs Volume Portal


Vollmer, Michael ; Spall, Sarah ; Chamith, Buddhika ; Sakka, Laith ; Koparkar, Chaitanya ; Kulkarni, Milind ; Tobin-Hochstadt, Sam ; Newton, Ryan R.

Compiling Tree Transforms to Operate on Packed Representations

pdf-format:
LIPIcs-ECOOP-2017-26.pdf (0.7 MB)


Abstract

When written idiomatically in most programming languages, programs that traverse and construct trees operate over pointer-based data structures, using one heap object per-leaf and per-node. This representation is efficient for random access and shape-changing modifications, but for traversals, such as compiler passes, that process most or all of a tree in bulk, it can be inefficient. In this work we instead compile tree traversals to operate on pointer-free pre-order serializations of trees. On modern architectures such programs often run significantly faster than their pointer-based counterparts, and additionally are directly suited to storage and transmission without requiring marshaling. We present a prototype compiler, Gibbon, that compiles a small first-order, purely functional language sufficient for tree traversals. The compiler transforms this language into intermediate representation with explicit pointers into input and output buffers for packed data. The key compiler technologies include an effect system for capturing traversal behavior, combined with an algorithm to insert destination cursors. We evaluate our compiler on tree transformations over a real-world dataset of source-code syntax trees. For traversals touching the whole tree, such as maps and folds, packed data allows speedups of over 2x compared to a highly-optimized pointer-based baseline.

BibTeX - Entry

@InProceedings{vollmer_et_al:LIPIcs:2017:7273,
  author =	{Michael Vollmer and Sarah Spall and Buddhika Chamith and Laith Sakka and Chaitanya Koparkar and Milind Kulkarni and Sam Tobin-Hochstadt and Ryan R. Newton},
  title =	{{Compiling Tree Transforms to Operate on Packed Representations}},
  booktitle =	{31st European Conference on Object-Oriented Programming (ECOOP 2017)},
  pages =	{26:1--26:29},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-035-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{74},
  editor =	{Peter M{\"u}ller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7273},
  URN =		{urn:nbn:de:0030-drops-72737},
  doi =		{10.4230/LIPIcs.ECOOP.2017.26},
  annote =	{Keywords: compiler optimization, program transformation, tree traversal}
}

Keywords: compiler optimization, program transformation, tree traversal
Seminar: 31st European Conference on Object-Oriented Programming (ECOOP 2017)
Issue Date: 2017
Date of publication: 13.06.2017


DROPS-Home | Fulltext Search | Imprint Published by LZI