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.
No takes yet. Share an insight, caveat, or question.
John Fitch (1978) studied this question.
Synapse has enriched 5 related papers. Consider them for comparative context: