Question from a non-user: Garbage Collection
Bennu Strelitzia
will make separate postings abput. Sorry if they are obvious or
otherwise-unsuitable questions, but I have spent some time reading
trying to answer them and have not been able to do so.
What I would wish for in garbage collection in Lisp:
Is there a flavor of lisp that due to immutability of structures makes
referential cycles impossible, eliminating a requirement for full-blown GC?
i.e. reference counting could do the trick for an efficient minimal
implementation if there were no referential cycles, I hate the real
weight of every full-blown GC I have ever seen in a language in spite of
all the "wisdom" that claims that it is not a problem. I love nothing
better than a simple C program that can run very fast start to finish in
a few K of space, and dislike how impossible most GC schemes seem to
make this, in my experience.
I also happen to really like the model that every mutation to a
structure creates a new structure sharing applicable read-only parts of
the old structure, making many things inherently more concurrency-safe,
so it seems like the two things would go hand in hand, because if each
mutation of a structure creates a new structure, then you have no
opportunity for a reference loop because any structure can only refer to
objects older than itself.
I have read that Clojure likes this sort of immutability in collections,
but unfortunately it is stuck with the Java garbage collector. Is this
something another Lisp might address without the fatness of a JVM or
other full-blown GC?
Bennu
Rahul Jain
> Is there a flavor of lisp that due to immutability of structures makes
> referential cycles impossible, eliminating a requirement for full-blown GC?
Look at haskell. It doesn't have lisp syntax, tho, and the way it deals
with the fact that the real world has state makes it a bit arcane for
writing complex applications.
> i.e. reference counting could do the trick for an efficient minimal
> implementation if there were no referential cycles, I hate the real
> weight of every full-blown GC I have ever seen in a language in spite of
> all the "wisdom" that claims that it is not a problem. I love nothing
> better than a simple C program that can run very fast start to finish in
> a few K of space, and dislike how impossible most GC schemes seem to
> make this, in my experience.
Refcounting uses more space and takes more CPU time to do in a purely
functional language. Garbage collection does not take time, it is
collection of non-garbage. In a language without side-effects, you will
generate a lot of garbage, so you want to optimize for the garbage case.
This means not using refcounting.
--
Rahul Jain
rj...@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
Duane Rettig
wrote:
> I would appreciate any pointers you may have on a few issues which I
> will make separate postings abput. Sorry if they are obvious or
> otherwise-unsuitable questions, but I have spent some time reading
> trying to answer them and have not been able to do so.
Likely because those who use modern Lisps simply don't find a need to
discuss it, because it is seldom a problem, and when it is it is
something to discuss with their Lisp vendor rather than publicly.
However, it is a perfectly fine question, so I'll attempt to answer
it.
> What I would wish for in garbage collection in Lisp:
>
> Is there a flavor of lisp that due to immutability of structures makes
> referential cycles impossible, eliminating a requirement for full-blown GC?
When you say "full-blown GC", it makes me think that you are likely
unaware of recent (within the last 30 years) developments in garbage-
collection. Depending on what you mean by "full-blown", generational
garbage-collectors have been the norm for many years, now, and almost
never have to work on the whole heap. The theory is that most data
are either short-lived or long-lived, and so if the gc works mostly on
the long-lived data, it can be most efficient.
> i.e. reference counting could do the trick for an efficient minimal
> implementation if there were no referential cycles, I hate the real
> weight of every full-blown GC I have ever seen in a language in spite of
> all the "wisdom" that claims that it is not a problem. I love nothing
> better than a simple C program that can run very fast start to finish in
> a few K of space, and dislike how impossible most GC schemes seem to
> make this, in my experience.
A C program can indeed run very fast with very little space, and it
will do very little (this is not a pejorative statement - it may be
that the task only requires a little bit of work). Lisps can do this
as well, and most lisps provide the ability to move aside the gc
activity in favor of all-out speed for the task. In practice, this
does not occur so often, because Lisp users like to have their lisps
available for long periods of time for many different tasks, and
because the GCs on these Lisps really aren't a problem (because they
tend to do only the work that's needed) they tend to keep their Lisps
running for longer periods of time, and put up with the percent or two
of gc time.
But back to your C analogy: once you start getting into larger tasks,
data driven and using malloc/free, you are suddenly up against the
same wall as every other language: "how do I manage my heap space?"
and C doesn't do it very well. First, since malloc/free are manually
managed, there is a lot of potential for user error, and many C
program bugs are seen due to use of already-deallocated memory (there
are even whole systems like Purify geared to precisely this problem).
Secondly, your version of malloc/free, or its current
parameterization, will determine whether it runs slowly or wastes
memory. If it set to use a "best fit" algorithm, it will have to take
malloc time to search for the best fit for the request, and it will
also take time, either at malloc time or at free time, to coalesce
multiple free blocks. At the other end of the scale, a bucket-style
malloc might have powers-of-two sized blocks given to the user, even
if the request was just larger than the next power-of-two smaller.
There is therefore a huge potential for space waste.
> I also happen to really like the model that every mutation to a
> structure creates a new structure sharing applicable read-only parts of
> the old structure, making many things inherently more concurrency-safe,
> so it seems like the two things would go hand in hand, because if each
> mutation of a structure creates a new structure, then you have no
> opportunity for a reference loop because any structure can only refer to
> objects older than itself.
STM is indeed a powerful tool, but it is a hammer that forces you to
shape your nails like STM nails. If you can do that, then great; your
job is done if you find an STM system (Clojure is just such a system,
as you mention below). But if your problem does not fit as easily
into the STM model, then you have to deal with that fact and use tools
that solve your problem. (note that Clojure may also have these
tools, but since I am not a Clojure advocate, I'll let someone who is
put in any plugs for it).
> I have read that Clojure likes this sort of immutability in collections,
> but unfortunately it is stuck with the Java garbage collector. Is this
> something another Lisp might address without the fatness of a JVM or
> other full-blown GC?
Many other Lisps take the following philosophy:
1. JVM is here to stay, and thus we must be able to work with it. We
do this via inter-language communication techniques, including in some
cases generating Java byte codes, but in other cases simply using RPC
style communication with JVM.
2. JVM is not everything, and we can generally get much more
efficient code generation and heap management by taking on the task
ourselves.
As for concurrency, most of the Lisp vendors are working on or have
concurrency models, with or without STM, based on the needs of their
user base. You should do some shopping, and find the one that suits
your needs. You haven't stated any needs in your post here, so it
will be up to you to decide whether a particular Lisp suits your needs
or not. As for the fear you've expressed that the Lisp GCs would be
"full-blown", implying that they are inefficient and/or will cause
noticeable pauses in your program's operation, I say try some for
yourself, and become pleasantly surprised at how little most Lispers
even think about their Lisp's garbage-collector.
Duane
Kaz Kylheku
> 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.
Refcounting does not eliminate ``pauses'' from the program execution.
If you drop the last reference on an object which is itself the last
reference a large number of other objects, this triggers a cascade of
refcounts dropping to zero, which takes time to complete.
Refcounting can't be deferred, so even a short-lived program whose heap
is cleaned up by the operating system has to waste cycles on
refcounting, whereas the program with GC wins simply by never invoking
GC over its lifetime.
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.
Cycles can't be avoided in Lisp as easily as you might think because of
lexical closures. Closure environments are mutable, because variables
are assignable, and can easily generate cycles.
;; cycle created: lexical varible fun points to
;; the closure, and is captured by it at the same time:
(setf fun (lambda () ...))
So what you have to do is banish all variable assignment.
Without cycles, you can't express graph structures, so an entire branch
of computer science goes out the window. Many useful algorithms
call for graphs. You can't compile a regular expression to an NFA using
standard algorithms without generating a graph. So with refcounting
you need hacks, like the use of some uncounted backreferences, or
maintaining the structure completely outside of the managed memory.
Tamas K Papp
> 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 :-)
Cheers,
Tamas
William D Clinger
post.
Kaz Kylheku wrote:
> Refcounting can't be deferred,
A Google search on "deferred reference counting" would
provide more reliable information.
Will
Helmut Eller
> 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
Pillsy
> On 2009-12-16, Bennu Strelitzia <bennu.strelit...@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
George Neuner
<kkyl...@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
Rahul Jain
> 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!
Pascal J. Bourguignon
Without mutation, arrays become a O(N) affair, there's no sharing of
slots amongst arrays... So building such a matrix will be rather costly.
--
__Pascal Bourguignon__
http://www.informatimago.com
Pascal J. Bourguignon
Basically, you're overlooking the performance of generationnal GC.
Allocating even a big number of temporaty structure is basically free,
both in allocation and in garbage collecion, since only the objects that
are kept will cost some work to the garbage collector.
George Neuner
wrote:
Refcounters (even lazy ones) eventually have to scan all the garbage
blocks. Scavengers (semi-space, generational, etc.) scan only live
data. Because they move/compact live data at each collection,
scavengers can use sequential "bump" allocation which is just a
pointer or index increment and limit check rather than block
splitting/coalescing and list manipulation. The combination of near
free allocation and ignoring garbage blocks means that temporary
allocations which don't trigger a collection are essentially free.
Refcounters have a slight advantage overall in terms of data locality
and also have an advantage in low memory conditions. However
scavengers typically size young object regions so as to fit completely
within the CPU cache - making for very fast incremental collections.
Generational systems are designed with the assumption that temporary
objects are expected to die quickly. The longer data survives the
less frequently it will be subjected to collection.
George
Barry Margolin
From http://www.haskell.org/tutorial/arrays.html:
Obviously, a naive implementation of such an array semantics would be
intolerably inefficient, either requiring a new copy of an array for
each incremental redefinition, or taking linear time for array lookup;
thus, serious attempts at using this approach employ sophisticated
static analysis and clever run-time devices to avoid excessive copying.
--
Barry Margolin, bar...@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
*** PLEASE don't copy me on replies, I'll read them in the group ***
Rahul Jain
> Without mutation, arrays become a O(N) affair, there's no sharing of
> slots amongst arrays... So building such a matrix will be rather costly.
O(log N) is pretty trivial to achieve... just use a tree.
Kaz Kylheku
If we have a graph structure, it means that given some node object N, we can
navigate to some adjancent object. For instance if the edges are numbered from
zer0, we can call a function like (neighbor N 3) to obtain the fourth neighbor
of N.
In order to be able to do this with the matrix representation, the object
N has to have a backpointer to the matrix. And that creates the
cyclical reference at the storage level: N points to the array, and the array
contains N somewhere.
The only way you can eliminate the circularity is if the nodes do not know who
their neighbors are (do not have a backreference to the matrix). But that's a
different kind of graph then.
I don't want to be constrained into working only with that kind of graph, just
because my memory management is dumb.
Kaz Kylheku
> On Wed, 16 Dec 2009 18:04:14 +0000 (UTC), Kaz Kylheku
><kkyl...@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.
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.
Kaz Kylheku
Your idea depends on the assumption that ``it is a big deal that a large
vector has been allocated for temporary use and is now garbage.''
Why is that a big deal?
A larger vector is no more difficult to hunt down and reclaim than a
small vector. How vectors can be implemented is that they are small control
records which are themselves in a garbage-collected heap, but the vector data
is in an ordinary heap that isn't garbage-collected. So then it's a large
/number/ of vectors that contributes to GC times, rather than large vector
size. Under this representation, when we allocate a vector, that only
contributes a small record to the garbage collected heap which must be
traversed in preparation for marking, and then traversed again to sweep it for
unreachable objects.
So the remaining reason why we might be concerned about a large vector being
garbage is that we are holding on to a large amount memory longer than
necessary, preventing it from being used elsewhere.
This can be solved without reference counting. Simply provide an operation
which lets the program explicitly shrink the vector. If a ten million element
vector is reduced to size zero (or to a tiny, nonzero size, like 1), the memory
can be reclaimed instantly.
A shrunk vector is better than one which is prematurely deleted, because it
isn't garbage. It's safe. The worst that can happen is that some code thinks
that the vector is larger than it really is; but that only results in
out-of-bounds array references, which can be checked. We can disallow
direct interior pointers into vector data, such that everything goes through
indexing which is checked agains size (even displaced-to arrays).
Kaz Kylheku
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.
Kaz Kylheku
Here is another one. The most naive garbage collection has a sweep phase. But
let me present an argument that this sweep phase is better than refcounting.
Whenever refcounting reclaims an object, it is because a refcount has reached
zero. These zero refcounts are discovered dynamically by chasing the references
among objects: essentially, the order in which objects are discovered to be
unreachable is random.
What's worse, sometimes refcounted objects are shared. An unreachable object
may have a refcount that is greater than one, and has to be visited that many
times before its count drops to zero. These visits may be spread apart such
that the object is evacuated from the cache and fetched again.
Under mark-and-sweep naive GC, objects are discovered to be unreachable in a
nice, predictable order: they are visited by marching a pointer through the
heap (often, a heap of identically-sized objects, like conses, or the header
records of vectors, etc). Each object is visited once. It is discovered that it
was not marked with the ``reachable'' flag, and so its is updated in some way
to recycle it.
Marching through memory in a linear way is something that processors can do
fast.
Firstly, we avoid fetching any of the data into the L1 cache more than once,
since we are making one pass. Secondly, the access pattern is such that it is
susceptible to speedup by prefetching. Some modern processors have L2 to L1
prefetch, which is similar to prefetching the blocks of a file, under the
assumption that it's being sequentially accessed. This means that while you are
working with one cache line full of data, the processor can be generating the
cache refill for the next one.
Secondly, on some processors, there are cache hint instructions: you can tell
the processors that you exepect to be accessing a particular address. If
you're sweeping through objects in a linear heap, you know the address of any
number of objects in advance by simple pointer arithmetic. Using cache hints,
we can tell the processor to load several cache lines ahead.
If you're traversing objects under refcounting, you can generate a cache hinit
only for the immediately reachable objects. To get any objects which are two
hops away, you have to load the first-hop objects into the cache, check
their type, so you know where their references are.
Thirdly, small objects are packed several to a cache line. If your processor
has 64 byte L1 cache lines, and you have 8 byte conses, you get 8 conses
to a cache line. It's much faster to access several object in the same cache
line, than several objects all over the place. This is similar to traversing a
disk-based database in record-bucket order, compared to fetching records in
random order.
Fourth, DRAM memories support burst mode access, which works only for
consecutive addresses. The memory bandwidth of linear access is much faster
than that of random access. Burst mode allows fast main memory -> L2 cache
fills. Again, works in your favor if you're linearly scanning. We have had
decently high resolution displays with decent refresh rates, even in the dark
ages of slow memory with 1000 nanosecond + access times. High resolution video
memories have for decades demonstrated that predictable, linear access to
memory can be trivially optimized with a bit of parallelism, and a high
bandwidth can be achieved even though the latency of random accesses is high.
Summary: visiting dead objects random order with refcounting: bad. Dumb sweep
through dead objects in address order: better.
George Neuner
<kkyl...@gmail.com> wrote:
>On 2009-12-16, George Neuner <gneu...@comcast.net> wrote:
>> On Wed, 16 Dec 2009 18:04:14 +0000 (UTC), Kaz Kylheku
>><kkyl...@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
Kaz Kylheku
> On Fri, 18 Dec 2009 21:27:17 +0000 (UTC), Kaz Kylheku
><kkyl...@gmail.com> wrote:
>
>>On 2009-12-16, George Neuner <gneu...@comcast.net> wrote:
>>> On Wed, 16 Dec 2009 18:04:14 +0000 (UTC), Kaz Kylheku
>>><kkyl...@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.
Pascal J. Bourguignon
> On Fri, 18 Dec 2009 21:27:17 +0000 (UTC), Kaz Kylheku
> <kkyl...@gmail.com> wrote:
>
>>On 2009-12-16, George Neuner <gneu...@comcast.net> wrote:
>>> On Wed, 16 Dec 2009 18:04:14 +0000 (UTC), Kaz Kylheku
>>><kkyl...@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!
Tim Bradshaw
> 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.
Vend
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.
George Neuner
<kkyl...@gmail.com> wrote:
True, but I'm not assuming the compiler targets C++ ... strict stack
semantics allow for any pointer-like representation to elide reference
counts for temporaries in any language.
George
Vend
> Refcounting does not eliminate ``pauses'' from the program execution.
> If you drop the last reference on an object which is itself the last
> reference a large number of other objects, this triggers a cascade of
> refcounts dropping to zero, which takes time to complete.
You can defer deallocation, or run it concurrently in another thread.
> Refcounting can't be deferred, so even a short-lived program whose heap
> is cleaned up by the operating system has to waste cycles on
> refcounting, whereas the program with GC wins simply by never invoking
> GC over its lifetime.
Many hybrid approaches defer counter updates.
> So what you have to do is banish all variable assignment.
Reference cycles can be handled in a reference counted memory
mangagment system too.
When an object reference count drops to a non-zero value, you put it
in a set that is periodically scanned by a cycle detector.
> Without cycles, you can't express graph structures, so an entire branch
> of computer science goes out the window.
You can do that using lazy evaluation.
Tim Bradshaw
>> [...]
> You can defer deallocation, or run it concurrently in another thread.
> Many hybrid approaches defer counter updates.
> Reference cycles can be handled in a reference counted memory
> mangagment system too.
> When an object reference count drops to a non-zero value, you put it
> in a set that is periodically scanned by a cycle detector.
> You can do that using lazy evaluation.
Or in other words: you can make a reference counting system do a lot of
what GC'd system does anyway, except for the toxic
look-at-all-the-dead-objects-thus-trashing-the-cache stuff.
Alternatively, you could, you know, use a garbage collector.
--tim
Vend
Reference counting memory managment is a form of garbage collection.
Possibly you mean tracing garbage collection, which either sweeps dead
objects or moves live objects around the heap, in both cases affecting
caching performance.
Tim Bradshaw
> Reference counting memory managment is a form of garbage collection.
That depends on who you ask, of course.
>
> Possibly you mean tracing garbage collection, which either sweeps dead
> objects or moves live objects around the heap, in both cases affecting
> caching performance.
Yes. I suspect copying collectors have rather good cache behaviour,
since they almost inevitably mean that (some of) the live data is
cached after the GC has run. Anything that spends its time walking all
over dead data is kind of inherently awful.
Kaz Kylheku
> On Dec 16, 7:04 pm, Kaz Kylheku <kkylh...@gmail.com> wrote:
>
>> Refcounting does not eliminate ``pauses'' from the program execution.
>> If you drop the last reference on an object which is itself the last
>> reference a large number of other objects, this triggers a cascade of
>> refcounts dropping to zero, which takes time to complete.
>
> You can defer deallocation, or run it concurrently in another thread.
>
>> Refcounting can't be deferred, so even a short-lived program whose heap
>> is cleaned up by the operating system has to waste cycles on
>> refcounting, whereas the program with GC wins simply by never invoking
>> GC over its lifetime.
>
> Many hybrid approaches defer counter updates.
Hybrid means that you have a puzzlingly pointless mix of real garbage
collection, and a dumb reference counting hacks.
>> So what you have to do is banish all variable assignment.
>
> Reference cycles can be handled in a reference counted memory
> mangagment system too.
If you can do this, there is no reason not to implement normal garbage
collection. People use reference counting hacks because they don't have
the support from the language to be able to implement proper gc.
> When an object reference count drops to a non-zero value, you put it
> in a set that is periodically scanned by a cycle detector.
Object reference counts drop to non-zero all the time, so this set is
going to have every object in the system, except for ones with simple
lifetimes that come into life existence with one reference, which
is then dropped.
>> Without cycles, you can't express graph structures, so an entire branch
>> of computer science goes out the window.
>
> You can do that using lazy evaluation.
I don't think so, and suspect that you're confusing implicitly infinite
lazy structures with cyclic structures (which also appear
infinite).
Vend
> On 2009-12-21, Vend <ven...@virgilio.it> wrote:
>
> > On Dec 16, 7:04 pm, Kaz Kylheku <kkylh...@gmail.com> wrote:
>
> >> Refcounting does not eliminate ``pauses'' from the program execution.
> >> If you drop the last reference on an object which is itself the last
> >> reference a large number of other objects, this triggers a cascade of
> >> refcounts dropping to zero, which takes time to complete.
>
> > You can defer deallocation, or run it concurrently in another thread.
>
> >> Refcounting can't be deferred, so even a short-lived program whose heap
> >> is cleaned up by the operating system has to waste cycles on
> >> refcounting, whereas the program with GC wins simply by never invoking
> >> GC over its lifetime.
>
> > Many hybrid approaches defer counter updates.
>
> Hybrid means that you have a puzzlingly pointless mix of real garbage
> collection, and a dumb reference counting hacks.
No argument?
> >> So what you have to do is banish all variable assignment.
>
> > Reference cycles can be handled in a reference counted memory
> > mangagment system too.
>
> If you can do this, there is no reason not to implement normal garbage
> collection. People use reference counting hacks because they don't have
> the support from the language to be able to implement proper gc.
Reference counting is a method that can be used by language compilers/
runtimes to implement proper gc.
> > When an object reference count drops to a non-zero value, you put it
> > in a set that is periodically scanned by a cycle detector.
>
> Object reference counts drop to non-zero all the time, so this set is
> going to have every object in the system, except for ones with simple
> lifetimes that come into life existence with one reference, which
> is then dropped.
As far as I know, statistically most object will have at most one
reference. Since these object can't appear in reference cycles, there
is no need to run the cycle detection algorthm on them.
> >> Without cycles, you can't express graph structures, so an entire branch
> >> of computer science goes out the window.
>
> > You can do that using lazy evaluation.
>
> I don't think so, and suspect that you're confusing implicitly infinite
> lazy structures with cyclic structures (which also appear
> infinite).
Cyclic data structures are substantially equivalent to infinite
periodic data structures.
Kaz Kylheku
> On 2009-12-21 11:22:09 +0000, Vend <ven...@virgilio.it> said:
>
>> Reference counting memory managment is a form of garbage collection.
>
> That depends on who you ask, of course.
If you ask me, no. Reference counting is not garbage collection.
I may have thought so once, but I changed my mind, and I'm still getting
smarter. Therefore, it's smarter to regard refcounting as something
other than, or less than garbage collection. Q.E.D. :)
To me, garbage collection means: computing the lifetimes of objects without any
help from extra memory-management-related instructions added to the compiled
program.
Under garbage collection, the application program only ever makes one kind of
memory-management call: a request for the creation of a new object. It is
otherwise completely, void of all memory management concerns, both at the
source level, and in the compiled code.
Vend
>
> I may have thought so once, but I changed my mind, and I'm still getting
> smarter. Therefore, it's smarter to regard refcounting as something
> other than, or less than garbage collection. Q.E.D. :)
>
> To me, garbage collection means: computing the lifetimes of objects without any
> help from extra memory-management-related instructions added to the compiled
> program.
In generational garbage collectors, the program will execute
additional instructions each time a reference to a young object is
stored inside an old object.
Do you consider generational GC a proper form of GC?
Even in non-generational tracing collectors, some instructions are
required to generate typing information for stack-allocated pointers
and heap-allocated objects for the marker (unless you perform
conservative GC, which sucks.)
Vend
> On 2009-12-21 11:22:09 +0000, Vend <ven...@virgilio.it> said:
>
> > Reference counting memory managment is a form of garbage collection.
>
> That depends on who you ask, of course.
>
>
>
> > Possibly you mean tracing garbage collection, which either sweeps dead
> > objects or moves live objects around the heap, in both cases affecting
> > caching performance.
>
> Yes. I suspect copying collectors have rather good cache behaviour,
> since they almost inevitably mean that (some of) the live data is
> cached after the GC has run.
That's probably true of young-generation collection of generational
GC.
Kaz Kylheku
>>
>> I may have thought so once, but I changed my mind, and I'm still getting
>> smarter. Therefore, it's smarter to regard refcounting as something
>> other than, or less than garbage collection. Q.E.D. :)
>>
>> To me, garbage collection means: computing the lifetimes of objects without any
>> help from extra memory-management-related instructions added to the compiled
>> program.
>
> In generational garbage collectors, the program will execute
> additional instructions each time a reference to a young object is
> stored inside an old object.
Indeeed, because such stores violate the desireable property that pointers only
point from newer generations to the older, and never the other way around.
If the memory manager is not informed about this situation, it will wrongly
reclaim the young objects, if they are not referenced by objects that are
as young young, or younger, leaving the old-to-young references dangling.
Any memory manager that needs to be informed this way, is not GC.
If you can find a way to solve this problem without help from the program,
then you have GC.
> Do you consider generational GC a proper form of GC?
No, I don't.
This so-called ``garbage collector'' cannot collect garbage properly
from some machine-language programs which pose no problems to the the full
garbage collector.
Garbage collection is anything that has exactly the same semantics as an
abstract model described in terms of mark and sweep, and can be used as a
binary drop-in replacement for a reference implementation thereof without
recompiling any new machine code.
George Neuner
Jones and Lins book is pretty much the bible of GC. Don't be overly
concerned by the old publication date: little has changed since it was
written. Definitely worth a read if you're interested in GC.
Jones and Lins, "Garbage Collection: Algorithms for Automatic
Dynamic Memory Management", ISBN 0-471-94148-4.
George