The recently introduced Perceus algorithm can automatically insert reference count instructions such that the resulting (cycle-free) program is garbage free: objects are freed at the very moment they can no longer be referenced. An important extension is reuse analysis. This optimization pairs objects of known size with fresh allocations of the same size and tries to reuse the object in-place at runtime if it happens to be unique. Unfortunately, current implementations of reuse analysis are fragile with respect to small program transformations, or can cause an arbitrary increase in the peak heap usage. We present a novel drop-guided reuse algorithm that is simpler and more robust than previous approaches. Moreover, we generalize the linear resource calculus to precisely characterize garbage-free and frame-limited evaluations. On each function call, a frame-limited evaluation may hold on to memory longer if the size is bounded by a constant factor. Using this framework we show that our drop-guided reuse is frame-limited and find that an implementation of our new reuse approach in Koka can provide significant speedups.
Mon 12 SepDisplayed time zone: Belgrade, Bratislava, Budapest, Ljubljana, Prague change
13:40 - 15:20 | Analysis and TransformationsICFP Papers and Events at Linhart Chair(s): Malgorzata Biernacka University of Wrocław | ||
13:40 20mTalk | Reference Counting with Frame Limited Reuse ICFP Papers and Events DOI | ||
14:00 20mTalk | Entanglement Detection With Near-Zero CostDistinguished Paper ICFP Papers and Events Sam Westrick Carnegie Mellon University, Jatin Arora Carnegie Mellon University, Umut A. Acar Carnegie Mellon University DOI | ||
14:20 20mTalk | Generating circuits with generators ICFP Papers and Events Marek Materzok University of Wroclaw DOI | ||
14:40 20mTalk | Staged Compilation With Two-Level Type Theory ICFP Papers and Events András Kovács Eötvös Loránd University DOI | ||
15:00 20mTalk | Random Testing of a Higher-Order Blockchain LanguageExperience Report ICFP Papers and Events Tram Hoang National University of Singapore, Anton Trunov Zilliqa Research, Leonidas Lampropoulos University of Maryland, College Park, Ilya Sergey National University of Singapore DOI Pre-print |