The one-bit reference count

DS Wise, DP Friedman - BIT Numerical Mathematics, 1977 - Springer
DS Wise, DP Friedman
BIT Numerical Mathematics, 1977Springer
Deutsch and Bobrow propose a storage reclamation scheme for a heap which is a hybrid of
garbage collection and reference counting. The point of the hybrid scheme is to keep track of
very low reference counts between necessary invocation of garbage collection so that nodes
which are allocated and rather quickly abandoned can be returned to available space,
delaying necessity for garbage collection. We show how such a scheme may be
implemented using the mark bit already required in every node by the garbage collector …
Abstract
Deutsch and Bobrow propose a storage reclamation scheme for a heap which is a hybrid of garbage collection and reference counting. The point of the hybrid scheme is to keep track of very low reference counts between necessary invocation of garbage collection so that nodes which are allocated and rather quickly abandoned can be returned to available space, delaying necessity for garbage collection. We show how such a scheme may be implemented using the mark bit already required in every node by the garbage collector. Between garbage collections that bit is used to distinguish nodes with a reference count known to be one. A significant feature of our scheme is a small cache of references to nodes whose implemented counts “ought to be higher” which prevents the loss of logical count information in simple manipulations of uniquely referenced structures.
Springer