A note on compacting garbage collection

John P Fitch; A C Norman

doi:10.1093/comjnl/21.1.31

A note on compacting garbage collection

John P Fitch, A C Norman

Department of Computer Science

Research output: Contribution to journal › Article › peer-review

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 language	English
Pages (from-to)	31-34
Number of pages	4
Journal	The Computer Journal
Volume	21
Issue number	1
DOIs	https://doi.org/10.1093/comjnl/21.1.31
Publication status	Published - 1977

Access to Document

10.1093/comjnl/21.1.31

Cite this

@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

SN - 0010-4620

VL - 21

SP - 31

EP - 34

JO - The Computer Journal

JF - The Computer Journal

IS - 1

ER -

A note on compacting garbage collection

Abstract

Access to Document

Other files and links

Cite this