Re: Best Ref-counting algorithms?

On Thu, 16 Jul 2009 09:54:56 GMT, "BartC" <bartc@freeuk.com> wrote:


>"BGB / cr88192" <cr88192@hotmail.com> wrote in message
>> "George Neuner" <gneuner2@comcast.net> wrote in message
>>> On Sun, 12 Jul 2009 13:41:59 -0700 (PDT), Christoffer Lernv
>
>
>>> If you're dead set on reference counting, you should investigate 1-bit
>>> reference counting. I don't have URL's to give you but they should be
>>> easy to find. The programming language is designed so that most data
>>> are not shared and then you only need a simple flag to say whether the
>>> item is shared and so needs special handling.
>>>
>> this sounds interesting, but I don't know much about this approach...
>
>It sounds scarily like what I was once using: a language where
>variables never shared data, except when used in expressions and
>function calls, when a copy bit was set so that only shallow copies of
>any value could be pushed around instead.
>
>With strings, and arrays of arbitrary complexity, being handled
>automatically with implicit pointers and the copy bit used to tell it
>when to free, duplicate, or do nothing, this worked extremely well
>with no need for GC:
>
>a:=(10,20,30,40,50) >reate some array
>a:=0 #now the array magically disappears and a is an int
>
>It doesn't work well however when the language allows *explicit* pointers:
>
>a:=(10,20,30,40,50) #an array again
>p:=&a[2] #set some explicit pointers to elements in a
>q:=&a[3]
>a:=0
>
>Now the array disappears again, but p and q are left pointing at phantom
>elements. If this 1-bit trick can help with this, I'd be interested too, as
>full GC seems an overkill.


It might be some help, but you still need some way to identify the
base address of the array so you can deal with its allocation block,
check bounds, etc.


One way to handle this with 1-bit RC is to allocate the array
descriptor and data block separately. You manage the small descriptor
and special case the GC to also release the data block when the
descriptor is released. This arrangement also allows for having easy
extensible arrays.


It does mean that array references are double indirected - ie. the
"pointers" are really "handles", which may have some performance
issues. It isn't a problem for loops and such where you'd compute and
cache the address anyway, but for isolated references it can be an
issue.




One thing I forgot to mention previously is that the 1-bit "share"
flag can usually be kept as an immediate tag in the pointers
themselves. That makes checking/setting it simple but to use the
pointer you may have to strip the tag or factor its value into your
index calculations.


George

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