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: Richard Jones , Rafael Lins, Garbage collection: algorithms for automatic dynamic memory management, John Wiley & Sons, Inc., New York, NY, 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: 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
• 5: Henry Lieberman , Carl Hewitt, A real-time garbage collector based on the lifetimes of objects, Communications of the ACM, v.26 n.6, p.419-429, June 1983 [doi>10.1145/358141.358147]
• 6: Jacob Seligmann , Steffen Grarup, Incremental Mature Garbage Collection Using the Train Algorithm, Proceedings of the 9th European Conference on Object-Oriented Programming, p.235-252, August 07-11, 1995
• 7: Patrick Sobalvarro, A Lifetime-based Garbage Collector for LISP Systems on General- Purpose Computers, Massachusetts Institute of Technology, Cambridge, MA, 1988
• 8: David Ungar, Generation Scavenging: A non-disruptive high performance storage reclamation algorithm, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.157-167, April 1984
• 9: Paul R. Wilson, Uniprocessor Garbage Collection Techniques, Proceedings of the International Workshop on Memory Management, p.1-42, September 17-19, 1992
• 10: P. R. Wilson , T. G. Moher, A “card-marking” scheme for controlling intergenerational references in generation-based garbage collection on stock hardware, ACM SIGPLAN Notices, v.24 n.5, p.87-92, May 1989 [doi>10.1145/66068.66077]

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Garbage collection

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Data types and structures

  G. Mathematics of Computing
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Algorithm design and analysis

General Terms:
Algorithms, Design, Languages, Performance, Theory

Keywords:
garbage collection, generational garbage collection, the train algorithm