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

Displayed time zone: Amsterdam, Berlin, Bern, Rome, Stockholm, Vienna change

13:40 - 15:20
ImplementationECOOP Research Papers at Auditorium, Vertex Building
Chair(s): Tobias Wrigstad Uppsala University
13:40
25m
Talk
Parallelizing Julia with a Non-invasive DSL
ECOOP Research Papers
Todd A. Anderson , Hai Liu Intel Labs, Lindsey Kuper Intel Labs, Ehsan Totoni Intel Labs, Jan Vitek Northeastern University, Tatiana Shpeisman Intel Labs
Link to publication Media Attached
14:05
25m
Talk
Interprocedural Specialization of Higher-Order Dynamic Languages Without Static Analysis
ECOOP Research Papers
Baptiste Saleil , Marc Feeley Université de Montréal
Link to publication Media Attached
14:30
25m
Talk
Compiling tree transforms to operate on packed representations
ECOOP Research Papers
Michael Vollmer Indiana University, USA, Sarah Spall Indiana University, Buddhika Chamith Indiana University, Laith Sakka , Milind Kulkarni Purdue University, Sam Tobin-Hochstadt Indiana University, Ryan R. Newton Indiana University
Link to publication Media Attached
14:55
25m
Talk
An Empirical Study on Deoptimization in the Graal Compiler
ECOOP Research Papers
Yudi Zheng University of Lugano, Lubomír Bulej Charles University, Walter Binder University of Lugano
Link to publication Media Attached