1465368 - Experiment with removing premarking

Status: RESOLVED WONTFIX

(Core :: JavaScript: GC, enhancement, P3)

Description

[Paul Bone [:pbone]]

During incremental GC we premark any new arenas that are allocated into to ensure that new objects are black.  I want to experiment with marking only the new objects rather than whole arenas.

Comment 1

[Paul Bone [:pbone]]

Attachment: Allocate tenured objects black during incremental collection

I havn't done the jitcase, I'm using --jitflags=none for now.  I may also change the condition, right now i'm using wasGCStarted() but there maybe something finer-grained.

Comment 2

[Paul Bone [:pbone]]

Attachment: Remove premarking

Comment 3

[Jon Coppeard (:jonco)]

Comment on attachment 8981819 [details] [diff] [review]
Allocate tenured objects black during incremental collection

Review of attachment 8981819 [details] [diff] [review]:
-----------------------------------------------------------------

Indeed, the condition is too broad. You want to check | zone->isGCMarking() || zone->isGCSweeping() |.

::: js/src/gc/Allocator.cpp
@@ +260,5 @@
>          }
>      }
> +    if (cell && cx->zone()->wasGCStarted()) {
> +        cell->markBlack();
> +    }

(nit: no braces around single line if, here and below)

::: js/src/gc/GC.cpp
@@ +2306,5 @@
>          oomUnsafe.crash("Could not allocate new arena while compacting");
>      }
> +    TenuredCell *cell = TenuredCell::fromPointer(dstAlloc);
> +    if (zone->wasGCStarted())
> +        cell->markBlack();

You don't want to mark new cells black while compacting.  This happens after mark and sweep and is not required.

Comment 4

[Jon Coppeard (:jonco)]

Comment on attachment 8981820 [details] [diff] [review]
Remove premarking

Review of attachment 8981820 [details] [diff] [review]:
-----------------------------------------------------------------

::: js/src/gc/GC.cpp
@@ -5679,5 @@
>          zone->changeGCState(Zone::Mark, Zone::Sweep);
>  
>          /* Purge the ArenaLists before sweeping. */
> -        if (isIncremental)
> -            zone->arenas.unmarkPreMarkedFreeCells();

I think you can remove the implementation of unmarkPreMarkedFreeCells() too.

Comment 5

[Steve Fink [:sfink] [:s:]]

I'm somewhat skeptical of an approach that is going to slow down the JIT allocation fast path. It's also an extra memory write (that depends on a read) on every allocation, because the mark bits are separate from the memory. I suspect that's not as cache-friendly as marking a whole swath of cells at once.

If you really want to avoid overmarking, I wonder if there's some point in time when you could mark everything allocated so far -- eg, add a field to ArenaHeader that records the first free cell when you start a GC, and then when you use up an arena, you mark from that cell to the end? It's still gross because the mark bits would be wrong in the meantime, and you might need to change isMarked() to flush the pending mark bits if you can't catch all the transitions. But maybe we have a place to do a flush every time you leave JITted code? I guess you also need any code running underneath the JIT... hm, maybe this isn't such a good idea. I think it puts you back to where we were when we were checking a per-arena allocatedDuringIncremental flag.

I suppose I shouldn't get in the way of this experiment when I haven't even followed the discussion enough to know why this is needed...

Comment 6

[Paul Bone [:pbone]]

(In reply to Steve Fink [:sfink] [:s:] (PTO June 31) from comment #5)
> I'm somewhat skeptical of an approach that is going to slow down the JIT
> allocation fast path. It's also an extra memory write (that depends on a
> read) on every allocation, because the mark bits are separate from the
> memory. I suspect that's not as cache-friendly as marking a whole swath of
> cells at once.

That's a good point.

> If you really want to avoid overmarking, I wonder if there's some point in
> time when you could mark everything allocated so far -- eg, add a field to
> ArenaHeader that records the first free cell when you start a GC, and then
> when you use up an arena, you mark from that cell to the end? It's still
> gross because the mark bits would be wrong in the meantime, and you might
> need to change isMarked() to flush the pending mark bits if you can't catch
> all the transitions. But maybe we have a place to do a flush every time you
> leave JITted code? I guess you also need any code running underneath the
> JIT... hm, maybe this isn't such a good idea. I think it puts you back to
> where we were when we were checking a per-arena allocatedDuringIncremental
> flag.

One concern is that the premarking code makes some free cells black, which just, urgh, that's just wrong.  So your suggestion is also the same type of "wrong".

Avoiding overmarking isn't really a concern, since the sweeping code, before beginning sweeping, makes any free cells (on free lists) white before beginning sweeping.  So it's not as if the memory is not recovered.

> I suppose I shouldn't get in the way of this experiment when I haven't even
> followed the discussion enough to know why this is needed...

It drew my attention while I hit some assertions regarding premarking while trying to avoid collecting the nursery every slice.  One way to avoid these assertions would be to remove this hack so I don't need another hack to handle it.  That was only the original reason, now that I've learnt more I'd like to retro-actively say that my reason is that I'd like to remove doing extra work, shading all these cells black then shading some of them white later on.

