A note on compacting garbage collection

John P Fitch, A C Norman

Research output: Contribution to journalArticle

Abstract

A variation of the Haddon and Waite compacting garbage collector is presented that needs only bounded workspace, but which has typical runtime proportional to the size of the heap rather than n log n for a heap of size n. The algorithm has been measured in the context of a LISP system where it has been seen to behave close to its optimum. The relationship of this algorithm to one due to Lang and Weigbreit is also explained.
LanguageEnglish
Pages31-34
Number of pages4
JournalThe Computer Journal
Volume21
Issue number1
DOIs
StatusPublished - 1977

Cite this

A note on compacting garbage collection. / Fitch, John P; Norman, A C.

In: The Computer Journal, Vol. 21, No. 1, 1977, p. 31-34.

Research output: Contribution to journalArticle

Fitch, John P ; Norman, A C. / A note on compacting garbage collection. In: The Computer Journal. 1977 ; Vol. 21, No. 1. pp. 31-34.
@article{1fac1daaa55f483cb0052ba0efb796d5,
title = "A note on compacting garbage collection",
abstract = "A variation of the Haddon and Waite compacting garbage collector is presented that needs only bounded workspace, but which has typical runtime proportional to the size of the heap rather than n log n for a heap of size n. The algorithm has been measured in the context of a LISP system where it has been seen to behave close to its optimum. The relationship of this algorithm to one due to Lang and Weigbreit is also explained.",
author = "Fitch, {John P} and Norman, {A C}",
year = "1977",
doi = "10.1093/comjnl/21.1.31",
language = "English",
volume = "21",
pages = "31--34",
journal = "The Computer Journal",
issn = "0010-4620",
publisher = "Oxford University Press",
number = "1",

}

TY - JOUR

T1 - A note on compacting garbage collection

AU - Fitch, John P

AU - Norman, A C

PY - 1977

Y1 - 1977

N2 - A variation of the Haddon and Waite compacting garbage collector is presented that needs only bounded workspace, but which has typical runtime proportional to the size of the heap rather than n log n for a heap of size n. The algorithm has been measured in the context of a LISP system where it has been seen to behave close to its optimum. The relationship of this algorithm to one due to Lang and Weigbreit is also explained.

AB - A variation of the Haddon and Waite compacting garbage collector is presented that needs only bounded workspace, but which has typical runtime proportional to the size of the heap rather than n log n for a heap of size n. The algorithm has been measured in the context of a LISP system where it has been seen to behave close to its optimum. The relationship of this algorithm to one due to Lang and Weigbreit is also explained.

UR - http://dx.doi.org/10.1093/comjnl/21.1.31

U2 - 10.1093/comjnl/21.1.31

DO - 10.1093/comjnl/21.1.31

M3 - Article

VL - 21

SP - 31

EP - 34

JO - The Computer Journal

T2 - The Computer Journal

JF - The Computer Journal

SN - 0010-4620

IS - 1

ER -