Re: Compiler writers will love this language

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

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