Re: Are there any studies or reports about the analysis of cyclic structures?

Dear David:

Thanks for your info. 
I had read the papers you mentioned here. Your research [Bacon01] really help us better/quickly study the reference counting technique.   

As many people pointed out here, there seem no papers/studies focusing on the analysis of cyclic structures. In fact, my concern is, if someone develops a cycle detection algorithm and he/she wants to do a micro-benchmarking for measuring the performance, what would be better test cases (e.g. singly-linked list or doubly-linked list) and what is the significant scale for each test case? 

I know that, in practice, a better way to evaluate the algorithm would be done in a real system, such as JVM. However, this is not easy for a researcher who is not familiar with that specific system. I mean, if the taken cases (graphs) are real enough, the results of the micro-benchmarking may also be significant and particularly the evaluation work can be done easily (that needs not involve a specific system too much).


Thanks and Regards,

Chin-Yang


※ 引述《"David F. Bacon" <[email protected]>》之郵件內容： 
>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
>
>
>