SPLASH 2022
Mon 5 - Sat 10 December 2022 Auckland, New Zealand
Wed 7 Dec 2022 11:15 - 11:37 at Seminar Room G100 - GPCE Session 2 Chair(s): Atsushi Igarashi

One of the performance bottlenecks of nested recursive computations is the intermediate collections created at different levels of recursion. The existing techniques such as vertical and horizontal loop fusion do not remove such intermediate allocations. This paper proposes deep fusion, a technique for the efficient compilation of nested recursive computation over collections. The input to our compilation framework is a high-level functional program that can represent computations on flat and nested collections such as lists, sets, bags, and maps. The intermediate collections are removed in three levels. First, the immutable collections are translated into mutable ones by leveraging in-place updates using the destination-passing style technique. Second, deep fusion enables the inner level of recursion to reuse the destinations of the outer levels for in-place updates. Third, deep fusion removes the need to allocate tiny intermediate collections at different depths of recursion. Our experiments show that deep fusion can improve the performance of nested recursion over nested lists and maps.

Wed 7 Dec

Displayed time zone: Auckland, Wellington change

10:30 - 12:00
GPCE Session 2GPCE at Seminar Room G100
Chair(s): Atsushi Igarashi Kyoto University
10:30
22m
Talk
Incremental Processing of Structured Data in DatalogVirtual
GPCE
André Pacak JGU Mainz, Tamás Szabó GitHub, Sebastian Erdweg JGU Mainz
DOI
10:52
22m
Talk
Data Types as a More Ergonomic Frontend for Grammar-Guided Genetic ProgrammingVirtual
GPCE
Guilherme Espada University of Lisbon, Leon Ingelse University of Lisbon, Paulo Canelas University of Lisbon; Carnegie Mellon University, Pedro Barbosa University of Lisbon; Instituto de Medicina Molecular, Alcides Fonseca University of Lisbon
DOI
11:15
22m
Talk
Deep Fusion for Efficient Nested Recursive ComputationsVirtual
GPCE
Amir Shaikhha University of Edinburgh
DOI
11:37
22m
Talk
Composable Sequence Macros for Fast IterationVirtual
GPCE
Anna Bolotina Czech Technical University in Prague, Ryan Culpepper Czech Technical University in Prague
DOI