From: Dan Sugalski <[EMAIL PROTECTED]>
Date: Fri, 29 Apr 2005 15:23:47 -0400
At 10:55 PM -0400 4/28/05, Bob Rogers wrote:
> 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.
When running a sweep, yes, but the frequency of sweeping is in turn
proportional to the rate at which new memory is allocated, depending of
course on GC settings. So the overall cost is proportional to the
product, which (and this was my point) can be effectively zero for some
programs some of the time [1].
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.
That is true for a copying GC, but a mark/sweep GC also needs to visit
both the quick and the dead during the sweep phase in order to free
them.
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.
But you have to increment/decrement/test the refcount each time you pass
a refcounted object to a sub, don't you? So that makes the cost of
refcounting proportional to runtime, doesn't it? (I don't know how
Perl5 does it in detail.)
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.
Agreed.
>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.
I can think of many programs I've written or otherwise hacked on where
this is not the case. In some cases, the majority of objects are
directly circular (i.e. part of a cycle as opposed to being referenced
from an object in a cycle). But I suppose that just means that we've
worked on very different apps. Before Perl5, I used to use parent
pointers at the drop of a hat. But, 'nuff said, I guess.
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
In engineer heaven, perhaps. "RePentium, and ye shall be saveall'ed!"
;-}
-- Bob
[1] This was commonly true of programs written for the early Lisp
Machines; programmers tried really hard to avoid allocation of
short-term garbage, since real memory was expensive and GC was
painfully slow.
