729760 - GC: Incremental sweeping of shapes and types

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

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

Incremental sweeping of objects with finalizers should really reduce the maximum pause times for incremental GCs. In theory, there's nothing scary here. However, the code that iterates over ArenaLists and finalizes them will probably need to be refactored. Some of the state will have to be moved from local variables to global state, and all these functions will now have to return early if their budget expires.

One (possibly stupid) idea is to do all finalization on the background thread. However, the background thread would only be allowed to finalize non-background objects when the main thread is in a SWEEP slice, waiting for it to finish. When all the non-background allocation kinds had been finalized, it would finalize the background objects all at once, without waiting for the main thread (the way we normally do it).

The advantage of this approach is that the code wouldn't need to change much. The inner finalization loop would occasionally check if its budget had expired, and if so, it would wait on a condition variable. But this approach is pretty inelegant and probably slower.

Igor, are you interested in looking into this? It seems like I'll be busy fixing incremental GC bugs for a while longer, and it would be nice to make progress on this.

Comment 1

[Igor Bukanov]

(In reply to Bill McCloskey (:billm) from comment #0)

I can look into it. But first I want to do measurements for the bug 724807. It is important to find out early what parts of sweeping should be done in the background and what incrementally.

Comment 2

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

Oops. Didn't mean to assign this to myself.

Comment 3

[Jon Coppeard (:jonco)]

Attachment: Draft patch to implement incremental sweeping

Here's my progress so far at implementing incremental sweeping.

Current status is that the tests pass and the v8 benchmarks work with incremental zeal mode on, but I haven't tested this in the browser yet.

Also there's a few things I want to tidy up first before this is ready for review.

Comment 4

[Jon Coppeard (:jonco)]

Attachment: Incremental sweeping patch v2

Comment 5

[Andrew McCreight [:mccr8]]

What kind of approach are you taking?  Comment 0 is a little vague.

Comment 6

[Jon Coppeard (:jonco)]

Attachment: Incremental sweeping patch v3

Comment 7

[Jon Coppeard (:jonco)]

Attachment: Incremental sweeping patch v4

Patch with billm's fix for memory corruption crashes plus code review feedback

Comment 8

[Jon Coppeard (:jonco)]

Attachment: Incremental sweeping patch v5

Updated patch to remove change that broke tests (this was to fix an occasional crash on exit) and added incremental sweeping for all GC things except objects.

Comment 9

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

Comment on attachment 643417 [details] [diff] [review]
Incremental sweeping patch v5

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

Great work! Sorry about all the syntax nits. I'm a stickler for these things. Please fix these and then it's ready to be checked in.

::: js/src/jscntxt.h
@@ +566,5 @@
>      /* Indicates that the last incremental slice exhausted the mark stack. */
>      bool                gcLastMarkSlice;
>  
> +    /* Whether any sweeping will take place in the separate GC helper thread. */
> +    bool                gcSweepBackgroundThread;

Maybe call this gcSweepOnBackgroundThread. Otherwise it sounds like it's the ID of the background thread.

::: js/src/jsgc.cpp
@@ +361,5 @@
> +/*
> + * Remove the first arena from the list and return it, or return NULL if the
> + * list is empty.
> + */
> +ArenaHeader* ArenaLists::ArenaList::takeFirst()

ArenaHeader *...

@@ +366,5 @@
> +{
> +    JS_ASSERT_IF(!head, cursor == &head);
> +    if (!head)
> +        return NULL;
> +    ArenaHeader* first = head;

ArenaHeader *first

@@ +377,5 @@
> +/*
> + * Insert an arena into the list in appropriate position and update the cursor
> + * to ensure that any arena before the cursor is full.
> + */
> +void ArenaLists::ArenaList::insert(ArenaHeader *a)

Now that we're naming the ArenaList type more, it probably makes sense to move it out of the ArenaLists type. Could you do that?

@@ +404,4 @@
>      size_t thingSize = Arena::thingSize(thingKind);
> +
> +    ArenaHeader* aheader;
> +    while ((aheader = src.takeFirst()), aheader) {

I'm pretty sure that this syntax will work, and it's nicer:

while (ArenaHeader *aheader = src.takeFirst()) {
    ....
}

@@ +462,4 @@
>        case FINALIZE_EXTERNAL_STRING:
> +	return FinalizeTypedArenas<JSExternalString>(fop, src, dest, thingKind, budget);
> +      default:
> +        JS_ASSERT(false);

We have JS_NOT_REACHED("invalid alloc kind") for this purpose.

@@ +1611,5 @@
> +ArenaLists::queueForForegroundSweep(FreeOp *fop, AllocKind thingKind)
> +{
> +    JS_ASSERT(!fop->onBackgroundThread());
> +    JS_ASSERT(backgroundFinalizeState[thingKind] == BFS_DONE ||
> +              backgroundFinalizeState[thingKind] == BFS_JUST_FINISHED);

I think we never need the BFS_JUST_FINISHED case here. Is that right? (I can see why you changed the one in finalizeNow.)

@@ +1678,5 @@
>      JS_ASSERT(listHead);
>      AllocKind thingKind = listHead->getAllocKind();
>      JSCompartment *comp = listHead->compartment;
> +    ArenaList src;
> +    src.head = listHead;

It might be nice if ArenaList had a constructor that took an ArenaHeader* for the head.

@@ +1752,2 @@
>  {
> +    queueForForegroundSweep(fop, FINALIZE_SCRIPT);

Looking over the script finalization code again, I'm thinking maybe we should hold off on incrementalizing this one. There's a lot of debugger stuff that happens in there that we don't have very good tests for. I don't think scripts take much time anyway.

@@ +3206,5 @@
>  
>      rt->gcIsFull = true;
>      for (CompartmentsIter c(rt); !c.done(); c.next()) {
> +        JS_ASSERT(!c->wasGCStarted());
> +        for (int i = 0 ; i < FINALIZE_LIMIT ; ++i)

for (int i = 0; i < FINALIZE_LIMIT; i++)

Also, you should use the type "unsigned" here instead of int. Otherwise I think the compiler will complain, since FINALIZE_LIMIT is unsigned.

@@ +3462,5 @@
>  }
>  #endif
>  
>  static void
> +BeginSweepPhase(JSRuntime *rt, SliceBudget &sliceBudget)

Is there any reason to pass in the budget here?

@@ +3563,5 @@
> +
> +bool
> +ArenaLists::foregroundFinalize(FreeOp *fop, AllocKind thingKind, SliceBudget &sliceBudget)
> +{
> +    ArenaList& src = arenaListsToSweep[thingKind];

ArenaList &src = ...

@@ +3567,5 @@
> +    ArenaList& src = arenaListsToSweep[thingKind];
> +    if (!src.head)
> +        return true;
> +
> +    ArenaList& dest = arenaLists[thingKind];

ArenaList &dest = ...

@@ +3574,5 @@
> +}
> +
> +static bool
> +SweepPhase(JSRuntime *rt, SliceBudget &sliceBudget)
> +{

This function should have one of these in scope the whole time:

gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_SWEEP);

@@ +3577,5 @@
> +SweepPhase(JSRuntime *rt, SliceBudget &sliceBudget)
> +{
> +    FreeOp fop(rt, rt->gcSweepBackgroundThread, false);
> +
> +    while (rt->gcSweepPhase < FinalizePhaseCount) {

I think this loop, and the ones below, might be clearer as for loops:

for (; rt->gcSweepPhase < FinalizePhaseCount; rt->gcSweepPhase++)

You can use multiple lines for the loop head if needed.

@@ +3605,5 @@
> +}
> +
> +static void
> +EndSweepPhase(JSRuntime *rt, JSGCInvocationKind gckind, gcreason::Reason gcReason)
> +{

This function should have one of these in scope the whole time:

gcstats::AutoPhase ap(rt->gcStats, gcstats::PHASE_SWEEP);

@@ +3646,5 @@
> +        if (c->wasGCStarted())
> +            c->setGCStarted(false);
> +
> +        JS_ASSERT(!c->wasGCStarted());
> +        for (int i = 0 ; i < FINALIZE_LIMIT ; ++i)

for (unsigned i = 0; i < FINALIZE_LIMIT; i++)

@@ +3761,3 @@
>          c->setNeedsBarrier(false);
> +        c->setGCStarted(false);
> +        for (int i = 0 ; i < FINALIZE_LIMIT ; ++i)

for (unsigned i = 0; i < FINALIZE_LIMIT; i++)

@@ +3836,5 @@
>  };
>  
>  static void
> +PushZealSelectedObjects(JSRuntime *rt)
> + {

Extra space here.

@@ +3839,5 @@
> +PushZealSelectedObjects(JSRuntime *rt)
> + {
> +#ifdef JS_GC_ZEAL
> +    /* Push selected objects onto the mark stack and clear the list. */
> +    if (!rt->gcSelectedForMarking.empty()) {

I'm not sure why this test was here. It's not needed.

@@ +3893,5 @@
>          rt->gcIncrementalState = MARK_ROOTS;
>          rt->gcLastMarkSlice = false;
>      }
>  
> +    switch(rt->gcIncrementalState) {

Space between switch and the paren.

@@ +3929,5 @@
> +             * when we resume, so we stay in MARK state.
> +             */
> +            rt->gcLastMarkSlice = true;
> +            break;
> +         }

This brace doesn't line up with the opening brace.

::: js/src/jsgc.h
@@ +142,5 @@
>              head = NULL;
>              cursor = &head;
>          }
> +
> +        void set(const ArenaList &other) {

Could this be an operator= ?

@@ +150,5 @@
> +            else
> +                cursor = other.cursor;
> +        }
> +
> +        ArenaHeader* takeFirst();

Methods like this are usually called popFront() in SpiderMonkey.

Also, it should be ArenaHeader *name().

@@ +151,5 @@
> +                cursor = other.cursor;
> +        }
> +
> +        ArenaHeader* takeFirst();
> +        void insert(ArenaHeader*);

void insert(ArenaHeader *aheader).

@@ +192,5 @@
>      };
>  
>      volatile uintptr_t backgroundFinalizeState[FINALIZE_LIMIT];
>  
> +public:

This should be indented two spaces.

@@ +361,2 @@
>  
> +    bool foregroundFinalize(FreeOp *fop, AllocKind thingKind, SliceBudget& sliceBudget);

SliceBudget &budget

@@ +363,3 @@
>      static void backgroundFinalize(FreeOp *fop, ArenaHeader *listHead);
>  
> +    void resetFinalizeNow(AllocKind thingKind);

This doesn't seem to be used anywhere. Can you remove it?

::: js/src/jsgcinlines.h
@@ +489,5 @@
>  
>  inline js::Shape *
>  js_NewGCShape(JSContext *cx)
>  {
> +    js::Shape* shape = js::gc::NewGCThing<js::Shape>(cx, js::gc::FINALIZE_SHAPE, sizeof(js::Shape));

Shape *shape

::: js/src/jspropertytree.cpp
@@ +145,5 @@
>       * tree root -- see bug 335700 for details.
>       */
>      KidsPointer *kidp = &parent_->kids;
>      if (kidp->isShape()) {
> +        Shape* kid = kidp->toShape();

Shape *kid

@@ +156,5 @@
>      }
>  
> +#ifdef JSGC_INCREMENTAL
> +    /*
> +     * We need a read barrier for the shape tree, since these are weak pointers.

This comment probably belongs inside the comp->needsBarrier() case.

@@ +165,5 @@
> +            Shape *tmp = shape;
> +            MarkShapeUnbarriered(comp->barrierTracer(), &tmp, "read barrier");
> +            JS_ASSERT(tmp == shape);
> +        }
> +        else if (comp->wasGCStarted() && cx->runtime->gcIncrementalState == js::gc::SWEEP &&

The else should go on the same line as the close brace above it.

Comment 10

[Jon Coppeard (:jonco)]

Attachment: Incremental sweeping patch v6

Updated patch with billm's comments addressed plus some refactoring that occurred to me in the process.

Still getting the following assert occasionally, although I can build what feels like a stable browser with it:

js::Shape::removeChild (this=0x10287a420, child=0x10287d8f8) at jspropertytree.cpp:110
110	        JS_ASSERT(kidp->toShape() == child);

Comment 11

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

Just so nobody gets the wrong idea here, this patch incrementalizes one aspect of sweeping--namely the sweeping of shapes and types. Eventually, the same code may be used to incrementalize a few other things, but that will require work in xpconnect and the DOM. The impact on pause times will be measurable but not dramatic. Sweeping consists of a lot of little phases that add up to a long pause. Each one will have to be fixed in its own way.

Comment 12

[Andrew McCreight [:mccr8]]

From a random GC from my regular build, "Sweep Shape" is 8.7ms and "Sweep Types" is 6.8ms.  I don't know if this affects anything else in addition.

Comment 13

[Jon Coppeard (:jonco)]

Attachment: Incremental sweeping patch v7

Latest patch containing fix for assertions when finalizing shapes.

Comment 14

[Jon Coppeard (:jonco)]

Attachment: Incremental sweeping patch v8

Updated patch with fix for ScriptSource sweeping issue that arose during catchup to inbound.

Comment 15

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

Comment on attachment 645330 [details] [diff] [review]
Incremental sweeping patch v8

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

::: js/src/gc/Heap.h
@@ +916,5 @@
> +    hasDelayedMarking = 0;
> +    auxNextLink = 0;
> +}
> +
> +inline ArenaHeader *ArenaHeader::getNextAllocDuringSweep() const

The return type should go on its own line.

::: js/src/jsgc.cpp
@@ +1467,5 @@
>      }
>  }
>  
> +static inline void
> +pushArenaAllocatedDuringSweep(JSRuntime* runtime, ArenaHeader* arena)

Since this is not a method, the name should be capitalized. Also, the parameters should be "JSRuntime *rt" and "ArenaHeader *arena".

@@ +1474,5 @@
> +    runtime->gcArenasAllocatedDuringSweep = arena;
> +}
> +
> +static inline ArenaHeader*
> +popArenaAllocatedDuringSweep(JSRuntime* runtime)

This function only has one use. I'd rather just have the code at the site where it's used.

@@ +1539,5 @@
>              if (JS_UNLIKELY(comp->needsBarrier())) {
>                  aheader->allocatedDuringIncremental = true;
>                  comp->rt->gcMarker.delayMarkingArena(aheader);
>              }
> +            else if (JS_UNLIKELY(comp->isGCSweeping())) {

This is a pretty hot path. I'd rather we have one branch here, rather than two. Can you do it like this?

if (JS_UNLIKELY(comp->wasGCStarted())) {
    if (comp->needsBarrier()) ...
    else if (comp->isGCSweeping()) ...
}

Also, the else should go on the same line as the close brace.

@@ +1571,5 @@
>      if (JS_UNLIKELY(comp->needsBarrier())) {
>          aheader->allocatedDuringIncremental = true;
>          comp->rt->gcMarker.delayMarkingArena(aheader);
>      }
> +    else if (JS_UNLIKELY(comp->isGCSweeping())) {

Same here.

::: js/src/jsgc.h
@@ +385,2 @@
>  
> +    bool foregroundFinalize(FreeOp *fop, AllocKind thingKind, SliceBudget& sliceBudget);

& goes with sliceBudget

Comment 16

[Jon Coppeard (:jonco)]

Thanks for the review.

I've fixed the comments and pushed to inbound.

https://hg.mozilla.org/integration/mozilla-inbound/rev/6f47fa34dcbc

Comment 17

[Ed Morley [:emorley]]

Backed out for make check failures:
https://tbpl.mozilla.org/?tree=Mozilla-Inbound&onlyunstarred=1&rev=6f47fa34dcbc

eg:
https://tbpl.mozilla.org/php/getParsedLog.php?id=13834155&tree=Mozilla-Inbound
https://tbpl.mozilla.org/php/getParsedLog.php?id=13833952&tree=Mozilla-Inbound

https://hg.mozilla.org/integration/mozilla-inbound/rev/38a8439f4c9d

Comment 18

[Ed Morley [:emorley]]

(In reply to Ed Morley [:edmorley] from comment #17)
> https://tbpl.mozilla.org/?tree=Mozilla-Inbound&onlyunstarred=1&rev=6f47fa34dcbc

Sorry, meant to paste the version without &onlyunstarred=1:
https://tbpl.mozilla.org/?tree=Mozilla-Inbound&rev=6f47fa34dcbc

Comment 19

[Jon Coppeard (:jonco)]

Fixed assertion failures and pushed to inbound:

https://hg.mozilla.org/integration/mozilla-inbound/rev/106da1cef37b

Comment 20

[Matt Brubeck (:mbrubeck)]

https://hg.mozilla.org/mozilla-central/rev/106da1cef37b