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.