Bounding space usage of conservative garbage collectors

ABSTRACT

Conservative garbage collectors can automatically reclaim unused memory in the absence of precise pointer location information. If a location can possibly contain a pointer, it is treated by the collector as though it contained a pointer. Although it is commonly assumed that this can lead to unbounded space use due to misidentified pointers, such extreme space use is rarely observed in practice, and then generally only if the number of misidentified pointers is itself unbounded.We show that if the program manipulates only data structures satisfying a simple GC-robustness criterion, then a bounded number of misidentified pointers can at most result in increasing space usage by a constant factor. We argue that nearly all common data structures are already GC-robust, and it is typically easy to identify and replace those that are not. Thus it becomes feasible to prove space bounds on programs collected by mildly conservative garbage collectors, such as the one in [2]. The worst-case space overhead introduced by such mild conservatism is comparable to the worst-case fragmentation overhead for inherent in any non-moving storage allocator.The same GC-robustness criterion also ensures the absence of temporary space leaks of the kind discussed in [13] for generational garbage collectors.

REFERENCES

• 1: Andrew W. Appel, Compiling with continuations, Cambridge University Press, New York, NY, 1992
• 2: K. Barabash, , N. Buchbinder, T. Domani, B. K. Kolodner, Y. Ossia, S. S. Pinter, J. Shepherd, R. Sivan, and V. Umansky. Mostly accurate stack scanning. In Proceedings of the Usenix Java Virtual Machine gesearvh and Technology Symposium, April 2001.
• 3: J. F. Bartlett. Compacting garbage collection with ambiguous roots. Lisp Pointers, pages 3-12, April-June 1988.
• 4: Hans-Juergen Boehm, Space efficient conservative garbage collection, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.197-206, June 21-25, 1993, Albuquerque, New Mexico, United States
• 5: D. R. Chase, Safety consideration for storage allocation optimizations, Proceedings of the ACM SIGPLAN 1988 conference on Programming Language design and Implementation, p.1-10, June 20-24, 1988, Atlanta, Georgia, United States
• 6: William D. Clinger, Proper tail recursion and space efficiency, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.174-185, June 17-19, 1998, Montreal, Quebec, Canada
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: Martin Hirzel , Amer Diwan, On the type accuracy of garbage collection, Proceedings of the 2nd international symposium on Memory management, p.1-11, October 15-16, 2000, Minneapolis, Minnesota, United States
• 9: Richard L. Hudson , J. Eliot B. Moss, Incremental Collection of Mature Objects, Proceedings of the International Workshop on Memory Management, p.388-403, September 17-19, 1992
• 10: Sheng Liang, Java Native Interface: Programmer's Guide and Reference, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 11: J. M. Robson, An Estimate of the Store Size Necessary for Dynamic Storage Allocation, Journal of the ACM (JACM), v.18 n.3, p.416-423, July 1971 [doi>10.1145/321650.321658]
• 12: J. M. Robson, Bounds for Some Functions Concerning Dynamic Storage Allocation, Journal of the ACM (JACM), v.21 n.3, p.491-499, July 1974 [doi>10.1145/321832.321846]
• 13: Niklas Röjemo, Generational Garbage Collection without Temporary Space Leaks for Lazy Functional Languages, Proceedings of the International Workshop on Memory Management, p.145-162, September 27-29, 1995
• 14: Manuel Serrano , Hans-J. Boehm, Understanding memory allocation of scheme programs, Proceedings of the fifth ACM SIGPLAN international conference on Functional programming, p.245-256, September 2000
• 15: M. Weiser , A. Demers , C. Hauser, The portable common runtime approach to interoperability, Proceedings of the twelfth ACM symposium on Operating systems principles, p.114-122, November 1989
• 16: E. P. Wentworth, Pitfalls of conservation garbage collection, Software—Practice & Experience, v.20 n.7, p.719-727, July 1990 [doi>10.1002/spe.4380200707]