[cap-talk] Object garbage collection - early work

[Charles Landau]

[Discussion moved here from coyotos-dev]

Sandro Magi wrote at 
http://www.coyotos.org/pipermail/coyotos-dev/2008-August/001690.html:
> Charles Landau wrote:
>> > The PDP-1 did not have a garbage collector 
>> > in the traditional sense of scanning all live objects and then 
>> > collecting the rest. It kept a reference count on objects. When a 
>> > reference was deleted, it then scanned *from that point* to determine if 
>> > the remaining references were merely self-referential.
> 
> Interesting! All non-concurrent GC algorithms are a hybrid mix of 
> reference counting and tracing [1], so this system definitely counts as 
> GC. The first cycle collector for reference counting was described in 
> the literature in 2001 [2] to the best of my knowledge, but this use 
> might predate it by a good number of years.
> 
> Sandro
> 
> [1] http://researchweb.watson.ibm.com/people/d/dfb/papers/Bacon04Unified.pdf
 > [2]

> http://researchweb.watson.ibm.com/people/d/dfb/papers/Bacon01Concurrent.pdf

William Ackerman responded privately:

> Yes, I believe I had a not-fooled-by-directed-cycles garbage
> collector on the PDP-1, probably around 1969.
> 
> ... But I didn't remember at the time where it would have been
> used. The intention was to implement "directories", which
> were [text string -> OS object] maps, and would, of course,
> be the only way that files would have names on the PDP-1.
> 
> ...  Then I remembered, after starting
> this email message -- "spheres" a.k.a. "computations".
> They had C-lists that could own other spheres, and the various
> system calls could copy capabilities around, so one could make
> big trees of such things, including directed cycles. (Where
> "big" trees meant however many drum fields you could get,
> which wasn't many.)
> 
> Anyway, I worked out a hairy algorithm, *which I never proved,
> and never published anywhere*, and, as far as I know, was an
> original invention. ...  I recall testing it on as big and hairy a tree
> as I could make. Because it had to swap in the fields to look
> at their C-lists, it took a long time to run. (A minute or so,
> I guess.) It was very gratifying to see it terminate.
> 
> Much later, at MIT in the early/mid 80's, I recall seeing
> something in SIGPLAN or TOPLAS or something that made me think
> that this was still an interesting issue and that it had not
> been worked out. I recall writing up something, which I may
> have submitted and didn't hear anything back. It may be that
> I had misconstrued what the issue was--I don't remember. But
> I must have reconstructed the algorithm, presumably by going
> back and looking at the original code. Which I had recovered
> off of the old DECtapes. I don't know whether I still have
> that stuff. Much of the PDP-1 stuff may be lost.
> 
> Your recollection of how it worked is correct. It kept reference
> counts, and checked from the point where a reference count was
> being decreased to see whether it had now created an orphan.
> There was some kind of second reference count field indicating
> how many references could be attributed to the object's own
> subobjects, and a few status bits, ....