Azul Pauseless GC

Thanks damien for the link :)

Begin forwarded message:

> Nice explanation of the Azul Pauseless GC (easier than the paper :)
> http://www.infoq.com/articles/azul_gc_in_detail

FWIW, the "pauseless" feature of the algorithm sounds very close (if not
exactly) like VisualWorks' incremental GC, modulo the multithreading.

On 2/26/11 9:46 , Stéphane Ducasse wrote:
> Thanks damien for the link :)
>
> Begin forwarded message:
>
>> Nice explanation of the Azul Pauseless GC (easier than the paper :)
>> http://www.infoq.com/articles/azul_gc_in_detail
>
>
>

Hi Andres:

On 28 Feb 2011, at 08:01, Andres Valloud wrote:

> FWIW, the "pauseless" feature of the algorithm sounds very close (if not exactly) like VisualWorks' incremental GC, modulo the multithreading.
Is VisualWorks' GC documented somewhere?
However, you might want to read the VEE'05 paper directly, the GC they use is 'nothing-like' a typical incremental GC. The read-barrier is the key here, and that is a rather exotic approach due to its constant overhead on standard systems.

So, just in case VisualWorks is actually using something similar, a reference to a paper or some such would be great.

Thanks
Stefan



--
Stefan Marr
Software Languages Lab
Vrije Universiteit Brussel
Pleinlaan 2 / B-1050 Brussels / Belgium
http://soft.vub.ac.be/~smarr
Phone: +32 2 629 2974
Fax:   +32 2 629 3525

> Is VisualWorks' GC documented somewhere?

What kind of documentation do you mean?

> However, you might want to read the VEE'05 paper directly, the GC
> they use is 'nothing-like' a typical incremental GC. The read-barrier
> is the key here, and that is a rather exotic approach due to its
> constant overhead on standard systems.

I thought they get away with the extra expenditure because they can hide
it under a multicore CPU (with the associated mutex section overhead
etc), and because they have a compacting IGC that allows their very
large images to run.  Probably it's a design decision to support huge apps.

> So, just in case VisualWorks is actually using something similar, a
> reference to a paper or some such would be great.

VisualWorks' IGC can mark and sweep incrementally.  It does not compact
incrementally, either.  Somewhere in the source documentation there's an
assertion that the read barriers to do that would be painful, so
compaction is left to the stop-the-world GC.  The rest is pretty
similar, including things like the targeted pause times (I'm almost done
with an overhaul of that bit of the IGC implementation, actually).

Now, if you had a read check to see whether the object body was
forwarded or not, then you could also compact incrementally.
Unfortunately, checking before every read would probably cost you
performance wise (plus: what happens when you want to forward an object
body referenced by another thread in registers in the middle of an
optimized section?).  So, depending on the application, it might be
better to avoid stopping the world, while in other cases it might be
preferable to skip the IGC completely and using the stop-the-world GC.

Finally, I am curious as to what kind of applications need on the order
of 1TB of address space in a single "image".  Those image scales impose
specific performance penalties e.g.: the IGC has to be more complex.  I
wonder if those apps couldn't be written in a more "agent-like" manner
to substitute controlled inter-image communication for the IGC
complexities that affect the runtime in a pervasive way.  Do you know
what kind of apps are those?

Andres.

Hi Andres:


On 28 Feb 2011, at 09:41, Andres Valloud wrote:

>> Is VisualWorks' GC documented somewhere?
>
> What kind of documentation do you mean?
A paper about the GC algorithm, the name of the algorithm?

>
>> However, you might want to read the VEE'05 paper directly, the GC
>> they use is 'nothing-like' a typical incremental GC. The read-barrier
>> is the key here, and that is a rather exotic approach due to its
>> constant overhead on standard systems.
>
> I thought they get away with the extra expenditure because they can hide it under a multicore CPU (with the associated mutex section overhead etc), and because they have a compacting IGC that allows their very large images to run.  Probably it's a design decision to support huge apps.
Their target is/was mainly financial/trade applications hugh heaps, on hugh and expensive custom hardware. Order of 1000cores per box with a 54-core custom chip.



