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

>>>>> "Chin-Yang" == Chin-Yang Lin <[email protected]> writes:

    Chin-Yang> I am studying the traditional gc algorithm - reference
    Chin-Yang> counting(RC). A major weakness for RC is the inability to
    Chin-Yang> reclaim cyclic garbage. Many studies proposed their cyclic
    Chin-Yang> reference counting algorithms to deal with this problem in
    Chin-Yang> different efficient manners.

    Chin-Yang> However, I can not find any studies or reports on the
    Chin-Yang> analysis of cyclic structures. I mean, in real programs
    Chin-Yang> execution (especially for that written in Object-Oriented
    Chin-Yang> language), what is the likely proportion of cyclic garbage?
    Chin-Yang> What is the average size of cyclic structures? ...


Dear Tomylin -- This is known to vary a lot. Some programs use trees/DAGs
(acylic structures) almost exclusively, some use back links, which create
cycles. For example, I believe that the SPECjvm benchmark javac uses back
links in its parse trees (which attach to other information), so it has
large structures that are cyclic or reachable from cycles.

Some of the empirical work on cycle detection might tell you more.

-- EM