Liveness-Based Garbage Collection

Current garbage collectors leave much heap-allocated data uncollected because they preserve data reachable from a root set. However, only live data—a subset of reachable data—need be preserved.  We formulate a context-sensitive liveness analysis for structured data and prove it correct. We then use a 0-CFA-like conservative approximation to annotate each allocation and function-call program point with a finite-state automaton—which the garbage collector inspects to curtail reachability during marking. As a result, fewer objects are marked (albeit with a more expensive marker) and then preserved (e.g. by a copy phase). Experiments confirm the expected performance benefits—increase in garbage reclaimed and a consequent decrease in the number of collections, a decrease in the memory size required to run programs, and reduced overall garbage collection time for a majority of programs (work done with  Prasanna K (IITB), Rahul Asati (IITB), Amitabha Sanyal (IITB), and Alan Mycroft(University of Cambridge)).

Bio: Dr Amey Karkare completed his PhD from IIT Bombay in 2009, and his B.Tech. from IIT Kanpur in 1998. His areas of interest include Intelligent Tutoring Systems, Program Analysis, Compiler Optimizations, and Functional Programming. He has more than 7 years of industrial experience most of which is in the area of Compiler Optimizations. He is an Assistant Professor and P K Kelkar Research Fellow in the department of CSE at IIT Kanpur.  He is currently visiting Dept of CSE, IIT Bombay (until Dec 2016).