Tag-free garbage collection for strongly typed programming languages

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

Abstract

With the emergence of a number of strongly typed languages with very dynamic storage allocation, efficient methods of storage reclamation have become especially important. Even though no type tags are required for type checking programs written in these languages, current implementations do use tags to support run time garbage collection. This often inflicts a high time and space overhead on program execution. Since the early days of LISP (and Algol68 later on), there have been schemes for performing tag-free garbage collection. In this paper, we describe an improvement of existing methods that leads to more effective storage reclamation in the absence of tags. Garbage collection has also traditionally been viewed as being independent of the particular program being executed. This means that results of compile-time analyses which could increase the effectiveness of garbage collection cannot be incorporated easily into the garbage collection process. This paper describes a method for performing garbage collection 1) in the absence of tagged data, and 2) using compile-time information. This method relies on compiler-generated garbage collection routines specific to the program being executed and incurs no time overhead during execution other then the cost of the garbage collection process itself. We describe tag-free garbage collection methods for monomorphically typed and polymorphically typed languages, and suggest how they might be extended to support parallel languages.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
PublisherAssociation for Computing Machinery
Pages165-176
Number of pages12
ISBN (Print)0897914287
DOIs
StatePublished - May 1 1991
Event1991 ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation, PLDI 1991 - Ottawa, Canada
Duration: Jun 24 1991Jun 28 1991

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

Other

Other1991 ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation, PLDI 1991
CountryCanada
CityOttawa
Period6/24/916/28/91

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Tag-free garbage collection for strongly typed programming languages'. Together they form a unique fingerprint.

  • Cite this

    Goldberg, B. (1991). Tag-free garbage collection for strongly typed programming languages. In Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI) (pp. 165-176). (Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)). Association for Computing Machinery. https://doi.org/10.1145/113445.113460