Trustworthy Systems


Eliot Moss, University of Massachusetts at Amherst

Prospects for Optimal Program-Specific Garbage Collection


For several years we have been engaging this question: Can machine learning methods enable us to construct optimal or nearly optimal program-specific strategies for when to invoke the garbage collection? We have been working in the context of Java programs and in this talk will report in some detail on our after-the-fact analysis of program executions to determine what would have been an optimal set of times at which to collect. Here optimality is with respect to a simple, but reasonable cost model: number of bytes copied / examined by the collector.

Last June we reported optimal results for this for non-generational collection (a dynamic programming problem) and approximately optimal results for generational collection in a Distinguished Paper at PLDI 2016. Since then we have developed an algorithm to compute optimal results for generational collection, using an interesting reframed (but equivalent) cost model. We also have empirical results comparing that optimal cost with a lower bound on it that is cheaper to compute, and also an upper bound similarly cheap to compute, which show that these bounds appear to be tight in practice.

We will cover both the previous and new results on optimal GC schedules (after the fact analysis). We will further discuss our approach to applying machine learning to this problem and the challenges we face in that endeavor. Our co-authors in this line of work are Ben Marlin, Nick Jacek, and Meng Shieh ("Joe") Chiu, and it has been supported by the US National Science Foundation.


Eliot Moss received his undergraduate and graduate degrees from the Massachusetts Institute of Technology, culminating in a Ph.D. in computer science in 1981, on the subject of nested transactions. He served in the U.S. Army until 1985 when he joined the faculty of the Department of Computer Science (now the College of Information and Computer Sciences), University of Massachusetts Amherst, where he now holds the rank of Professor. He co-directs the Architecture and Language Implementation Laboratory. Dr. Moss's research focuses on efficient implementation of modern and emerging language features on modern and future hardware. He is particularly well-known for his work on garbage collection and on transactions and transactional memory. He is a Fellow of the ACM and of the IEEE, a co-recipient of the Dijkstra Prize in Distributed Computing in 2012, and the SOSP Hall of Fame award in 2015.