Incremental garbage collection without tags

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Garbage collection algorithms that do not require tagging of data have been around since the early days of LISP. With the emergence of strongly-typed languages that require heap allocation, interest in tag-free garbage collection has increased. Several papers published recently describe methods for performing tag-free copying garbage collection by retaining compile-time type information at run time. However, all of these algorithms have the “stop and collect” property, in which program execution is suspended for a significant amount of time during garbage collection. For many programs an incremental garbage collection method, in which the garbage collection overhead is spread evenly throughout the computation, is desirable. Methods for incremental copying garbage collection have been around since the 1970's. However, these algorithms (the most notable of which is Baker's algorithm) rely on tagged data. In this paper, we present a method for performing incremental copying garbage collection without tags. We then extend this method to work for polymorphically typed languages, and to provide breadth-first copying for improved performance and data locality.

Original languageEnglish (US)
Title of host publicationESOP 1992 - 4th European Symposium on Programming, Proceedings
EditorsBernd Krieg-Bruckner
PublisherSpringer Verlag
Pages200-218
Number of pages19
ISBN (Print)9783540552536
DOIs
StatePublished - 1992
Event4th European Symposium on Programming, ESOP 1992 held jointly with 17th Colloquium on Trees in Algebra and Programming, CAAP 1992 - Rennes, France
Duration: Feb 26 1992Feb 28 1992

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume582 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other4th European Symposium on Programming, ESOP 1992 held jointly with 17th Colloquium on Trees in Algebra and Programming, CAAP 1992
CountryFrance
CityRennes
Period2/26/922/28/92

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Incremental garbage collection without tags'. Together they form a unique fingerprint.

Cite this