Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Linear-Mark: Locality vs. Accuracy in Mark-Sweep Garbage Collection
event speaker icon
Chiara Meiohas (M.Sc. Thesis Seminar)
event date icon
Sunday, 10.09.2023, 10:00
event location icon
Zoom Lecture: 2945058890 and Taub 401
event speaker icon
Advisor: Prof. Erez Petrank
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.