[gclist] Finalizers & Reference counting.

[Boehm, Hans]

> -----Original Message-----
> From: Jerrold Leichter [mailto:jerrold.leichter@smarts.com]
> ...
> I just don't think you can pick one particular factor (like 
> the cost of
> synchronization) and say "Aha!  RC loses!"  The tradeoffs are 
> complex, and
> this is just one more factor to consider.

I agree.  But I still think it's a significant factor

I think we really need to distinguish between "simple RC" for which all reference count operations are performed synchronously by the mutator, and more sophisticated deferred RC schemes such as

Bacon, Attanasio, Lee, Rajan, Smith, "Java without the Coffee Breaks: A Nonintrusive Multiprocesssor Garbage Collector"

I think it's fair to say that for typical Java programs the best deferred schemes are at least in the same ballpark as tracing collectors.  They seem to be slower in terms of throughput, but can get very low pause times.  I think they're worth examining closely, and they may win in some situations, though based on the published results, I would usually still prefer a tracing collector.  They also share a lot of performance characteristics with tracing collection.  In particular, you don't get simple timing guarantees for acyclic data structures.

Simple synchronous reference counting seems to work well for very large objects in acyclic data structures, e.g. in file systems.  It also sometimes pays off if you can simultaneously use it for things other than memory management, e.g. avoiding copies.  And it may reduce space consumption.  But as a general memory management technique for small objects, it suffers from many problems:

1) Cycles.
2) Large pause times.  It's generally far more expensive to deallocate a data structure comprising most of the heap an object at a time than it is to trace the heap.
3) If you have finalizers/destructors, you need to explicitly defer finalization to get correct semantics.  I maintain that implementations that run finalizers/destructors synchronously (all of the C++ ones?) are just plain wrong, at least in the sense that they greatly complicate the programmers job, and no real programmer will do the work to ensure that the results are correct.
4) Large mutator overhead, especially for multithreaded code, even if it doesn't allocate during a phase.

My impression is that for a multithreaded application operating on small objects, the cost of atomic operations doesn't always matter, but it ensures that you almost always lose on time performance.  If a piece of code runs within the cache, the atomic operations will slow it down by a large factor, since you've added 40-400 cycles to every pointer assignment, and your code used to run fast enough that this is a big deal.  (Based on my experiments, there is basically nothing else you can do during these operations, so clever scheduling doesn't help much.)  If it doesn't fit in the cache, the reference-counted version will almost certainly greatly increase the number of cache misses, since pointer assignments now touch both the old and new referenced object.  In this case, even the single-threaded version will take the hit, though the cost of the atomic operations is much less of an issue.

Unfortunately real measurements are hard to come by.  But the above paper makes many major improvements to the simple RC algorithm and gets uniprocessor runtimes that are still appreciably slower than tracing.  (It does include a cycle collector, which affects the cost.)

Hans