| |
Click here for full text:
The Space Cost of Lazy Reference Counting
Boehm, Hans-J.
HPL-2003-215
Keyword(s): reference counting; pause time; space; garbage collection; memory management
Abstract: Reference counting memory management is often advocated as a technique for reducing or avoiding the pauses associated with tracing garbage collection. We present some measurements to remind the reader that classic reference count implementations may in fact exhibit longer pauses than tracing collectors. We then analyze reference counting with lazy deletion, the standard technique for avoiding long pauses by deferring deletions and associated reference count decrements, usually to allocation time. Our principal result is that if each reference count operation is constrained to take constant time, then the overall space requirements can be increased by a factor of n(R) in the worst case, where R is the ratio between the size of the largest and smallest allocated object. This bound is achievable, but probably large enough to render this design point useless for most real-time applications. We show that this space cost can largely be avoided if allocating an n byte object is allowed to additionally perform O(n) reference counting work. Notes: To be published in and presented at the 31st Annual ACM SIGPLAN/SIGACT Symposium on Principles of Programming Languages (POPL '04), 14-16 January 2004, Venice, Italy
10 Pages
Back to Index
|
printable version
