============Forward begins=============
"A (Grand?) Unified Theory of Storage Reclamation" Speaker: David F. Bacon Host: Professor Martin Rinard Host Affiliation: Computer Architecture Group
Date: 4-5-2004 Time: 3:30 PM - 5:00 PM Refreshments: 3:15 PM Location: Gates 7th Floor Lounge
The two basic forms of automatic storage reclamation, tracing and = reference counting, were invented at the dawn of the high-level language = era over 40 years ago. Since then there have been many improvements and = optimizations, but all systems are based on one or the other of these = methods, which are uniformly viewed as being fundamentally different and = possessing very distinct performance properties. We have implemented = high-performance collectors of both types, and in the process observed = that the more we optimized them, the more similarly they behaved -- that - they seem to share some deep structure.
We present a formulation of the two algorithms that shows that they are = in fact duals of each other. Intuitively, the difference is that = tracing operates on live objects, or "matter", while reference counting = operates on dead objects, or "anti-matter". For every operation by the = tracing collector, there is a precisely corresponding anti-operation by = the reference counting collector.
Viewed in this light, we show that all high-performance collectors (for = example, deferred reference counting and generational collection) are in = fact hybrids of tracing and reference counting. We are developing a = uniform cost-model for the collectors to quantify the tradeoffs that - result from choosing different hybridizations of tracing and reference = counting. This will allow the correct scheme to be selected based on = system performance requirements and the expected properties of the = target application.
Relevant URL(S):
For more information please contact: Mary McDavitt, 617-253-9620, [EMAIL PROTECTED]
_______________________________________________ Seminars mailing list [EMAIL PROTECTED] http://lists.csail.mit.edu/mailman/listinfo/seminars
