>>> Circular references seem to be a bit like goto: You can come up with all
>>> kinds of situations where it's "necessary", but in practice it happens
>>> rarely if at all.)
> 
>> I disagree. Doubly-linked lists, trees with pointers up the nodes, 
>> widgets with child widgets that have parent pointers, etc. Pretty much 
>> everything "OO" is good at winds up generating circular references.
> 
>   Yet, as I said, languages like PHP and Objective C seem to use
> reference counting without too many problems.

Well given a long chain of objects pointing to objects, and a pure 
reference counting system, each scan of the GC will only reclaim *one* 
object from the chain. If the chain is long, it could take a damn long 
time to reclaim all that memory.

Reference counting really is far too simplistic to work properly. I have 
no idea how other languages appear to make it work [probably by 
suplimenting it], but I wouldn't trust it as far as I could throw it. ;-)

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> Right. I suspect either they don't get GCed if you wind up with a 
>> reference to $B inside $B, or there's a mark/sweep mechanism that kicks 
>> in. Given my experiences, I'd expect it just leaks. :-)
> 
> http://www.derickrethans.nl/circular_references.php
> 
>   It seems they are working on something called "cyclic tracing" to
> alleviate the problem, whatever that may mean.

Yeah, I found that.

The naive attempt to make it blow up didn't work, using arrays, so 
obviously they're doing something a mite more sophisticated than raw 
reference counting. I suspect the fact that there *is* a symbol table 
(i.e., that there's really only one pointer to the data structure, and 
potentially many pointers to the pointer to the data structure) comes 
into it somewhere.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Warp wrote:
>   Yet, as I said, languages like PHP and Objective C seem to use
> reference counting without too many problems.

I think they're doing more than reference counting.

Reference counting is also quite slow for things that allocate and 
deallocate a lot, as you have to update the counts (atomically, if 
threaded) for every assignment.  Plus, if your objects are small (think 
LISP), it's a really poor choice.

Here's a decent FAQ I found while looking into the PHP stuff:

http://www.iecc.com/gclist/GC-faq.html

It pretty much covers the basics.  A lot of the cutting-edge stuff 
(realtime incremental GC with hardware support etc) is behind a 
you-have-to-pay-for-membership portals, like ACM stuff.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Orchid XP v8 <voi### [at] devnull> wrote:
> Well given a long chain of objects pointing to objects, and a pure 
> reference counting system, each scan of the GC will only reclaim *one* 
> object from the chain. If the chain is long, it could take a damn long 
> time to reclaim all that memory.

  Hmm, you are mixing reference counting with garbage collection.

  In a pure reference counting system the object is destroyed immediately
when all references to it go out of scope. There are no "GC scans".
(Naturally if it's a long chain of references, destroying the first
object will destroy all the others like dominoes falling.)

> Reference counting really is far too simplistic to work properly.

  Well, as long as you don't have circular references (there are ways
to make it *difficult* to create them) I don't see a problem.

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> http://www.iecc.com/gclist/GC-faq.html

  "Most allocated objects have short lifetimes."

  Hmm, that may be so with languages which force you to allocate everything
on the heap (ie. things which potentially have longer lifetimes than
stack-allocated local objects).

  Personally I seldom find myself allocating memory dynamically for short
periods of time in time-critical parts of the program, when coding in C++.
Most short-lived objects and variables can usually be handled on the stack.

  Stack allocation is actually pretty fast (at least with gcc in linux).
I have made some tests which sometimes even gave surprising results:
Having a single heap-allocated array which is used by a function each
time this function is called can sometimes be even slower than having
the function allocate the array from the stack each time it's called.
(In other words, having allocated an array just once with 'new' and
having the function, which is being called repeatedly, just use that
array, may in some cases be slower than if the function allocated the
array for itself from the stack each time the function is called.)

  That's a bit surprising of a result, but might be explainable by
cache behavior or something similar.

  (The reason why I tested this was because having the function use
the externally-allocated array is not thread-safe, while having it
allocate the array locally is.)

-- 
                                                          - Warp

Post a reply to this message

On Mon, 31 Mar 2008 22:58:31 +0200, Warp <war### [at] tagpovrayorg> wrote:
>   Stack allocation is actually pretty fast (at least with gcc in linux).

That stack allocation is fast should come as no surprise since it  
typically requires a grand total of zero additional CPU instructions. In  
the worst case it requires a single one-cycle instruction.


-- 
FE

Post a reply to this message

Warp wrote:
> (Naturally if it's a long chain of references, destroying the first
> object will destroy all the others like dominoes falling.)

That's where the "nondeterministic time" comes in with reference 
counting, just so you recognise.

>> Reference counting really is far too simplistic to work properly.
> 
>   Well, as long as you don't have circular references (there are ways
> to make it *difficult* to create them) I don't see a problem.

That's the primary problem, yes. That, and the size of the counter, if 
it needs to be the same as the size of a pointer. And that it's probably 
the slowest way to do GC.

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Warp wrote:
> Darren New <dne### [at] sanrrcom> wrote:
>> http://www.iecc.com/gclist/GC-faq.html
> 
>   "Most allocated objects have short lifetimes."
> 
>   Hmm, that may be so with languages which force you to allocate everything
> on the heap (ie. things which potentially have longer lifetimes than
> stack-allocated local objects).

And if it's not on the heap, but on the stack instead, it *still* has a 
pretty short lifetime. :-)

>   Personally I seldom find myself allocating memory dynamically for short
> periods of time in time-critical parts of the program, when coding in C++.
> Most short-lived objects and variables can usually be handled on the stack.

Yep. And a lot of languages are smart enough to figure that out 
automatically. Not Java as initially implemented.

One of the advantages of letting the compiler handle stuff like this for 
you is that the compiler can get smarter.

>   That's a bit surprising of a result, but might be explainable by
> cache behavior or something similar.

Yeah, or better addressing modes maybe?

-- 
   Darren New / San Diego, CA, USA (PST)
     "That's pretty. Where's that?"
          "It's the Age of Channelwood."
     "We should go there on vacation some time."

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> Warp wrote:
> > (Naturally if it's a long chain of references, destroying the first
> > object will destroy all the others like dominoes falling.)

> That's where the "nondeterministic time" comes in with reference 
> counting, just so you recognise.

  How is that nondeterministic? It's perfectly predictable when those
objects will be destroyed. Just because destroying one object causes
the destruction of another doesn't make it "nondeterministic".

-- 
                                                          - Warp

Post a reply to this message

Fredrik Eriksson <fe79}--at--{yahoo}--dot--{com> wrote:
> On Mon, 31 Mar 2008 22:58:31 +0200, Warp <war### [at] tagpovrayorg> wrote:
> >   Stack allocation is actually pretty fast (at least with gcc in linux).

> That stack allocation is fast should come as no surprise since it  
> typically requires a grand total of zero additional CPU instructions. In  
> the worst case it requires a single one-cycle instruction.

  But so does using a pre-allocated array. The array is *already* allocated.
The function doesn't need to allocate it each time. Yet, in some cases,
the function becomes faster by using the stack-allocated array than the
pre-allocated array in the heap.

-- 
                                                          - Warp

Post a reply to this message