Re: Compiler writers will love this language

mwotton@cse.unsw.edu.au (Mark Alexander Wotton)
3 Jul 2003 23:59:20 -0400

          From comp.compilers

Related articles
[16 earlier articles]
Re: Compiler writers will love this language lex@cc.gatech.edu (Lex Spoon) (2003-06-25)
Re: Compiler writers will love this language firefly@diku.dk (Peter \Firefly\Lund) (2003-06-25)
Re: Compiler writers will love this language joachim.durchholz@web.de (Joachim Durchholz) (2003-07-02)
Re: Compiler writers will love this language strohm@airmail.net (John R. Strohm) (2003-07-02)
Re: Compiler writers will love this language genew@mail.ocis.net (2003-07-02)
Re: Compiler writers will love this language ericmuttta@email.com (2003-07-02)
Re: Compiler writers will love this language mwotton@cse.unsw.edu.au (2003-07-03)
Re: Compiler writers will love this language nmm1@cus.cam.ac.uk (2003-07-04)
Re: Compiler writers will love this language nmm1@cus.cam.ac.uk (2003-07-04)
Re: Compiler writers will love this language joachim.durchholz@web.de (Joachim Durchholz) (2003-07-13)
garbage collection lex@cc.gatech.edu (Lex Spoon) (2003-07-13)
Re: Compiler writers will love this language ericmuttta@email.com (2003-07-15)
Re: Compiler writers will love this language nmm1@cus.cam.ac.uk (2003-07-15)
[2 later articles]
| List of all articles for this month |

From: mwotton@cse.unsw.edu.au (Mark Alexander Wotton)
Newsgroups: comp.compilers
Date: 3 Jul 2003 23:59:20 -0400
Organization: Mare's Nest Collective
References: 03-05-211 03-06-015 03-06-054 03-06-057 03-06-078 03-06-106 03-07-023
Keywords: storage
Posted-Date: 03 Jul 2003 23:59:20 EDT

On 2 Jul 2003 00:44:39 -0400, Eric posted:
> mwotton@cse.unsw.edu.au (Mark Alexander Wotton) wrote in message news:03-06-106...
>> You do have the problem with reference-counting that it doesn't cope
>> very well with two-way links.
>
> This problem really bugs, because the standard library is going to be
> full of data structures the utilise two way links (eg. doubly linked
> lists). Is there a general solution (other than using a completely
> different scheme like mark-and-sweep) for this? One of the reasons I
> really fancy reference-counting is its low overhead, but I suspect
> that with a few adjustments to the algorithm, one can add in logic
> that will detect circular links during deallocation. Its seems to be a
> general graph traversal/tracing problem, where one wants to know "have
> I visited this node before?" and if the answer is "yes" then we know a
> circular link exists somewhere and act accordingly inorder to
> deallocate the objects involved.


As soon as you've done graph traversal, though, you've got the same
overhead as mark and sweep. The appeal of reference counting (apart
from simplicity) is that it's got a constant overhead (modulo the case
discussed where a freed object sets off a chain of deallocation). To
be honest, I'm not even convinced that reference counting does have
low overhead. If A points to B, and is then changed to point to C,
then I have three memory accesses instead of 1: I have to decrement
B's counter and increment C's, as well as the actual write to A.


(Idle thought: seeing as the only way to create circular references is
through mutable references in a strict language, or tying the knot in
a lazy one, perhaps reference counting would be useful for a strict
purely functional language.)


>> Generational collection is nice partly
>> because it's complete (all unused allocations are reclaimed)
>
> How, by the way, does generational collection deal with circular
> references? Could the algorithm used be adapted for use in reference
> counting, to form a sort of new hybrid scheme?


My understanding is that generational collection is essentially an
optimisation on mark and sweep, which has no problems with circular
references.


>> mrak
>
> You know, i have been calling you "mrak" all this time, is that
> correct or just a typo for "Mark"? In any case, thanx for your
> comments.


It's a deliberate tyop. My real name is Mark.


Mrak


--
realise your life was only bait for a bigger fish
-- aesop rock


Post a followup to this message

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