Warp wrote:

> Darren New <dne### [at] sanrrcom> wrote:
> 
>>Not necessarily. They're pointed to by the object that represents the 
>>list as a whole. What pointer would you drop to make the list 
>>garbage-collect with a reference-count GC?
> 
> 
>   How do languages where there no concept of "new" (as in Java or C++)
> nor a Java-style GC of dynamically allocated objects do it?

They don't dynamically allocate and deallocate memory, I guess. I'm not 
sure what your questions means. What I'm saying is that having circular 
links between objects is not at all uncommon in languages that allow 
such. It's the natural way to represent many semi-independent entities 
(like screens/windows, frames/scrollbars, RPG objects/rooms, tree nodes, 
etc.).

Obviously, if you don't have dynamically-allocated objects, then you 
don't have to worry about circular references with reference-counting 
garbage collection. If you have dynamically-allocated objects *and* no 
GC, then obviously it's up to the programmer to free things without 
assistance, and programmed reference counting won't fix that.

>>Plus, reference counting has very bad performance as well as being 
>>non-real-time and uninterruptable.
> 
> 
>   Very bad performance? I think that incrementing/decrementing a counter
> each time an object is copied doesn't increase too much of its slowness.

Not true. You have to also account for the object's reference count 
overflowing, for example. Plus, you actually have to *free* the objects 
when the counter goes to zero. Generational GC doesn't have to do 
anything with objects that have been freed (which admittedly makes 
finalizers messy, but they are messy to handle "correctly" in any 
language and model). You can allocate 100,000 individual objects and 
free them all with one instruction. There's a reason why nobody uses 
reference-counted garbage collection for real any more.

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message

Darren New wrote:
> Not true. You have to also account for the object's reference count
> overflowing, for example.

Sorry, can't help responding to this: If your reference counter variable
size is the same as your native pointer size, it can *never* overflow.

	Thorsten

Post a reply to this message

Thorsten Froehlich wrote:

> Darren New wrote:
> 
>>Not true. You have to also account for the object's reference count
>>overflowing, for example.
> 
> Sorry, can't help responding to this: If your reference counter variable
> size is the same as your native pointer size, it can *never* overflow.

Yes, but that's very inefficient, especially if you have objects that 
are persisted elsewhere (e.g., if you have objects distributed across 
many computers, or stored in named files, or in an OO database). Most 
reference-counted systems allocate between five and eight bits for 
reference counts. Incidentally, that's another reason reference counting 
isn't used much - the size penalty. And you still have to be able to do 
mark-and-sweep to account for circular references anyway.

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> You have to also account for the object's reference count 
> overflowing, for example.

  It's impossible for a reference counter to overflow. You can't allocate
that much memory. You can't have pointers pointing to that many objects
in the first place.

  If you had to manage more data than the pointer size of the architecture
can point to, then everything handling the data will be bigger&slower
anyways. A reference counter won't matter much.

> You can allocate 100,000 individual objects and 
> free them all with one instruction.

  Assuming no memory fragmentation, of course.

  Besides, a reference-counting system doesn't have to *free* the
objects immediately when the last reference dies. It can mark the
object as "to be freed" and put it somewhere to wait.

  Btw, how does the GC engine know that the object is not used anymore?

-- 
                                                          - Warp

Post a reply to this message

Darren New <dne### [at] sanrrcom> wrote:
> > Sorry, can't help responding to this: If your reference counter variable
> > size is the same as your native pointer size, it can *never* overflow.

> Yes, but that's very inefficient, especially if you have objects that 
> are persisted elsewhere (e.g., if you have objects distributed across 
> many computers, or stored in named files, or in an OO database).

  Oh, of course handling more data than the natural pointer size of the
system is very efficient. It's just the reference counter which is
inefficient because it has to be able to count more than the natural
word size. Everything else is efficient even though everything else
also needs to handle values larger than the natural word size. Yes,
makes sense. Or then not.

  Besides, not everything *has* to be reference-counted.

> Most 
> reference-counted systems allocate between five and eight bits for 
> reference counts.

  Doesn't sound like a very smart thing to do. Sounds like over-optimization.

> Incidentally, that's another reason reference counting 
> isn't used much - the size penalty.

  And incidentally many (most? all?) garbage-collected languages will force
every single class to be allocated dynamically (which will add at the
very least the type or size of the object to be stored alongside it
so that it can be properly freed), which in turn forces every object
to be handled through at least one reference (which will add the size
of a pointer to the total memory consumption of the object), plus they
also usually automatically make every object dynamically bound (which
will add at least the size of some kind of pointer to the total memory
consumption of the object).
  Even by a rather conservative estimate we could estimate that each
object requires at least 12 bytes of overhead in such a language. But
of course that is nothing to worry about. The size of a reference count
on the other hand is something to be very worried about.

-- 
                                                          - Warp

Post a reply to this message

> Orchid XP v3 <voi### [at] devnull> wrote:
> > I think he's hinting that finding the right pivot is the "hard" part
> > of the algorithm, and if you get that wrong you get poor
> > performance...
> 
> But that doesn't make quicksort a bad sorting algorithm.

Exactly. So, the lesson we learn from this is the following: An
algorithm or system for which you have to work hard to avoid
pathological cases can still be useful.

Now, if we remember the above, and apply it to Andy's statement:

> I have no idea why after all these years people still think reference 
> counting is a good idea. It's so trivial to find an example where it 
> utterly fails...

then it is easy to see why after all these years people still think
reference counting is a good idea.

I thought my original reply was both concise and clear, but maybe I was
the only one to think that.

