Re: Daily gclist MIME digest V5 #52

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Erez Petrank wrote:
> The algorithms proposed at the early days are in [1,2,3] and some of it
> is explained in the GC-book [6].  More advanced algorithms appear in
> [4,5].  You can easily find and download the latest work from the internet.

Thanks a lot, Erez. I'm trying to locate the Richard E.Jones book in the
nearby university library.

I provide some links (Google courtesy) that I hope be useful to other
list subscribers:

> [1] LINS,R.D.Cyclic reference counting with lazy
> mark-scan.Inf.Process.Lett.44,4 (Dec.
> 1992),215?220.

http://www.cs.kent.ac.uk/pubs/1992/120/

I've not read it yet, but his approach seems similar to my current work:
If the ref count is zero, I delete the object. If the refcount is not
zero, I add the object to a lazy mark&sweep structure. From time to
time, I scan the structure. For each object there, I get its ref count
and keep it in a variable. Then I follow the graph references from
there. Each time I reach the initial object, I decrease the variable
that maintains the running reference count of the object. If that
variable is zero, then this object lives in a cyclic structure and the
only pointers to it comes from that structure. If all other objects in
the structure only have internal pointers also, we can recicle it entirely.

I still need to traverse a potentially large object space. For example,
if an internal object points to the "root" object, I would need to scan
the entire object space. Not fun if your objects reside on disk and you
count them by millions.

OK. I just read the article. The algorithm seems similar to my current
implementation. The four colour scan could be useful, nevertheless, to
avoid re-scan known non-cycle members.

Let's move on...

> [2] JONES,R.E.,AND LINS,R.D.Cyclic weighted reference counting without
> delay.In
> PARLE?93 Parallel Architectures and Languages Europe (June
> 1993),A.Bode,M.Reeve,
> and G.Wolf,Eds.,vol.694 of Lecture Notes in Computer
> Science,Springer-Verlag,
> pp.712?715.

http://citeseer.ist.psu.edu/jones92cyclic.html

The interesting bit here (to me, of course) is that this algorith allows
concurrent operation of the mutator. In my case, the mutator can fully
cooperate with GC, so it is not a problem.

I didn't know the weighted garbage collection approach. Very clever. My
problem is uniprocessor, nevertheles. But nice trick. I will remember it.

> [3] MART?INEZ,A.D.,WACHENCHAUZER,R.,AND LINS,R.D.Cyclic reference counting
> with local mark-scan.Inf.Process.Lett.34,1 (1990),31?35.

This paper is "superseded" by [1] :-).

> [4] David F.Bacon and V.T.Rajan.Concurrent cycle collection in reference
> counted systems.In Jørgen Lindskov Knudsen,editor,
> Proceedings of 15th European Conference on Object-Oriented
> Programming,ECOOP 2001,volume 2072 of Springer-Verlag,
> Budapest,June 2001.Springer-Verlag.

http://citeseer.ist.psu.edu/532569.html

This work polishes several cases in [1] (in particular, scanning time is
proportional to object count) and avoid to scan "acyclic" objects,
something I already do :).

The concurrent version is nice. I should study it better, but
concurrency is not, currently, a priority.

> [5] Harel Paz, Erez Petrank, David F. Bacon, V.T. Rajan, and Elliot K.
> Kolodner. An efficient on-the-fly cycle collection. In  Proceedings of
> the 14th International Conference on Compiler Construction, Edinburgh,
> April 2005. Springer-Verlag.

Just cooked. Nice :)

http://citeseer.ist.psu.edu/639516.html

Good paper, with some heuristics to improve cycle detection efficiency.
Nevertheless, the entire object rspository must be scanned if a "deep"
object links to "root" object :-(.

> [6]  Richard E.Jones.Garbage Collection:Algorithms for Automatic Dynamic
> Memory Management.Wiley,Chichester,July
> 1996.With a chapter on Distributed Garbage Collection by R.Lins.

Trying to find it...

Time to rest. Thank you for your time and links.

- --
Jesus Cea Avion                         _/_/      _/_/_/        _/_/_/
[email protected] http://www.argo.es/~jcea/ _/_/    _/_/  _/_/    _/_/  _/_/
                                      _/_/    _/_/          _/_/_/_/_/
PGP Key Available at KeyServ   _/_/  _/_/    _/_/          _/_/  _/_/
"Things are not so easy"      _/_/  _/_/    _/_/  _/_/    _/_/  _/_/
"My name is Dump, Core Dump"   _/_/_/        _/_/_/      _/_/  _/_/
"El amor es poner tu felicidad en la felicidad de otro" - Leibniz
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.2 (GNU/Linux)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iQCVAwUBQ8ai35lgi5GaxT1NAQI7igP+Oovus2pvK1BvL9htuP1RB5hhnKYVVRCK
te31KbCDf7bQ9PLUs48ih3sE8t2Zzp9PODJkhqf7c6x1r73iL8xAmUUzxsyXfaOz
5oGkfUiBTh9rmVXTEkD7AJbQhoQlRgLQvsvh+JfyipHyM4hAbVKhBtfvN4eOstgh
4TQ7BvjeLj0=
=m/yl
-----END PGP SIGNATURE-----