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.
Original languageEnglish
Pages (from-to)31-34
Number of pages4
JournalThe Computer Journal
Volume21
Issue number1
DOIs
Publication 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

JF - The Computer Journal

SN - 0010-4620

IS - 1

ER -