>> So, just in case VisualWorks is actually using something similar, a
>> reference to a paper or some such would be great.
>
> VisualWorks' IGC can mark and sweep incrementally.  It does not compact incrementally, either.  Somewhere in the source documentation there's an assertion that the read barriers to do that would be painful, so compaction is left to the stop-the-world GC.  The rest is pretty similar, including things like the targeted pause times (I'm almost done with an overhaul of that bit of the IGC implementation, actually).
I guess it is some variation of a three-color incremental mark/sweep?


> Now, if you had a read check to see whether the object body was forwarded or not, then you could also compact incrementally. Unfortunately, checking before every read would probably cost you performance wise (plus: what happens when you want to forward an object body referenced by another thread in registers in the middle of an optimized section?).
That is the whole point of their design.
They have a hardware read barrier, and they use traps do make that possible.
One of the tricks they are pulling for that is that they return the memory page to the OS, and thus, they run into a trap when ever someone is referring to an old object address. Then, when that occurs they just fix the address to the new one. (as far as I remember...)


> So, depending on the application, it might be better to avoid stopping the world, while in other cases it might be preferable to skip the IGC completely and using the stop-the-world GC.
As I said, they are after big financial and commerce applications, the stories Cliff Click is usually telling is that if they would need to do a GC in pre-Christmas load situations their customers would lose a lot of sales...
Everything is plain old Java, no idea what kind of custom solutions those companies built on top of that.

Best regards
Stefan


--
Stefan Marr
Software Languages Lab
Vrije Universiteit Brussel
Pleinlaan 2 / B-1050 Brussels / Belgium
http://soft.vub.ac.be/~smarr
Phone: +32 2 629 2974
Fax:   +32 2 629 3525

>> What kind of documentation do you mean?
> A paper about the GC algorithm, the name of the algorithm?

There are some docs that state what happens, the docs come with the VM
sources.  But, basically, when the IGC is marking, then writes into
marked objects mark objects.  This allows mark stack consistency.  You
can mark incrementally until the mark stack is empty.  Then you can zero
out weak references that are gone (and deal with ephemerons).  After
that, you can also sweep dead object bodies and put them back into the
corresponding free block "lists".

The VisualWorks implementation is somewhat complex because there are
many moving parts.  The IGC marks whatever is in old space.  Perm space
("permanent" old objects) are assumed to never be garbage, so they
aren't even marked.  New objects are not marked either because they are
managed more efficiently by the new space scavenger.  There are remember
tables that allow you to do all of this effectively.  Special care must
be taken when tenuring new objects into old space if they were
referenced from a marked object in the remember table for new space.  In
64 bit systems, the class table is weak so you have to treat it as a
special case.  Etcetera :)...

> Their target is/was mainly financial/trade applications huge heaps,
> on huge and expensive custom hardware. Order of 1000 cores per box
> with a 54-core custom chip.

Wow... I wonder what happens when (not if) it crashes.

> I guess it is some variation of a three-color incremental mark/sweep?

IIRC, "three-color" refers to "not marked, marked, and scanned".  If so,
yes, it's sort of like that.

> One of the tricks they are pulling for that is that they return the
> memory page to the OS, and thus, they run into a trap when ever
> someone is referring to an old object address. Then, when that
> occurs they just fix the address to the new one. (as far as I
> remember...)

Oh, ok.  With such huge images, the likelyhood of any page being
accessed must not be overly high.  I suspect they may have to have some
sort of "mark stack" that cannot be paged out to make that possible.

Andres.

Hi Andres:

On 28 Feb 2011, at 11:20, Andres Valloud wrote:

> Oh, ok.  With such huge images, the likelyhood of any page being accessed must not be overly high.  I suspect they may have to have some sort of "mark stack" that cannot be paged out to make that possible.

Here you can hear Cliff bragging about some details:
http://www.infoq.com/interviews/click-gc-azul

Other than that, the linked article and the VEE'05 paper should cover the details better than I could.

Best regards
Stefan

>
> Andres.
>

--
Stefan Marr
Software Languages Lab
Vrije Universiteit Brussel
Pleinlaan 2 / B-1050 Brussels / Belgium
http://soft.vub.ac.be/~smarr
Phone: +32 2 629 2974
Fax:   +32 2 629 3525