Orchid XP v8 <voi### [at] devnull> wrote:
> Warp wrote:

> >   I assume that it frees all the objects, not just A, but how does it do
> > it efficiently?

> The simplest (non-broken) GC implementation is the mark/sweep type.

  That really didn't answer my question. I didn't ask for the simplest
solution.

> [Note that I do not consider "reference counting" to be a valid GC 
> algorithm, since it doesn't actually work properly...]

  Yet many languages use it, such as for example PHP and Objective C.

  It just sounds to me that people object about reference counting because
in theory it's problematic, but some people just go ahead and use it anyways
without problems.

  (Yes, I know that in PHP you can actually get circular references which
get never freed, and that's a known problem, but it doesn't seem to cause
too many problems in practice nevertheless, seeing how popular PHP is.
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.)

-- 
                                                          - Warp

Post a reply to this message

Warp wrote:
>   That really didn't answer my question. I didn't ask for the simplest
> solution.

Well, you're asking about a very complex field that's been evolving for 
30 years. And the GC for each language is different.

>> [Note that I do not consider "reference counting" to be a valid GC 
>> algorithm, since it doesn't actually work properly...]
> 
>   Yet many languages use it, such as for example PHP and Objective C.

I'm not sure PHP lets you have a pointer to another object visible at 
the user layer. If you do
   $x['hello'] = $y
as far as the user is concerned, $x['hello'] and $y are two different 
values. So $y['hello'] = $y doesn't form a circular reference, as far as 
I can remember.  I'll try it out as soon as I boot over to Linux.

>   It just sounds to me that people object about reference counting because
> in theory it's problematic, but some people just go ahead and use it anyways
> without problems.

Not without problems. Firefox, for example, is redoing the entire 
plug-in memory management thing because it's too hard for extension 
writers to get right.

>   (Yes, I know that in PHP you can actually get circular references which
> get never freed, and that's a known problem, but it doesn't seem to cause
> too many problems in practice nevertheless, seeing how popular PHP is.

PHP tends to run for one web page, then exit. That's part of the 
solution. Indeed, I ran across this, trying to use PHP in a loop to 
insert a few million records from a file into a database.

Since PHP doesn't actually have pointers, it's possible the runtime is 
doing things to patch up as well.

But saying "it's good enough, who cares if one out of 20 programs leaks 
memory" is a very PHP approach, yah.

> 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.

-- 
   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

> I'm not sure PHP lets you have a pointer to another object visible at 
> the user layer. If you do
>   $x['hello'] = $y
> as far as the user is concerned, $x['hello'] and $y are two different 
> values. So $y['hello'] = $y doesn't form a circular reference, as far as 
> I can remember.  I'll try it out as soon as I boot over to Linux.

PHP has "references":

$a =& $b;

This behaves like Unix hardlinks. "$a and $b are completely equal here, 
that's not $a pointing to $b or vice versa, that's $a and $b pointing to 
the same place"

Post a reply to this message

Nicolas Alvarez wrote:
> This behaves like Unix hardlinks. "$a and $b are completely equal here, 
> that's not $a pointing to $b or vice versa, that's $a and $b pointing to 
> the same place"

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. :-)

-- 
   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:
> > 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.

-- 
                                                          - Warp

Post a reply to this message

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.

-- 
                                                          - Warp

Post a reply to this message

>>> 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