[gclist] Are there any studies or reports about the analysis of cyclic structures?

[David F. Bacon]

> I feel I should point out that the first garbage collector was
> mark-sweep tracing, not reference counting [McCarthy 1960, section
> 4c].

reference counting was published by collins in the same year, in the
december cacm (http://portal.acm.org/citation.cfm?id=367501) -- although the
lack of cycle collection wasn't pointed out until somewhat later (citation,
anyone?).   so the invention of the two algorithms was roughly
contemporaneous, although it is highly likely that tracing came first since
collins cites mccarthy's work (he calls it "elegant but inefficient"!).  how
early they were in use (as opposed to when they were published) would be an
interesting tidbit.

as for chin-yang's original query, i don't know of anyone who has explicitly
studied the shape of cyclic structures in heaps.  those of us who have built
cycle collectors have done so implicitly in various ways.  for instance, in
my work with rajan we avoid trial deletion in statically acyclic portions of
the graph ("green nodes") and there are statistics on that in our paper
(http://www.research.ibm.com/people/d/dfb/publications.html#Bacon01Concurren
t) as well as information about how much cyclic data actually turns out to
be garbage.  similar insights will be available from blackburn and
mckinley's paper (http://portal.acm.org/citation.cfm?doid=949305.949336) on
ulterior reference counting.

as eliot points out, shapes vary considerably and the javac spec benchmark
was found in the above work to have large cyclic structures, making it the
most challenging among the spec benchmarks.  a thorough survey would be a
useful contribution.

david