From: Chris Benson
Subject: Deutsch/Bobrow paper on garbage collection: Successful Implementations?
Date:
Message-ID: <888471297.856765@ridge.spiritone.com>
L. Peter Deutsch and Daniel G. Bobrow published a paper called 'An Efficient,
Incremental, Automatic Garbage Collector' in the CACM (Sept. 1976). I am
doing some research on garbage collection and I would like to know if the
algorithm they describe was ever successfully implemented and if it is used in
any modern systems?
If anyone is familiar with this paper and knows the answer to my question,
please let me know! Thanks-
Chris Benson
···············@spiritone.com|nospam
remove spam-bait to reply
From: Eliot & Linda
Subject: Re: Deutsch/Bobrow paper on garbage collection: Successful Implementations?
Date:
Message-ID: <34F59F3A.1430@pacbell.net>
Chris Benson wrote:
>
> L. Peter Deutsch and Daniel G. Bobrow published a paper called 'An Efficient,
> Incremental, Automatic Garbage Collector' in the CACM (Sept. 1976). I am
> doing some research on garbage collection and I would like to know if the
> algorithm they describe was ever successfully implemented and if it is used in
> any modern systems?
>
> If anyone is familiar with this paper and knows the answer to my question,
> please let me know! Thanks-
The algorithm they present is commonly known as "Deferred Reference
Counting". The algorithm is a modification of reference counting that
does not count the stack. In stack implementations of Lisp-like
languages most writes are to the stack, but the net change in reference
counts due to writes to the stack is zero, since objects are retained
only via references to the heap. The algorithm maintains a set of
objects that at some time in their life have a zero count, known ast the
Zero Count Table (ZCT)). These objects can't be reclaimed since they
may have (uncounted) references from the stack. Periodically, (e.g.
when the ZCT reaches a high-tide) the stack is swept, incrementing the
counts of objects referenced from the stack, the ZCT is scanned for
objects in the ZCT that still have a zero count, and these are
reclaimed, using a standard recursive freeing traversal. The ZCT is
then emptied, the stack is swept decrementing the counts of objects on
the stack, and putting objects with a zero count (that are therefore
only referenced from the stack) back in the ZCT. Computation then
continues.
Presumably the technique was successfully applied to Lisp by Deutsch &
Bobrow. I think it may have been used in some Mesa implementations, but
I'm not sure. The algorithm was also popular in eighties Smalltalk
implementations. The first commercial releases of Smalltalk from
ParcPlace used it (ObjectWorks 2.1, 2.2 & 2.3). My BrouHaHa engine used
it (see OOPSLA '87). But generation scavenging is significantly more
efficent, (~ 3x), and has replaced it in all modern implementations I'm
aware of.
One advantage it does have is the ability to run with very little
head-room. But its inability to reclaim circular structures requires
back-up by a global collector.
A web search for "deferred reference counting" should find a number of
descriptions in survey papers.
_______________,,,^..^,,,_______________
Eliot Miranda, ParcPlace