The Space Cost of Lazy Reference Counting

[摘要] 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

[发布机构] HP Development Company

[学科分类] 计算机科学（综合）

[关键词] reference counting;pause time;space;garbage collection;memory management