Question from a non-user: Garbage Collection
in [Lisp]
|
Prev: TPS
Next: Style, or lack thereof in Graham's ANSI CL
From: William D Clinger on 16 Dec 2009 13:36 Duane Rettig provided an excellent answer to the original post. Kaz Kylheku wrote: > Refcounting can't be deferred, A Google search on "deferred reference counting" would provide more reliable information. Will
From: Helmut Eller on 16 Dec 2009 13:40 * Bennu Strelitzia [2009-12-16 15:31+0100] writes: > Is there a flavor of lisp that due to immutability of structures makes > referential cycles impossible, eliminating a requirement for full-blown GC? Not really a Lisp, but Erlang seems to fit the bill. All data structures in Erlang are immutable and "updates" are done by copying. Not sure what the difference between full-blown vs. non-full-blown GC could be, but Erlang has a generational GC. The absence of mutable objects allows some simplifications (no write barriers, no old-to-new pointers) and unsurprisingly Erlang's GC exploits those features. Helmut
From: Pillsy on 16 Dec 2009 14:29 On Dec 16, 1:04 pm, Kaz Kylheku <kkylh...(a)gmail.com> wrote: > On 2009-12-16, Bennu Strelitzia <bennu.strelit...(a)gmail.com> wrote: > > i.e. reference counting could do the trick for an efficient minimal > > implementation if there were no referential cycles, I hate the real > Reference counting is not efficient. Except in some highly contrived > benchmarks that don't reflect real-world use, it is slower than garbage > collection. Even simple mark-and-sweep can beat reference counting in > realistic situations. The following is a very naive observation. The one thing it seems like reference counting could allow you to do is immediate recycling of space. For example, if I want to sum two vectors, using (map 'vector #'+ a-big-vector another-big-vector) I'll get a third big vector that has to be consed. If I know that A- BIG-VECTOR isn't being used by anything else, I can recycle it using MAP-INTO instead, but in general I have no idea. However, if there were a reference count on those big vectors, the implementation could make the decision for me at run-time. I'm primarily thinking of using using reference counting as a way of augmenting garbage collection, not as a replacement for it; indeed, you could limit it to only work with some data types or objects, like big simple arrays of floats or characters. There's no way this is a new idea, and it's entirely possible I'm overlooking some trade-offs that keep it from being worthwhile. Cheers, Pillsy
From: George Neuner on 16 Dec 2009 15:03 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 reallocated, but in terms of complexity all refcounters do more work than tracing forms of GC. George
From: Rahul Jain on 16 Dec 2009 17:27
Kaz Kylheku <kkylheku(a)gmail.com> writes: > Every time an object's refcount is modified, an entire cache line > becomes dirty and has to be flushed to main memory. When another > processor in the system wants to access anything which lands in that > cache line, having noticed that it's dirty, it has to fetch the latest > version of that cache line from main memory. This means that two or > more processors can't work with the same refcounted object in a way that > is scalable, if at all they touch the refcounts---even if they are > treating the objects as read-only! As the refcounts are bumped, you have > performance-wasting cache ping-pong, and this can happen even with > separate objects (false sharing) if they land wholly or partially into > the same cache line. Refcounts have to be updated in a thread-safe way, > using expensive atomic operations that can cause stalls of thousands of > cycles. The consequences is that a refcounted program simply will not > scale well to a multiprocessor system. Thanks, Kaz. I hadn't even thought of that issue. It's a huge one for modern programs! -- Rahul Jain rjain(a)nyct.net Professional Software Developer, Amateur Quantum Mechanicist |