A note on compacting garbage collection

John P Fitch, A C Norman

Research output: Contribution to journalArticlepeer-review


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
Issue number1
Publication statusPublished - 1977

Cite this