The Memory Management Reference
Bibliography Abstract

 Contents | News | Glossary | FAQ | Articles | Bibliography | Links | Feedback

Henry G. Baker. 1994. Minimizing Reference Count Updating with Deferred and Anchored Pointers for Functional Data Structures.

"Reference counting" can be an attractive form of dynamic storage management. It recovers storage promptly and (with a garbage stack instead of a free list) it can be made "real-time" -- i.e., all accesses can be performed in constant time. Its major drawbacks are its inability to reclaim cycles, its count storage, and its count update overhead. Update overhead is especially irritating for functional (read-only) data where updates may dirty pristine cache lines and pages. We show how reference count updating can be largely eliminated for functional data structures by using the "linear style" of programming that is inspired by Girard's linear logic, and by distinguishing normal pointers from "anchored pointers", which indicate not only the object itself, but also the depth of the stack frame that anchors the object. An "anchor" for a pointer is essentially an enclosing data structure that is temporarily locked from being collected for the duration of the anchored pointer's existence by a deferred reference count. An "anchored pointer" thus implies a reference count increment that has been deferred until it is either cancelled or performed. Anchored pointers are generalizations of "borrowed" pointers and "phantom" pointers. Anchored pointers can provide a solution to the "derived pointer problem" in garbage collection.