David A. Barrett
ABSTRACT
Generational techniques have been very successful in reducing the impact of garbage collection algorithms upon the performance of programs. However, all generational algorithms occasionally promote objects that later become garbage, resulting in an accumulation of garbage in older generations. Reclaiming this tenured garbage without resorting to collecting the entire heap is a difficult problem. In this paper, we describe a mechanism that extends existing generational collection algorithms by allowing them to reclaim tenured garbage more effectively. In particular, our dynamic threatening boundary mechanism divides memory into two spaces, one for shortlived, and another for long-lived objects. Unlike previous work, our collection mechanism can dynamically adjust the boundary between these two spaces either forward or backward in time, essentially allowing data to become untenured. We describe an implementation of the dynamic threatening boundary mechanism and quantify its associated costs. We also describe a policy for setting the threatening boundary and evaluate its performance relative to existing generational collection algorithms. Our results show that a policy that uses the dynamic threatening boundary mechanism is effective at reclaiming tenured garbage.
- 1.Apple Computer Inc. Macintosh Common Lisp Reference, version 2 edition, 1992. pages 631-637.Google Scholar
- 2.David A. Barrett and Benjamin G. Zom. Using lifetime predictors to improve memory allocation performance. In ACM SIGPLAN Symposium on Programming Lan. guage Design and Implementation, pages 187-196, Albuquerque, New Mexico, June 1993. Google ScholarDigital Library
- 3.H. Boehm and M. Weiser. Garbage collection in an uncooperative environment. Software Practice and Experience, pages 807-820, September 1988. Google ScholarDigital Library
- 4.Hans-J. Boehm, Alan J. Demers, and Scott Shenker. Mostly parallel garbage collection. In ACM SIGPLAN Symposium on Programming Language Design and Implementation, pages 157-164, June 1991. Toronto, Ontario, Canada. Google ScholarDigital Library
- 5.Patrick Caudill and Allen Wirfs-Brock. A third generation Smalltalk-80 implementation. In Normam Meyrowitz, editor, OOPSLA'86 Conference Proceedings, pages 119-130, Portland, OR, September 1986. ACM. Google ScholarDigital Library
- 6.Alan Demers, Mark Weiser, Barry Hayes, Hans Boetam, Daniel Bobrow, and Scott Shenker. Combining generational and conservative garbage collection: Framework and implementations. In Conference Record of the Sev. enteenth ACM Symposium on Principles of Programming Languages, pages 261-269, January 1990. Google ScholarDigital Library
- 7.David Detlefs, A1 Dosser, and Benjamin Zorn. Memory allocation costs in large C and C++ programs. Software Practice and Experience, 24(6):527-542, June 1994. Google ScholarDigital Library
- 8.Digital Equipment Corporation. ATOM Reference Manual, December 1993.Google Scholar
- 9.Fmnz Inc. Allegro CL User Guide, Version 4.1, revision 2 edition, March 1992. Chapter 15: Garbage Collection.Google Scholar
- 10.Barry Hayes. Using key object opportunism to collect old objects. In ACM SIGPLAN 1991 Conference on Object Oriented Programming Systems, Languages and Applications (OOPSLA '91), pages 33-46, Phoenix, Arizona, October 1991. ACM Press. Google ScholarDigital Library
- 11.Antony L. Hosking and Richard L. Hudson. Remembered sets can also play cards. In OOPSLA'93 Workshop on Garbage Collection in Object-Oriented Systems, Washington, D.C., September 1993.Google Scholar
- 12.R. L. Hudson, J. E. B. Moss, and A. Diwan. A language independent garbage collector toolkit. Technical Report COINS TR 91-47, University of Massachusetts, Amherst, MA, September 1991. Google ScholarDigital Library
- 13.Richard L. Hudson and J. Eliot B. Moss. Incremental collection of mature objects. In Proceedings of the International Workshop on Memory Management, pages 388-403, St. Malo, France, September 1992. Springer- Verlag Lecture Notes in Computer Science vol. 637. Google ScholarDigital Library
- 14.Henry Lieberman and Carl Hewitt. A real-time garbage collector based on the lifetimes of objects. Communications of the ACM, 26(6):419-429, June 1983. Google ScholarDigital Library
- 15.David A. Moon. Garbage collection in a large Lisp system. In Conference Record of the 1984 ACM Symposium on LISP and Functional Programming, pages 235-246, Austin, Texas, August 1984. Google ScholarDigital Library
- 16.David Ungar. Generation scavenging: A non-disruptive high performance storage reclamation algorithm. In SIG- SOFT/SIGPLAN Practical Programming Environments Conference, pages 157-167, April 1984. Google ScholarDigital Library
- 17.David Ungar and Frank Jackson. An adaptive tenuring policy for generation scavengers. A CM Transactions on Programming Languages and Systems, 14(i ): 1-27, January 1992. Google ScholarDigital Library
- 18.Mark D. Weiser, Alan J. Demers, Daniel G. Bobrow, and Barry Hayes. Method ancl system for reclaiming unreferenced computer memory space. United States Patent No. 5,321,834, June 1994.Google Scholar
- 19.Paul R. Wilson and Thomas G. Moher. Design of the opportunistic garbage collector. In ACM SIGPLAN 1989 Conference on Object Oriented Programming Systems, Languages and Applications (OOPSLA '89), pages 23- 35, New Orleans, Louisiana, October 1989. Google ScholarDigital Library
- 20.Benjamin Zorn. Comparing mark-and-sweep and stopand-copy garbage collection. In 1990 ACM Conference on Lisp and Functional Programming, pages 87-98, Nice, France, June 1990. Google ScholarDigital Library
- 21.Benjamin Zorn and Dirk Grunwald. Empirical measurements of six allocation-intensive C programs. ACM SIG- PLAN Notices, 27(12):71-80, December 1992. Google ScholarDigital Library
Index Terms
- Garbage collection using a dynamic threatening boundary
Recommendations
Garbage collection using a dynamic threatening boundary
Generational techniques have been very successful in reducing the impact of garbage collection algorithms upon the performance of programs. However, all generational algorithms occasionally promote objects that later become garbage, resulting in an ...
Age-based garbage collection
Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsModern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Comments