Front page | perl.perl6.internals |
Postings from April 2005
At 10:55 PM -0400 4/28/05, Bob Rogers wrote:
> From: Robin Redeker <robin@nethype.de>
> 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 <dan@sidhe.org>
> 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
dan@sidhe.org have teddy bears and even
teddy bears get drunk
Thread Previous
|
Thread Next