The default bug view has changed. See this FAQ.

GC: Incremental sweeping of shapes and types

RESOLVED FIXED in mozilla17

Status

()

Core
JavaScript Engine
RESOLVED FIXED
5 years ago
5 years ago

People

(Reporter: billm, Assigned: jonco)

Tracking

(Depends on: 1 bug, Blocks: 1 bug)

unspecified
mozilla17
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(blocking-kilimanjaro:+)

Details

(Whiteboard: [k9o:p1:fx15][Snappy:p1])

Attachments

(1 attachment, 7 obsolete attachments)

(Reporter)

Description

5 years ago
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

5 years ago
(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.
(Reporter)

Comment 2

5 years ago
Oops. Didn't mean to assign this to myself.
Assignee: wmccloskey → general

Updated

5 years ago
Depends on: 737365

Updated

5 years ago
Depends on: 741115
blocking-kilimanjaro: --- → ?
blocking-kilimanjaro: ? → +
Whiteboard: [k9o:p1:fx15]
(Reporter)

Updated

5 years ago
Assignee: general → wmccloskey

Updated

5 years ago
Blocks: 746389
(Assignee)

Updated

5 years ago
Assignee: wmccloskey → jcoppeard
Depends on: 770110
Depends on: 770200
(Assignee)

Comment 3

5 years ago
Created attachment 639702 [details] [diff] [review]
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.
(Assignee)

Comment 4

5 years ago
Created attachment 641086 [details] [diff] [review]
Incremental sweeping patch v2
Attachment #639702 - Attachment is obsolete: true
Whiteboard: [k9o:p1:fx15] → [k9o:p1:fx15][Snappy]
What kind of approach are you taking?  Comment 0 is a little vague.
(Assignee)

Comment 6

5 years ago
Created attachment 642605 [details] [diff] [review]
Incremental sweeping patch v3
Attachment #641086 - Attachment is obsolete: true
(Assignee)

Comment 7

5 years ago
Created attachment 643389 [details]
Incremental sweeping patch v4

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

Comment 8

5 years ago
Created attachment 643417 [details] [diff] [review]
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.
Attachment #642605 - Attachment is obsolete: true
Attachment #643389 - Attachment is obsolete: true
(Reporter)

Comment 9

5 years ago
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.
Attachment #643417 - Flags: review+
(Assignee)

Comment 10

5 years ago
Created attachment 643892 [details] [diff] [review]
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);
Attachment #643417 - Attachment is obsolete: true

Updated

5 years ago
Whiteboard: [k9o:p1:fx15][Snappy] → [k9o:p1:fx15][Snappy:p1]
(Reporter)

Comment 11

5 years ago
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.
Summary: GC: Incremental sweeping → GC: Incremental sweeping of shapes and types
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.
(Assignee)

Comment 13

5 years ago
Created attachment 644955 [details] [diff] [review]
Incremental sweeping patch v7

Latest patch containing fix for assertions when finalizing shapes.
Attachment #643892 - Attachment is obsolete: true
(Assignee)

Comment 14

5 years ago
Created attachment 645330 [details] [diff] [review]
Incremental sweeping patch v8

Updated patch with fix for ScriptSource sweeping issue that arose during catchup to inbound.
Attachment #644955 - Attachment is obsolete: true
Attachment #645330 - Flags: review?(wmccloskey)
(Reporter)

Comment 15

5 years ago
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
Attachment #645330 - Flags: review?(wmccloskey) → review+
(Assignee)

Comment 16

5 years ago
Thanks for the review.

I've fixed the comments and pushed to inbound.

https://hg.mozilla.org/integration/mozilla-inbound/rev/6f47fa34dcbc
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
(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
(Assignee)

Comment 19

5 years ago
Fixed assertion failures and pushed to inbound:

https://hg.mozilla.org/integration/mozilla-inbound/rev/106da1cef37b
https://hg.mozilla.org/mozilla-central/rev/106da1cef37b
Status: NEW → RESOLVED
Last Resolved: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla17
Depends on: 780653
Depends on: 785366
Depends on: 791174
Depends on: 801957
You need to log in before you can comment on or make changes to this bug.