Re: Register Allocators and Garbage Collectors

George Neuner <>
Tue, 16 Sep 2008 15:27:56 -0400

          From comp.compilers

Related articles
Register Allocators and Garbage Collectors (Ori Bernstein) (2008-09-09)
Re: Register Allocators and Garbage Collectors (George Neuner) (2008-09-13)
Re: Register Allocators and Garbage Collectors (Marco van de Voort) (2008-09-14)
Re: Register Allocators and Garbage Collectors (Sandeep Dutta) (2008-09-15)
Re: Register Allocators and Garbage Collectors (Ori Bernstein) (2008-09-15)
Re: Register Allocators and Garbage Collectors (Ori Bernstein) (2008-09-15)
Re: Register Allocators and Garbage Collectors (George Neuner) (2008-09-16)
Re: Register Allocators and Garbage Collectors (Ori Bernstein) (2008-09-17)
| List of all articles for this month |

From: George Neuner <>
Newsgroups: comp.compilers
Date: Tue, 16 Sep 2008 15:27:56 -0400
Organization: A noiseless patient Spider
References: 08-09-052 08-09-061 08-09-072
Keywords: GC, parallel
Posted-Date: 17 Sep 2008 03:37:28 EDT

On Mon, 15 Sep 2008 18:26:27 -0700 (PDT), Ori Bernstein
<> wrote:

>On Sep 13, 8:49 pm, George Neuner <> wrote:
>> On Tue, 9 Sep 2008 20:28:36 -0700 (PDT), Ori Bernstein
>> In a typical multi-threaded implementation, each thread maintains a
>> private heap which it can collect independently at any time. Objects
>> normally are created in the private heap. If the thread passes (hands
>> off) the object to another thread, it is copied to the new thread's
>> heap and becomes garbage to the original thread.
>Hm. How would this be detected? I suppose that the compiler would have
>to detect possible escape points and add runtime checks for that.

It doesn't need to be "detected" - to transfer an object between
private heaps, the threads had to communicate somehow. The new copy
in the 2nd thread will have its own reference, and the original copy
becomes garbage if/when the 1st thread loses all references to it.

It's the same as one computer sending data to another.

>But then how does a collector like Boehm handle it, as it has no
>support from the compiler?

Support from the compiler isn't necessary.

>> Collecting the shared heap requires collecting all the private heaps
>> as well because thread private objects may reference shared ones.
>> When a global collection is necessary, a typical method is send a
>> software interrupt each thread. The interrupt performs a private
>> collection and then either resumes or idles the thread. As part of
>> the private collection, the thread records references to shared
>> objects to be used as roots for the collection of the shared heap.
>Hm. Ok, I'm still not sure how you'd determine the roots if you've got
>the register allocator putting them into only registers and you've got
>a concurrent GC. (A blocking GC, they'd get pushed onto the stack
>before the GC function gets called, of course. I can see that.) I
>suppose that the compiler could put live ranges into the debug
>information, but that seems like it would be quite slow/inefficient to
>parse. And again, it raises the question of how a GC like the Bohem GC
>does it without compiler support.

Register allocation is irrelevant. I sort of gave you the answer
already in the text you quoted but I suppose some more detail wouldn't

There are two basic designs for a multi-mutator system: multiple
private heaps or a big shared heap. For performance reasons, many
shared-heap systems are designed so that each thread also has a
private heap. If there are both shared and private heaps, the
mutators generally are required to maintain the invariant that shared
objects never point to private objects - to share a private object a
mutator must copy it into the shared heap.

Regardless of whether there is a dedicated "GC thread", the collector
in a threaded system is not an atomic piece of code ... it is a
collection of cooperating functions which are used by both the
collector(s) and the mutator(s). In all the systems I am aware of,
mutator threads scan their own state and collect their own private
heaps - I know of no systems where a "GC thread" scans mutator threads
or collects anything other than shared heaps.

If there is no shared heap, each thread maintains its own set of
objects and collects its own heap whenever it chooses. There is no
sharing of objects wrt GC - if two threads need to share an object,
they must cooperate to synchronize their private copies.
Alternatively a thread may create an object, communicate a copy to
another thread and throw away its own copy. No special GC handling is
required for such a system.

If there is a shared heap, then the mutator threads must cooperate to
collect it because any of them may be holding references to shared
objects. Usually top level shared objects which will be collection
roots are required to be registered. In most GC'd languages there is
only one root - the top level name/binding table ... in C/C++ with a
Boehm library, you have to register all the globals explicitly.

When a shared collection is triggered, the collecting thread signals
each mutator thread and waits for a handshake. When the mutator
recognizes the signal (which may not be immediately), it invokes a
special GC routine to scan its own private state - registers, stack,
private heap, etc. It may do this generically by pushing the
registers onto the stack or, with compiler support, there may be a
unique routine for every stack frame that "knows" what roots are in
registers. If there is a private heap, the scan may also include
collecting it. The scan records any references to objects in the
shared heap and communicates the list to the thread waiting to collect
the shared heap. The lists of references from the mutators become
roots for the shared heap collection.

If the mutators are allowed to continue after scanning, then you have
the same coordination issues as in a single mutator concurrent system
- the collector has to be notified somehow of any changes made to the
connectivity map of the heap.

Hope this helps.

Post a followup to this message

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