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
Times are displayed in time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

13:40 - 15:20: ImplementationECOOP Research Papers at Auditorium, Vertex Building
Chair(s): Tobias WrigstadUppsala University
13:40 - 14:05
Talk
ECOOP Research Papers
Todd A. Anderson, Hai LiuIntel Labs, Lindsey KuperIntel Labs, Ehsan TotoniIntel Labs, Jan VitekNortheastern University, Tatiana ShpeismanIntel Labs
Link to publication Media Attached
14:05 - 14:30
Talk
ECOOP Research Papers
Baptiste Saleil, Marc FeeleyUniversité de Montréal
Link to publication Media Attached
14:30 - 14:55
Talk
ECOOP Research Papers
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
14:55 - 15:20
Talk
ECOOP Research Papers
Yudi ZhengUniversity of Lugano, Lubomír BulejCharles University, Walter BinderUniversity of Lugano
Link to publication Media Attached