Stop-and-copy and One-bit Reference Counting?

Technical Report 360

David S. Wise
Indiana University
Bloomington, Indiana 47405 USA
Fax: +1 (812) 855-4829
Email: [email protected]

(revised) March 1993

Abstract

A stop-and-copy garbage collector updates one-bit reference counting with essentially no extra space and minimal memory cycles beyond the conventional collection algorithm. Any object that is uniquely referenced during a collection becomes a candidate for cheap recovery before the next one, or faster recopying then if it remains uniquely referenced. Since most objects stay uniquely referenced, subsequent collections run faster even if none are recycled between garbage collections. This algorithm extends to generation scavenging, it admits uncounted references from roots, and it corrects conservatively stuck counters, that result from earlier uncertainty whether references were unique.

CR categories and Subject Descriptors:
D.4.2 [Storage Management]: Allocation/Deallocation strategies; E.2 [Data Storage Representations]: Linked representations.
General Term: Algorithms.
Additional Key Words and Phrases: multiple reference bit, MRB.

?Research reported herein was sponsored, in part, by the National Science Foundation under Grant Number CCR 90-02797.

1

1 One-bit Reference Counts

The most commonly used garbage collector is the stop and copy algorithm due to Minsky, Finichel, and Yokelson [15, 8]. Sometimes it is a generation scavenging [22, 26] variant that more frequently recovers shorter-lived structures with less effort. Reference counting [12] is an orthogonal strategy for storage management [11] that again is receiving attention in the context of parallel heap management because its transactions are all local [21, 30, 32]. Reference counting is best used along with a garbage collector as a hybrid manager [28, 20, 13, 29]. Although counting is too weak to handle certain circular structures [20, 16], garbage collection can back it up. On the other hand, successful reference counting can postpone need for garbage collection, or accelerate that collection [3]. Recovery of zero-count objects is worthwhile only when the per-node cost of reference-counting recovery undercuts that for garbage collecting [1]. The cost, however, must include the impact of synchronization in a real-time or multiprocessor environment. One way to improve the performance of both is to use hardware [32] to maintain the counts without any extra cycles.