Linear-Mark: Locality vs. Accuracy in Mark-Sweep Garbage Collection
Open Access
- 2 October 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1-12
Abstract
Tracing garbage collectors are widely deployed in modern programming languages. But tracing an arbitrary heap shape incurs poor locality and may hinder scalability. In this paper, we explore an avenue for mitigating these inefficiencies at the expense of conservative, less accurate identification of live objects. We do this by proposing and studying an alternative to the Mark-Sweep tracing algorithm, called Linear-Mark. It turns out that although Linear-Mark improves locality and scalability, the accuracy of Mark-Sweep outweighs the achieved enhancements. We present the Linear-Mark garbage-collecting algorithm and provide an evaluation that highlights the trade-offs between the Linear-Mark and the Mark-Sweep approaches. Our hope is that this research will inspire further algorithmic improvements, ultimately leading to better garbage collection algorithms.Keywords
This publication has 22 references indexed in Scilit:
- Tracing garbage collection on highly parallel platformsACM SIGPLAN Notices, 2010
- Limits of parallel marking garbage collection2008
- ImmixACM SIGPLAN Notices, 2008
- Effective prefetch for mark-sweep garbage collection2007
- The DaCapo benchmarks2006
- Mark and split2006
- An on-the-fly reference-counting garbage collector for javaACM Transactions on Programming Languages and Systems, 2006
- Garbage-first garbage collection2004
- Myths and realitiesACM SIGMETRICS Performance Evaluation Review, 2004
- A semi‐incremental garbage collection algorithmSoftware: Practice and Experience, 1982