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

[Chin-Yang Lin]

Dear=20David:

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

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

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


Thanks=20and=20Regards,

Chin-Yang


=A1=B0=20=A4=DE=ADz=A1m"David=20F.=20Bacon"=20<dfb at watson.ibm.com>=A1n=A4=A7=
=B6l=A5=F3=A4=BA=AEe=A1G=20
>as=20for=20chin-yang's=20original=20query,=20i=20don't=20know=20of=20anyone=
=20who=20has=20explicitly
>studied=20the=20shape=20of=20cyclic=20structures=20in=20heaps.=20=20those=20=
of=20us=20who=20have=20built
>cycle=20collectors=20have=20done=20so=20implicitly=20in=20various=20ways.=20=
=20for=20instance,=20in
>my=20work=20with=20rajan=20we=20avoid=20trial=20deletion=20in=20statically=20=
acyclic=20portions=20of
>the=20graph=20("green=20nodes")=20and=20there=20are=20statistics=20on=20tha=
t=20in=20our=20paper
>(http://www.research.ibm.com/people/d/dfb/publications.html#Bacon01Concurre=
n
>t)=20as=20well=20as=20information=20about=20how=20much=20cyclic=20data=20ac=
tually=20turns=20out=20to
>be=20garbage.=20=20similar=20insights=20will=20be=20available=20from=20blac=
kburn=20and
>mckinley's=20paper=20(http://portal.acm.org/citation.cfm?doid=3D949305.9493=
36)=20on
>ulterior=20reference=20counting.
>
>as=20eliot=20points=20out,=20shapes=20vary=20considerably=20and=20the=20jav=
ac=20spec=20benchmark
>was=20found=20in=20the=20above=20work=20to=20have=20large=20cyclic=20struct=
ures,=20making=20it=20the
>most=20challenging=20among=20the=20spec=20benchmarks.=20=20a=20thorough=20s=
urvey=20would=20be=20a
>useful=20contribution.
>
>david
>
>
>