TY - GEN
T1 - Incremental garbage collection without tags
AU - Goldberg, Benjamin
N1 - Funding Information:
1. Author's address: 251 Mercer Street, New York, NY 10012, USA. Email: goldberg@es.nyu.edu.T his research has been supported, in part, by the National Science Foundation (#CCR-8909634) and DARPA (DARPA/ONR #N00014-91-J1472).
Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 1992.
PY - 1992
Y1 - 1992
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85029495346&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85029495346&partnerID=8YFLogxK
U2 - 10.1007/3-540-55253-7_12
DO - 10.1007/3-540-55253-7_12
M3 - Conference contribution
AN - SCOPUS:85029495346
SN - 9783540552536
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 200
EP - 218
BT - ESOP 1992 - 4th European Symposium on Programming, Proceedings
A2 - Krieg-Bruckner, Bernd
PB - Springer Verlag
T2 - 4th European Symposium on Programming, ESOP 1992 held jointly with 17th Colloquium on Trees in Algebra and Programming, CAAP 1992
Y2 - 26 February 1992 through 28 February 1992
ER -