Combining card marking with remembered sets: how to save scanning time
Abstract
We consider the combination of card marking with remembered sets for generational garbage collection as suggested by Hosking and Hudson [3]. When more than two generations are used, a naive implementation may cause excessive and wasteful scanning of the cards and thus increase the collection time. We offer a simple data structure and a corresponding algorithm to keep track of which cards need be scanned for which generation. We then extend these ideas for the Train Algorithm of [4]. Here, the solution is more involved, and allows tracking of which card should be scanned for which car-collection in the train.
References
[1]
R. E. Jones and R. D. Lins. Garbage Collection: Algorithms for Automatic Dynamic Memory Management. John Wiley & Sons, July 1996.
[2]
U. HSlzle. A fast write barrier for generational garbage collectors. In Eliot Moss, Paul R. Wilson, and Benjamin Zorn, editors. OOPSLA/ECOOP '93 Workshop on Garbage Collection in Object-Oriented Systems, October 1993
[3]
A. L. Hosking and R. L. Hudson. Remembered Sets Can Also Play Cards. In OOPSLA'93 Workshop on Garbage Collection and Memory Management. Washington, DC, September 1993.
[4]
R. L. Hudson and J. E. B. Moss. Incremental garbage collection for mature objects. In Yves Bekkers and Jacques Cohen, editors. Proceedings of International Workshop on Memory Management, volume 637 of Lecture Notes in Computer Science, 1992. Springer-Verlag.
[5]
H. Lieberman and C. E. Hewitt. A Real Time Garbage Collector Based on the Lifetimes of Objects. Communications of the A CM, 26(6), pages 419-429, 1983.
[6]
J. Seligmann and S. Grarup. Incremental mature garbage collection using the train algorithm. In O. Nierstras, editor. Proceedings of 1995 European Conference on Object-Oriented Programming, Lecture Notes in Computer Science.Springer- Verlag, August 1995.
[7]
Patrick SobaNarro. A lifetimebased garbage collector for Lisp systems on general-purpose computers. Technical Report AITR-1417, MIT, AI Lab, February 1988.
[8]
D. Ungar. Generation Scavenging: A Non-disruptiw~ High Performance Storage Reclamation Algorithm. Proceedings of the A CM Symposium on Practical Software Development Environments, ACM SIG- PLAN Notices Vol. 19, No. 5, May 1984, pp. 157-167.
[9]
Paul R. Wilson. Uniprocessor garbage collection techniques. In Yves Bekkers and Jacques Cohen, editors. Proceedings of International Workshop on Memory Management, volume 637 of Lecture Notes in Computer Science, 1992. Springer-Verlag.
[10]
P. R. Wilson and T. G. Moher. A cardmarking scheme for controlling intergenerational references in generation-based garbage collection on stock hardware. A CM SIGPLAN Notices, 24(5):87-92, 1989.
Index Terms
- Combining card marking with remembered sets: how to save scanning time
Recommendations
Combining card marking with remembered sets: how to save scanning time
ISMM '98: Proceedings of the 1st international symposium on Memory managementWe consider the combination of card marking with remembered sets for generational garbage collection as suggested by Hosking and Hudson [3]. When more than two generations are used, a naive implementation may cause excessive and wasteful scanning of the ...
A generational on-the-fly garbage collector for Java
PLDI '00: Proceedings of the ACM SIGPLAN 2000 conference on Programming language design and implementationAn on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
A generational on-the-fly garbage collector for Java
An on-the-fly garbage collector does not stop the program threads to perform the collection. Instead, the collector executes in a separate thread (or process) in parallel to the program. On-the-fly collectors are useful for multi-threaded applications ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
March 1999
195 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/301589
- Chairmen:
- Simon Peyton Jones,
- Richard Jones
Copyright © 1998 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 01 October 1998
Published in SIGPLAN Volume 34, Issue 3
Check for updates
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations31Total Citations
- 615Total Downloads
- Downloads (Last 12 months)101
- Downloads (Last 6 weeks)16
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in