The Space Cost of Lazy Reference Counting

Hans-J. Boehm

To appear at Principles of Programming Languages (POPL04), Venice, Italy, January 14-16, 2004


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 lazy reference counting, the standard technique for avoiding long pauses by deferring 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 about 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.

Server START Conference Manager
Update Time 19 Sep 2003 at 17:40:42
Start Conference Manager
Conference Systems