[PRL] "A (Grand?) Unified Theory of Storage Reclamation" MIT, M 4/5/04

[Mitchell Wand]

From: CSAIL Event Calendar <eventcalendar at csail.mit.edu>
Sender: seminars-bounces at lists.csail.mit.edu
To: seminars at csail.mit.edu
Cc: 
Subject: TALK:4-5-04 "A (Grand?) Unified Theory of Storage Reclamation"
Date: Tue, 30 Mar 2004 13:11:15 -0500


"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,
mmcdavit at csail.mit.edu 

_______________________________________________
Seminars mailing list
Seminars at lists.csail.mit.edu
http://lists.csail.mit.edu/mailman/listinfo/seminars