701448 - GC: Moving Generational GC

Status: RESOLVED DUPLICATE of bug 619558

(Core :: JavaScript Engine, defect)

Description

[Terrence Cole [:terrence]]

As Bill pointed out, we don't have to move allocations to make our GC generational.  The real purpose of a generational GC is to partition old and new allocations for faster GC times.  Since our base quanta (the arena) is relatively small, we should be able to do a good enough job of partitioning just by being selective about where we allocate and carefully managing our arena list pointers.  

This won't give us the full benefit of locality that comes with a typical generational GC, but that is a small benefit compared to the others.  This work should also make it easier to move to full generational GC later when we have the capability to move allocations.

Comment 1

[Nicholas Nethercote [inactive]]

(In reply to Terrence Cole [:terrence] from comment #0)
> Since our base quanta (the arena) is
> relatively small, we should be able to do a good enough job of partitioning
> just by being selective about where we allocate and carefully managing our
> arena list pointers.  

I don't understand this.  What would be the equivalent of the nursery?  A single arena?  Multiple arenas?  Would we collect just those arenas when they fill up?  Would we then allocate future things using the freelists for those arenas?

Comment 2

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Unlike a normal generational collector, where the nursery is a fixed thing, our nursery would be a changing set of arenas over time. A scavenging GC would collect all the arenas in this set and no others. After collecting, it would clear the nursery set (so that it would contain no arenas). When allocating, we would try to allocate from arenas in the nursery first. If that didn't work, we would pick a fresh arena (with nothing allocated on it) and add it to the nursery. Within an arena, we would use the same allocation scheme as we currently do (a mix of freelists and bump pointer allocation).

One tricky part is what to do if we ran out of fresh arenas to add to the nursery. Then we would have to allocate from non-nursery arenas. Objects allocated this way wouldn't be collected in the next scavenge--they would have to wait for a full mark and sweep collection.

Comment 3

[Brian Hackett [Laid off!]]

It really won't be that hard to cut the dependency on the conservative scanner and do things exactly.  I'm hoping to start (for real) on this after the object shrink stuff lands.  I think that work is complementary with this though, and I hope we can work on the two pieces (nursery based collections and exact scanning) in parallel, with a third not-too-hard piece of doing moving nursery collections afterwards.

I don't know exactly how this would work, but it seems vulnerable to making lots of mostly empty arenas in a program with lots of short object lifetimes but some long ones (aka the use case generational GC is designed for).  Each nursery collection finds a small number of live objects, those arenas go into the major heap and can't be reused for the nursery until the objects are destroyed (right?), and eventually we run out of space and need to do all allocation from the major heap.

FWIW I think locality is important

Depending on the timetable for this and the complexity this allocation mechanism would entail, we could just cut the dependency on the conservative scanner without much trouble and jump straight into the moving generational GC.

Comment 4

[Brian Hackett [Laid off!]]

(Garbled post above, I hit the submit button accidentally).

Anyways, I'll be in the office tomorrow afternoon and am hoping we can talk some more about how to do this.

Comment 5

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Your point is a good one about ending up with lots of mostly empty arenas that can't go into the nursery. There are ways we can mitigate this. If a nursery arena is collected and it ends up with few objects in it, we can keep it in the nursery. We just have to keep any rememebered set entries that point into this arena. This is still a somewhat fragile mechanism, but I think it could be made to work reasonably well for the workloads where we currently do very poorly.

The main reason for doing non-moving collection is not the conservative scanning--we have a way to hack around that problem if needed. I'm more worried about the difficulty of getting moving collection of any sort to work, especially in the browser. I'm guessing that moving/compacting collection will be at least as hard a task as this bug.

Fundamentally, this bug is about getting the write barriers to work for generational collection. We'll have to come up with an efficient way of storing the remembered set, and we'll have to add a fast generational write barrier to the JIT. This work is largely independent of whether we do moving or non-moving generational GC, so I think it makes sense to start with the easier goal.

Comment 6

[Terrence Cole [:terrence]]

After an extensive discussion with Bill, Brian, and Andrew and a couple days of attacking the problem, we concluded doing a non-moving GC first would be more work than it is worth and not dovetail nicely with other efforts.  Renaming, as appropriate.

Comment 7

[Nicholas Nethercote [inactive]]

(In reply to Terrence Cole [:terrence] from comment #6)
> After an extensive discussion with Bill, Brian, and Andrew and a couple days
> of attacking the problem, we concluded doing a non-moving GC first would be
> more work than it is worth and not dovetail nicely with other efforts. 

I guess you meant "non-moving generational GC"?

> Renaming, as appropriate.

Isn't this now a dup of bug 619558?

Comment 8

[Terrence Cole [:terrence]]

(In reply to Nicholas Nethercote [:njn] from comment #7)
> (In reply to Terrence Cole [:terrence] from comment #6)
> > After an extensive discussion with Bill, Brian, and Andrew and a couple days
> > of attacking the problem, we concluded doing a non-moving GC first would be
> > more work than it is worth and not dovetail nicely with other efforts. 
> 
> I guess you meant "non-moving generational GC"?

Yes, I did.

> > Renaming, as appropriate.
> 
> Isn't this now a dup of bug 619558?

Ah, you are quite right.