Re: Best Ref-counting algorithms?

I think John is getting tired of this thread - GC is more a runtime
issue than a compiler one (except maybe for region-based GC which is
explicitly compiler directed).


I'm happy to continue this discussion by email if you want, but I do
suggest that you take the time to read Lins book because it seems like
you have some confusion about how the various forms of GC operate.
[You're also welcome to move it to gclist. See
http://lists.services.net/cgi-bin/mj_wwwusr/domain=lists.iecc.com?func=lists-full-long&extra=gclist
-John]


On Sat, 18 Jul 2009 15:06:26 -0700 (PDT), Christoffer Lernv
<lerno@dragonascendant.com> wrote:
>> On Jul 16, 6:35 pm, George Neuner <gneun...@comcast.net> wrote:
>
>So the idea is to let the ref counting work for the non-shared and
>then the shared set (which should be significantly smaller) is handled
>by a tracing GC?


That's one way to do it. Another I'll describe in a moment.


You're making a semantic mistake in equating "tracing" with "tracing
GC". Tracing is just a means to identify the set of live data - the
actual work of reclaiming garbage blocks is generically known as
"sweeping" and it can different forms. For most non-moving
collectors, tracing is just the first step in performing a collection.
OTOH, there are copying collectors for which tracing is the entirety
of the collection process. [For anyone about to interject here, I am
considering that Mark-Compact is a copying collector.]




For a ref-counter, the "interesting" set - cycles - is a subset of the
garbage. Garbage normally has no roots and is mainly disjoint ... so
it can't really be traced. So you first have to separate the garbage
by tracing and marking the live data. Then you scan the heap looking
for unmarked (garbage) chains of blocks that are circularly linked.


When a cycle is identified, the scanner breaks it by nulling the
pointer back to the head block and reducing the head block's counter.
At the end of scanning, the newly linear garbage can be freed normally
by the ref-counter. You can't do it immediately upon breaking a cycle
because the same blocks may be members of multiple cycles. The
scanner needs to remember the head blocks of the cycles it finds and
send all the chains to the ref-counter after the heap scan is
complete.




>> Baker's classic paper [on Treadmills] is at
>>http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.23.5878
>
>Since this is a tracing GC, will not a pure version of a Treadmill
>take longer to complete a round depending on how large the heap is?
>
>I admit to still having a rather vague understanding of various
>tracing GCs, but don't the vanilla tracing GCs necessarily work slower
>the larger the heap is?


Tracing in a Mark-Sweep collector touches only live data, so it
depends on utilization rather than total heap size ... it's the
sweeping phase that depends on heap size.


Mark-Compact and Cheney-style copying collectors touch only live data.




>Especially if we have a large object tree that gets scanned repeadedly
>but never needs to be collected.
>
>My understanding is that the idea with generational GCs is to move
>those structures to scan them much less often than majority of objects
>that are very short-lived.


Yes. The heap is subdivided into smaller areas which are handled
separately.




>On the other hand, perhaps your suggestion is exactly to combine use 1
>bit refcounts separate objects, and then slowly use a treadmill GC on
>the shared objects.


My suggestion was that shared objects be segregated and handled
separately. Any method that will handle cycles can be used to manage
the shared data.


I personally would not choose to use a ref-counter at all in a system
that requires high performance ... there is too much variability in
reclamation regardless of whether it is done aggressively or lazily.


AFAIK, Treadmills are the only non-moving collectors for which, like
Cheney copiers, tracing is the entirety of the collection process. And
they are the _only_ collectors for which time and cycle costs are
predictable.




>Still, the fact that large, unchanging objects needs to be scanned is
>a bit annoying as it increases costs the larger the heap is.


Tracing can always be done in parallel with the operation of the
mutator. In a non-moving collector, sweeping can be too. They cost
very little if you have a multi-processor.




>A typical problem when this is an issue is there you have a Server
>object that has references to most other parts of the system. This
>server object creates connection objects that are added when new
>connections are made, and removed when they disconnect.
>If the connection objects keep a reference to the Server object, we'd
>need to scan the whole server object and references - which might be
>almost the entire heap! - every time we want to destroy a circular
>reference to a connection.


That's what generational GC is for.




>Obviously any GC would need to be able to keep up with the garbage it
>needs to collect.


True ... but this represents another possible misunderstanding about
how GC works. Only ref-counters and Mark-Sweep collectors actually
"collect garbage". Mark-Compact and Cheney-style copying collectors
completely _ignore_ garbage: they are affected only by the amount of
live data and not by heap size or by the rate of garbage accumulation.






>> Generational GC solves a lot of the pause complaints because most
>> collection effort is concentrated on the nursery area ...
>> ... Older generations are collected less and less frequently.
>
>Isn't there the risk that unless you want a pause when the older
>generation really IS collected, you'd need that the older generation
>collector to not stop the world when it's run.


That depends on how the system is structured and is way too involved
to answer here. The short answer is: you can't design a system that
won't pause ... but you can design a system that won't pause
noticeably for a given definition of "noticeable".




>... the idea being approximately able to know when you potentially
>might be releasing a large amount of objects is very attractive if
>you are working on time-critical code.


Yes. I have a real-time programming background so I understand this
desire completely. The knee-jerk fix for this is to use stack or
region allocation. Practical region-based GC is still a research
project. See http://www.it-c.dk/research/mlkit/papers.html




>It would be nice to say "start automatic GC scheduling" or "wait with
>GC" or "run GC for 10ms starting from now".
>Any ideas why such controls are absent from java and several other
>GC:ed languages?


Because experience has shown that most programmers will eventually
hang themselves if you give them rope.


Most GC'd languages have as a goal the desire to protect programmers
from themselves. The average programmer today is only a little better
than poor. Language features like GC and monitor-based mutual
exclusion (Java's synchronized objects) are no longer conveniences for
good programmers but necessities without which the average programmers
cannot work effectively.


George

Return to the comp.compilers page.
Search the comp.compilers archives again.