Now you've pointed it out I'm also concerned about the JIT fast path, and that probably-not-very predictable memory read/write to make each object black. (compared with the sequential "make this arena black" which is more easily predicted and has writes to the same cache line.

Comment 7

[Paul Bone [:pbone]]

How are already created arenas handled.  Are they simply not allocated from once a GC begins so that we don't need to mark new objects in them?

The premarking code could set a bit in the arena saying "this arena was allocated after GC started" then the sweeping code, rather than un-marking the free cells in each arena, could find all the arenas with this bit set and mark all the allocated objects (those the free-lists skip over, are free-lists always in order?).

Comment 8

[Paul Bone [:pbone]]

Thanks for the feedback jonco,

Just a note that I've read it and will follow throw on it later.  Yes, I know I left some dead code there.

Cheers.

Comment 9

[Jon Coppeard (:jonco)]

(In reply to Paul Bone [:pbone] from comment #7)
> How are already created arenas handled.  Are they simply not allocated from
> once a GC begins so that we don't need to mark new objects in them?

The premarking handles both cases.  When we pick an arena to allocate from (either new or pre-existing) we premark everything in its first free list.
 
> The premarking code could set a bit in the arena saying "this arena was
> allocated after GC started" then the sweeping code, rather than un-marking
> the free cells in each arena, could find all the arenas with this bit set
> and mark all the allocated objects (those the free-lists skip over, are
> free-lists always in order?).

That's how it used to work until I changed it in bug 1359342.

Comment 10

[Paul Bone [:pbone]]

(In reply to Jon Coppeard (:jonco) from comment #9)
> (In reply to Paul Bone [:pbone] from comment #7)
> > How are already created arenas handled.  Are they simply not allocated from
> > once a GC begins so that we don't need to mark new objects in them?
> 
> The premarking handles both cases.  When we pick an arena to allocate from
> (either new or pre-existing) we premark everything in its first free list.

Okay, I see that in tryNewTenuredThing.  It tries to allocate from a free list (a list of cells) and if that fails (the list is empty) it calls refillFreeListFromAnyThread which eventually calls allocateFromArena which will either get an existing arena (and premark it) or allocate a new one (and premark it).

...

What happens if an arena is never allocated from between GC slices?  Because no-one allocated an object with that AllocKind or because within the arena list we never reached that object's arena.  Will it ever be premarked and wouldn't that trigger the assertion when beginSweepingSweepGroup unmarks the premarked cells?

> > The premarking code could set a bit in the arena saying "this arena was
> > allocated after GC started" then the sweeping code, rather than un-marking
> > the free cells in each arena, could find all the arenas with this bit set
> > and mark all the allocated objects (those the free-lists skip over, are
> > free-lists always in order?).
> 
> That's how it used to work until I changed it in bug 1359342.

I'll check it out.

Comment 11

[Jon Coppeard (:jonco)]

(In reply to Paul Bone [:pbone] from comment #10)
> What happens if an arena is never allocated from between GC slices?  Because
> no-one allocated an object with that AllocKind or because within the arena
> list we never reached that object's arena.  Will it ever be premarked and
> wouldn't that trigger the assertion when beginSweepingSweepGroup unmarks the
> premarked cells?

The current free list for the first arena of every alloc kind gets premarked at the start of marking.  When we finish marking, the current free list for the first arena of every alloc kind gets unmarked.  So if an arena is not allocated from during marking its free list will be premarked at the beginning and then unmarked again at the end.

Comment 12

[Paul Bone [:pbone]]

(In reply to Jon Coppeard (:jonco) from comment #11)
> (In reply to Paul Bone [:pbone] from comment #10)
> > What happens if an arena is never allocated from between GC slices?  Because
> > no-one allocated an object with that AllocKind or because within the arena
> > list we never reached that object's arena.  Will it ever be premarked and
> > wouldn't that trigger the assertion when beginSweepingSweepGroup unmarks the
> > premarked cells?
> 
> The current free list for the first arena of every alloc kind gets premarked
> at the start of marking.  When we finish marking, the current free list for
> the first arena of every alloc kind gets unmarked.  So if an arena is not
> allocated from during marking its free list will be premarked at the
> beginning and then unmarked again at the end.

I can't find where that is.  I found code that clears the free lists at the start of marking (and I guess then it allows the premarking code to run.

https://searchfox.org/mozilla-central/source/js/src/gc/GC.cpp#4365

Comment 13

[Paul Bone [:pbone]]

(In reply to Paul Bone [:pbone] from comment #10)
> 
> What happens if an arena is never allocated from between GC slices?  Because
> no-one allocated an object with that AllocKind or because within the arena
> list we never reached that object's arena.  Will it ever be premarked and
> wouldn't that trigger the assertion when beginSweepingSweepGroup unmarks the
> premarked cells?
> 

Ah-ha!

It's not that the first arena is premarked when collection begins, but that it's free list is cleared.  then either:

 * An allocation causes the free-list to be refilled causing premarking.

   (I think it actually skips the rest of this arena and begins new allocations in the next one).

 * No allocation occurs and the free-list is never rebuilt. then in the sweeping code where there's an isBlack() assertion before shading all the free cells white (which was my earlier question), it doesn't check any free cells because the free list is still empty.

Comment 14

[Jon Coppeard (:jonco)]

(In reply to Paul Bone [:pbone] from comment #13)
You're right, it clears the free lists and they get premarked on the next allocation.

Comment 15

[Paul Bone [:pbone]]

We could also use a similar stratergy to the one proposed in Bug 1508327 to speed up premarking.

Comment 16

[Jon Coppeard (:jonco)]

We've no plans to do this at present.