From: Robin Redeker <[EMAIL PROTECTED]> Date: Thu, 28 Apr 2005 00:12:50 +0200 Refcounting does this with a little overhead, but in a fast and deterministic O(1) way.
This is the first half of an apples-to-oranges comparison, and so is misleading even if partly true. Refcounting may be proportional (approximately) to the amount of reference manipulation, but GC is proportional (though even more approximately, and with a different constant) to the amount of memory allocated [1].
Actually it's proportional to the number of live objects.
A refcounting scheme has to touch *all* objects at least twice, while a tracing scheme generally has to touch only the objects that are live at trace time. For the most part, refcount O(n) time is proportional to the total number of objects created, while tracing O(n) time is proportional to the number of live objects.
It's definitely possible to work up degenerate examples for both refcount and tracing systems that show them in a horribly bad light relative to the other, but in the general case the tracing schemes are significantly less expensive.
From: Dan Sugalski <[EMAIL PROTECTED]> Date: Thu, 28 Apr 2005 13:10:00 -0400
. . .
>I don't think circular references are used that much. This is maybe >something a programmer still has to think a little bit about. >And if it means, that timely destruction maybe becomes slow only for the >sake of collecting circular references... don't know if thats a big >feature.
Circular references are far more common than objects that truly need timely destruction, yes, and the larger your programs get the more of an issue it is. Neither are terribly common, though.
I'm astounded. Do neither of you ever design data structures with symmetrical parent<->child pointers? No trees with parents? No doubly-linked lists? In my (probably skewed) experience, circular references are used frequently in languages like C or Lisp that don't penalize them.
I responded to Uri on this, but note that I said "neither are terribly common", and they aren't. Relative to the total number of GC-able things, objects in circular structures are a very small minority. Which, of course, doesn't help much as an app designer when you have to deal with these things, but it is important to know when doing the design of the back end, since relative usage of features needs to be kept in mind when making design tradeoffs. One of those annoying engineering things. (Just once I'd love to have my cake *and* eat it too, dammit! :)
--
Dan
--------------------------------------it's like this-------------------
Dan Sugalski even samurai
[EMAIL PROTECTED] have teddy bears and even
teddy bears get drunk
