Write a Blog >>
Thu 22 Jun 2017 14:30 - 14:55 at Auditorium, Vertex Building - Implementation Chair(s): Tobias Wrigstad

When written idiomatically in most programming languages, programs that traverse and construct trees operate over pointer-based data structures, with one heap object per-leaf and node. While this may seem tautological, we show that common tree traversals—found in compiler passes, space-partitioning trees, and elsewhere—can instead be automatically compiled to operate on pointer-free pre-order serializations of trees. On current x86 architectures such programs can run up to several times faster than their pointer-based counterparts.

We present a prototype compiler for a small first-order, purely functional language of tree traversals. The output language includes mutable cursors into input and output buffers for packed data. We propose a compilation technique with an effect system for capturing traversal behavior, combined with a lightweight analysis inferring data flow, and a program synthesis step for creating missing traversals.

Thu 22 Jun

ecoop-2017-papers
13:40 - 15:20: ECOOP Research Papers - Implementation at Auditorium, Vertex Building
Chair(s): Tobias WrigstadUppsala University
ecoop-2017-papers13:40 - 14:05
Talk
Todd A. Anderson, Hai LiuIntel Labs, Lindsey KuperIntel Labs, Ehsan TotoniIntel Labs, Jan VitekNortheastern University, Tatiana ShpeismanIntel Labs
Link to publication Media Attached
ecoop-2017-papers14:05 - 14:30
Talk
Baptiste Saleil, Marc FeeleyUniversité de Montréal
Link to publication Media Attached
ecoop-2017-papers14:30 - 14:55
Talk
Michael VollmerIndiana University, USA, Sarah SpallIndiana University, Buddhika ChamithIndiana University, Laith Sakka, Milind KulkarniPurdue University, Sam Tobin-HochstadtIndiana University, Ryan R. NewtonIndiana University
Link to publication Media Attached
ecoop-2017-papers14:55 - 15:20
Talk
Yudi ZhengUniversity of Lugano, Lubomír BulejCharles University, Walter BinderUniversity of Lugano
Link to publication Media Attached