Garbage collection and local variable type-precision and liveness in Java virtual machines

Abstract. Full precision in garbage collection implies retaining only those heap allocated objects that will actually be used in the fu-ture. Since full precision is not computable in general, garbage col-lectors use safe (i.e., conservative) approximations such as reach-ability from a set of root references. Ambiguous roots collectors (commonly called “conservative”) can be overly conservative be-cause they overestimate the root set, and thereby retain unexpect-edly large amounts of garbage. We consider two more precise col-lection schemes for Java virtual machines (JVMs). One uses a type analysis to obtain a type-precise root set (only those variables that contain references); the other adds a live variable analysis to reduce the root set to only the live reference variables. Even with the Java programming language’s strong typing, it turns out that the JVM specification has a feature that makes type-precise root sets difficult to compute. We explain the problem and ways in which it can be solved. Our experimental results include measurements of the costs of the type and liveness analyses at load time, of the incremental ben-efits at run time of the liveness analysis over the type analysis alone, and of various map sizes and counts. We find that the liveness anal-ysis often produces little or no improvement in heap size, some-times modest improvements, and occasionally the improvement is dramatic. While further study is in order, we conclude that the main benefit of the liveness analysis is preventing bad surprises.