Closed
Bug 729760
Opened 13 years ago
Closed 12 years ago
GC: Incremental sweeping of shapes and types
Categories
(Core :: JavaScript Engine, defect)
Core
JavaScript Engine
Tracking
()
People
(Reporter: billm, Assigned: jonco)
References
Details
(Whiteboard: [k9o:p1:fx15][Snappy:p1])
Attachments
(1 file, 7 obsolete files)
(deleted),
patch
|
billm
:
review+
|
Details | Diff | Splinter Review |
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•13 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•13 years ago
|
||
Oops. Didn't mean to assign this to myself.
Assignee: wmccloskey → general
Updated•13 years ago
|
blocking-kilimanjaro: --- → ?
Updated•13 years ago
|
blocking-kilimanjaro: ? → +
Whiteboard: [k9o:p1:fx15]
Reporter | ||
Updated•13 years ago
|
Assignee: general → wmccloskey
Assignee | ||
Updated•12 years ago
|
Assignee: wmccloskey → jcoppeard
Assignee | ||
Comment 3•12 years ago
|
||
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.
Updated•12 years ago
|
Whiteboard: [k9o:p1:fx15] → [k9o:p1:fx15][Snappy]
Assignee | ||
Comment 7•12 years ago
|
||
Patch with billm's fix for memory corruption crashes plus code review feedback
Assignee | ||
Comment 8•12 years ago
|
||
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•12 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•12 years ago
|
||
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•12 years ago
|
Whiteboard: [k9o:p1:fx15][Snappy] → [k9o:p1:fx15][Snappy:p1]
Reporter | ||
Comment 11•12 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.
Updated•12 years ago
|
Summary: GC: Incremental sweeping → GC: Incremental sweeping of shapes and types
Comment 12•12 years ago
|
||
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•12 years ago
|
||
Latest patch containing fix for assertions when finalizing shapes.
Attachment #643892 -
Attachment is obsolete: true
Assignee | ||
Comment 14•12 years ago
|
||
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•12 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•12 years ago
|
||
Thanks for the review. I've fixed the comments and pushed to inbound. https://hg.mozilla.org/integration/mozilla-inbound/rev/6f47fa34dcbc
Comment 17•12 years ago
|
||
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•12 years ago
|
||
(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•12 years ago
|
||
Fixed assertion failures and pushed to inbound: https://hg.mozilla.org/integration/mozilla-inbound/rev/106da1cef37b
Comment 20•12 years ago
|
||
https://hg.mozilla.org/mozilla-central/rev/106da1cef37b
Status: NEW → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla17
You need to log in
before you can comment on or make changes to this bug.
Description
•