Re: Storage management, was Compiler writers will love this language

haberg@matematik.su.se (Hans Aberg)
17 Jul 2003 00:27:22 -0400

          From comp.compilers

Related articles
[10 earlier articles]
Re: Storage management, was Compiler writers will love this language lex@cc.gatech.edu (Lex Spoon) (2003-07-04)
Re: Storage management, was Compiler writers will love this language mwotton@cse.unsw.edu.au (2003-07-04)
Re: Storage management, was Compiler writers will love this language blackmarlin@asean-mail.com (2003-07-04)
Re: Storage management, was Compiler writers will love this language nmm1@cus.cam.ac.uk (2003-07-13)
Re: Storage management, was Compiler writers will love this language stephen@dino.dnsalias.com (2003-07-17)
Re: Storage management, was Compiler writers will love this language monnier+comp.compilers/news/@cs-www.cs.yale.edu (Stefan Monnier) (2003-07-17)
Re: Storage management, was Compiler writers will love this language haberg@matematik.su.se (2003-07-17)
Re: Storage management, was Compiler writers will love this language lars@bearnip.com (2003-07-17)
Re: Storage management, was Compiler writers will love this language RLake@oxfam.org.pe (2003-07-17)
Re: Storage management, was Compiler writers will love this language dmr@bell-labs.com (Dennis Ritchie) (2003-07-17)
Re: Storage management, was Compiler writers will love this language dot@dotat.at (Tony Finch) (2003-07-17)
Re: Storage management, was Compiler writers will love this language waxlex@yahoo.co.uk (ikhnos) (2003-07-21)
Re: Storage management, was Compiler writers will love this dobes@dobesland.com (Dobes Vandermeer) (2003-07-25)
[1 later articles]
| List of all articles for this month |

From: haberg@matematik.su.se (Hans Aberg)
Newsgroups: comp.compilers
Date: 17 Jul 2003 00:27:22 -0400
Organization: Mathematics
References: 03-05-211 03-06-015 03-06-054 03-06-057 03-06-078 03-06-106 03-07-023 03-07-044 03-07-064
Keywords: GC
Posted-Date: 17 Jul 2003 00:27:22 EDT

nmm1@cus.cam.ac.uk (Nick Maclaren) wrote:


>|> I don't believe anyone has ever fixed the cyclic graph problem with
>|> reference-counting.
>
>As it is theoretically impossible to fix, that seems likely :-)


It is not impossible to make versions (but not pure ref count) that can
trace cyclicity in some circumstances:


I thought of a variation building on Tarjan's strongly connected
components (SCC) algorithm:
        http://www1.ics.uci.edu/~eppstein/161/960220.html#sca


This works so that the objects are numbered consecutively as they are
created. A cycle can then be detected if it points to another object with
(depending on the setup) higher/lower number, which can be used to adjust
the ref count so that deletion takes place appropriately also in cycles
(which initially must have some external ref pointing at them). A problem
arises though if, after an initial setup of references have been achieved,
they are relocated dynamically, creating new cycles. That is hard to track
down. But if that does not happen, one can make a version building on this
SCC algorithm to remove the cycles as well (or so I remember).


If one should get around this dynamically created cycles problem, perhaps
one ends up on essentially a tracing algorithm.


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.math.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.