It is often said in teaching that if you tell someone something he'll
forget it almost immediately, but if you make him work it out for
himself he will remember for longer.

-- 
"Listen to your users, but ignore what they say." - Nathaniel Borenstein
http://surreal.istic.org/          Calm down, it's only ones and zeroes.

Post a reply to this message

Warp wrote:
>   Oh, of course handling more data than the natural pointer size of the
> system is very efficient. It's just the reference counter which is
> inefficient because it has to be able to count more than the natural
> word size. Everything else is efficient even though everything else
> also needs to handle values larger than the natural word size. Yes,
> makes sense. Or then not.

Thank you for that lovely strawman.

>   Besides, not everything *has* to be reference-counted.

Um, yes?  So?   You're correct: Where something isn't reference-counted, 
the size of the reference counter adds no overhead.

>>Most 
>>reference-counted systems allocate between five and eight bits for 
>>reference counts.

>   Doesn't sound like a very smart thing to do. Sounds like over-optimization.

When you're trying to put 20,000 objects into 64K of ram, yes, it's 
actually quite a smart thing to do.

>>Incidentally, that's another reason reference counting 
>>isn't used much - the size penalty.
> 
>   And incidentally many (most? all?) garbage-collected languages will force
> every single class to be allocated dynamically

Only semantically.

> (which will add at the
> very least the type or size of the object to be stored alongside it
> so that it can be properly freed)

Only if the semantics of the language aren't already requiring that 
information.

>, which in turn forces every object
> to be handled through at least one reference (which will add the size
> of a pointer to the total memory consumption of the object)

That would be incorrect.

>, plus they
> also usually automatically make every object dynamically bound (which
> will add at least the size of some kind of pointer to the total memory
> consumption of the object).

That would also be incorrect.

>   Even by a rather conservative estimate we could estimate that each
> object requires at least 12 bytes of overhead in such a language.

Your ignorance of modern technology in this field is showing.

> of course that is nothing to worry about. The size of a reference count
> on the other hand is something to be very worried about.

I didn't say they weren't something to be worried about. I said that 
it's *a* thing to be worried about.

Reference counting doesn't solve the problem of knowing when to collect 
the garbage. It's inefficient in both time and space, it causes 
unpredictable performance by requiring large amounts of time to free 
arbitrarily large structures all at once due to cascading reference 
counts going to zero, and virtually nobody who knows anything about 
garbage collection uses it anymore.

That you could design a system that's even *more* inefficient than 
reference counting by not having followed the research over the last 20 
years or so of how to do things right should surprise nobody.

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message

Warp wrote:
>   It's impossible for a reference counter to overflow.

Unless your reference counter is smaller than the size of a pointer. 
Yes, you can build a reference counting system that doesn't overflow, by 
allocating a huge amount of space to a counter that is usually less than 
4 bits. But since you *still* need some other sort of garbage collection 
anyway, why would you waste that much space?

>>You can allocate 100,000 individual objects and 
>>free them all with one instruction.
> 
>   Assuming no memory fragmentation, of course.

How do you think allocation in a garbage collected system works? Of 
*course* there's no fragmentation.

>   Besides, a reference-counting system doesn't have to *free* the
> objects immediately when the last reference dies. It can mark the
> object as "to be freed" and put it somewhere to wait.

Um, why would it have to "put it somewhere"? The problem isn't "freeing 
the object". The problem is running through all the pointers in the 
object whose reference went to zero and marking those as freed also.

Once you do what you describe, then you've lost the simplicity of 
reference counting, and now you're doing some other sort of garbage 
collection. (Which sort depends on how/when you free the objects.)

And you still haven't solved the major problem, which is that reference 
counting DOES NOT WORK.  Reference counting, even with sufficiently 
large counters, does not free all the garbage, even if you do it 
inefficiently.

>   Btw, how does the GC engine know that the object is not used anymore?

There are a number of ways, from simplistic to convoluted. Generally, GC 
engines assume they can find the live pointers.

If you're actually interested in the topic, there are good references 
freely available. If you're just interested in arguing, I'm not.

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message

Darren New wrote:
> Most reference-counted systems allocate between five and eight bits for
> reference counts.

Care to provide some credible links/evidence for this claim? It is new to
me, and probably 99% of those using reference counting...

	Thorsten

Post a reply to this message

Thorsten Froehlich wrote:
> Care to provide some credible links/evidence for this claim?

Smalltalk-80: The Language and Implementation. Or look into any LISP 
implementation.

As for a newer reference? Not too many around, as people don't use 
reference counting seriously, because it's so flawed. Providing newer 
references would be like providing references for bad cache coherency 
performance of bubble sorts.

 > It is new to
> me, and probably 99% of those using reference counting...

There's a difference between "a reference-counted garbage-collection 
system" and "a program using reference counting."  Certainly, if you 
implement it yourself and you have full control over every way you're 
going to use it and you don't allocate enough objects that the added 
overhead is worth avoiding, then you can use a big counter. People who 
build systems that include GC for others to use generally don't get that 
luxury. Indeed, people that build systems that include GC generally 
don't use reference counting at all, as it (along with mark/sweep) is 
pretty much the most primitive lamest inefficient version of GC 
possible. But sure, if you're limited by what you can implement in C or 
C++ at the application level, it's not too bad, as long as you remember 
to manually break cycles everywhere and you're not trying to make it fast.

-- 
   Darren New / San Diego, CA, USA (PST)
     Just because you find out you are
     telepathic, don't let it go to your head.

Post a reply to this message