Question from a non-user: Garbage Collection
in [Lisp]
|
Prev: TPS
Next: Style, or lack thereof in Graham's ANSI CL
From: George Neuner on 18 Dec 2009 18:57 On Fri, 18 Dec 2009 21:27:17 +0000 (UTC), Kaz Kylheku <kkylheku(a)gmail.com> wrote: >On 2009-12-16, George Neuner <gneuner2(a)comcast.net> wrote: >> On Wed, 16 Dec 2009 18:04:14 +0000 (UTC), Kaz Kylheku >><kkylheku(a)gmail.com> wrote: >> >>>Refcounting can't be deferred, >> >> There are lazy refcounters which defer recycling until the memory is > >But do they defer the counting? The actual bumping up and down of refcounts? >That's a cost. With compiler cooperation, count manipulation can be elided in many circumstances. For example, temporary references that exist under strict stack semantics do not require object counter updates as they come and go. There's a family of so-called "one-bit" refcounters in which the count is really just a "share" flag which can be in the reference rather than attached to the object. The flag is set in both old and new references whenever a reference is copied but the object need not be touched at all. These refcounters are used successfully in hybrid systems with a backup tracer and are effective where non-shared objects are expected to be the norm. Some variants expand the idea to keep a few bits of counter in references and use the tracer only if the count becomes pinned. >My point was that in short-lived programs, GC has zero cost, because it never >happens, and the program code itself contains vanishingly few traces of >anything that caters to the task of memory management. > >Recounting programs have to always be refcounting. The code to do so is >compiled in. If you want a refcounted program to have zero overhead in cases >where it is expected to be short lived, you have to compile a separate image of >that program, in which the inline refcounting instructions are removed. Technically, refcounting is a form of GC. I have no argument, I'm just providing additional information. George
From: Kaz Kylheku on 19 Dec 2009 02:48 On 2009-12-18, George Neuner <gneuner2(a)comcast.net> wrote: > On Fri, 18 Dec 2009 21:27:17 +0000 (UTC), Kaz Kylheku ><kkylheku(a)gmail.com> wrote: > >>On 2009-12-16, George Neuner <gneuner2(a)comcast.net> wrote: >>> On Wed, 16 Dec 2009 18:04:14 +0000 (UTC), Kaz Kylheku >>><kkylheku(a)gmail.com> wrote: >>> >>>>Refcounting can't be deferred, >>> >>> There are lazy refcounters which defer recycling until the memory is >> >>But do they defer the counting? The actual bumping up and down of refcounts? >>That's a cost. > > With compiler cooperation, count manipulation can be elided in many > circumstances. > > For example, temporary references that exist under > strict stack semantics do not require object counter updates as they > come and go. Yes, been there done that; in C++ you can express it directly like this: void function(const ref_type &objref) { } I.e. pass the refcounted smart pointer by reference binding, rather than by value. This doesn't require special compiler cooperation; only that it implement C++ references properly.
From: Pascal J. Bourguignon on 19 Dec 2009 05:47 George Neuner <gneuner2(a)comcast.net> writes: > On Fri, 18 Dec 2009 21:27:17 +0000 (UTC), Kaz Kylheku > <kkylheku(a)gmail.com> wrote: > >>On 2009-12-16, George Neuner <gneuner2(a)comcast.net> wrote: >>> On Wed, 16 Dec 2009 18:04:14 +0000 (UTC), Kaz Kylheku >>><kkylheku(a)gmail.com> wrote: >>> >>>>Refcounting can't be deferred, >>> >>> There are lazy refcounters which defer recycling until the memory is >> >>But do they defer the counting? The actual bumping up and down of refcounts? >>That's a cost. > > With compiler cooperation, count manipulation can be elided in many > circumstances. For example, temporary references that exist under > strict stack semantics do not require object counter updates as they > come and go. > > There's a family of so-called "one-bit" refcounters in which the count > is really just a "share" flag which can be in the reference rather > than attached to the object. The flag is set in both old and new > references whenever a reference is copied but the object need not be > touched at all. These refcounters are used successfully in hybrid > systems with a backup tracer and are effective where non-shared > objects are expected to be the norm. Some variants expand the idea to > keep a few bits of counter in references and use the tracer only if > the count becomes pinned. The compiler can also help the garbage collector, as well as the programmer (declare (dynamic-extent ...)). -- __Pascal Bourguignon__ http://www.informatimago.com/ Wanna go outside. Oh, no! Help! I got outside! Let me back inside!
From: Tim Bradshaw on 19 Dec 2009 07:25 On 2009-12-18 22:58:55 +0000, Kaz Kylheku <kkylheku(a)gmail.com> said: > That's right. Suppose P to a root object R is the program's last reference to a > huge DAG of millions of objects rooted at R. When the program, through pointer > P, drops its last reference on R, the entire DAG becomes garbage. What this > means is that each object in the DAG is visited, and its refcount is dropped. > > So this action may cause a drastic pause in the execution of the program: > the very kind of pause that garbage collection is accused of, and which > refcounting is supposed to eliminate. Interlisp-D was a reference-counted implementation. It had exactly this problem: when you dropped some large object the machine would go away for hours. It was usually easier just to reboot.
From: Vend on 19 Dec 2009 14:20
On Dec 16, 7:21 pm, Tamas K Papp <tkp...(a)gmail.com> wrote: > On Wed, 16 Dec 2009 18:04:14 +0000, Kaz Kylheku wrote: > > Without cycles, you can't express graph structures, so an entire branch > > of computer science goes out the window. Many useful algorithms > > I disagree. Graphs can be represented, for example, in a matrix > (a[i,j] is nonzero iff i->j, etc). You can use this to reconstruct a > lookup table, basically emulating pointers. > > Which would, of course, would be a pretty pointless thing to do -- but > the OP's questions have been pretty pointless so far, so maybe this > would be a harmonious outcome :-) Or you could use lazy evaluation in order to create infinite periodic graphs equivalent to cyclic graphs. I think this is the main reason why pure functional langages strongly support lazy evaluation. |