Projects per year
Abstract
Abstract garbage collection is the application of garbage collection to an abstract interpreter. Existing work has shown that abstract garbage collection can improve both the interpreter’s precision and performance. Current approaches rely on heuristics to decide when to apply abstract garbage collection. Garbage will build up and impact precision and performance when the collection is applied infrequently, while too frequent applications will bring about their own performance overhead. A balance between these tradeoffs is often difficult to strike.
We propose a new approach to cope with the buildup of garbage in the results of an abstract interpreter. Our approach is able to eliminate all garbage, therefore obtaining the maximum precision and performance benefits of abstract garbage collection. At the same time, our approach does not require frequent heap traversals, and therefore adds little to the interpreters’s running time. The core of our approach uses reference counting to detect and eliminate garbage as soon as it arises. However, reference counting cannot deal with cycles, and we show that cycles are much more common in an abstract interpreter than in its concrete counterpart. To alleviate this problem, our approach detects cycles and employs reference counting at the level of strongly connected components. While this technique in general works for any system that uses reference counting, we argue that it works particularly well for an abstract interpreter. In fact, we show formally that for the continuation store, where most of the cycles occur, the cycle detection technique only requires O(1) amortized operations per continuation push.
We present our approach formally, and provide a proof-of-concept implementation in the Scala-AM framework. We empirically show our approach achieves both the optimal precision and significantly better performance compared to existing approaches to abstract garbage collection.
We propose a new approach to cope with the buildup of garbage in the results of an abstract interpreter. Our approach is able to eliminate all garbage, therefore obtaining the maximum precision and performance benefits of abstract garbage collection. At the same time, our approach does not require frequent heap traversals, and therefore adds little to the interpreters’s running time. The core of our approach uses reference counting to detect and eliminate garbage as soon as it arises. However, reference counting cannot deal with cycles, and we show that cycles are much more common in an abstract interpreter than in its concrete counterpart. To alleviate this problem, our approach detects cycles and employs reference counting at the level of strongly connected components. While this technique in general works for any system that uses reference counting, we argue that it works particularly well for an abstract interpreter. In fact, we show formally that for the continuation store, where most of the cycles occur, the cycle detection technique only requires O(1) amortized operations per continuation push.
We present our approach formally, and provide a proof-of-concept implementation in the Scala-AM framework. We empirically show our approach achieves both the optimal precision and significantly better performance compared to existing approaches to abstract garbage collection.
Original language | English |
---|---|
Title of host publication | Proceedings of the 33rd European Conference on Object-Oriented Programming (ECOOP 2019) |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Number of pages | 34 |
Volume | 134 |
ISBN (Electronic) | 9783959771115 |
ISBN (Print) | 978-3-95977-111-5 |
DOIs | |
Publication status | Published - 1 Jul 2019 |
Event | European Conference on Object-Oriented Programming (ECOOP 2019) - Hammersmith, London, United Kingdom Duration: 17 Jul 2019 → 18 Jul 2019 https://2019.ecoop.org |
Conference
Conference | European Conference on Object-Oriented Programming (ECOOP 2019) |
---|---|
Abbreviated title | ECOOP2019 |
Country | United Kingdom |
City | London |
Period | 17/07/19 → 18/07/19 |
Internet address |
Keywords
- abstract interpretation
- static analysis
- reference counting
- garbage collection
Fingerprint
Dive into the research topics of 'Garbage-free Abstract Interpretation through Abstract Reference Counting'. Together they form a unique fingerprint.-
SRP52: SRP-Onderzoekszwaartepunt: Foundations for Reliable Multi-Paradigm Network-Centric Programming
De Meuter, W., De Roover, C. & Gonzalez Boix, E.
1/03/19 → 29/02/24
Project: Fundamental
-
FWOTM867: Adaptive analysis for multi-paradigm programs through reflection
1/10/17 → 30/09/21
Project: Fundamental
-
Garbage-free Abstract Interpretation through Abstract Reference Counting (Artifact)
Van Es, N., Stiévenart, Q. & De Roover, C., 2019Research output: Non-textual form › Artefact
Open Access -
Garbage-free Abstract Interpretation through Abstract Reference Counting (Poster)
Van Es, N., Stiévenart, Q. & De Roover, C., 2019.Research output: Unpublished contribution to conference › Poster
Open AccessFile
Activities
- 1 Talk or presentation at a conference
-
Garbage-Free Abstract Interpretation through Abstract Reference Counting
Noah Van Es (Speaker)
17 Jul 2019Activity: Talk or presentation › Talk or presentation at a conference