Closed Bug 1382275 Opened 2 years ago Closed 2 years ago

Refactor incremental sweeping to more clearly express the control flow

Categories

(Core :: JavaScript: GC, enhancement)

55 Branch
enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla56
Tracking Status
firefox56 --- fixed

People

(Reporter: jonco, Assigned: jonco)

Details

Attachments

(1 file)

We currently have two lists of 'sweep actions' that are run during incremental sweeping.  The main loop in GCRuntime::performSweepActions is complicated and hard to read and requires a long comment explaining what it does.

We should refactor this into a more declarative form that better expresses the control flow here.
Attached patch reorg-sweepSplinter Review
This replaces the two lists of sweep actions that were stored per-process with a per-runtime tree of SweepAction objects.  SweepAction defines an interface with a run() method to do some sweep work and is templated on the arguments passed to that method.  State that used to be stored on the GCRumtime is now part of the the sweep action objects that make up the tree.

Sweep actions are provided to loop over the contents of various containers and to run a sequence of sweep actions.  These manage the state that needs to be preserved between yielding to the mutator and resuming sweeping.  

This makes use of iterator objects.  Sadly we use several styles of iterator in SpiderMonkey.  I used a done()/get()/next() style interface rather than empty()/front()/popFront() or the C++ STL style begin()/end()/++/== one (which complicates things be requiring an object to represent the end of the container to compare against).  ContainerIter provides this style of iterator for a STL-style container.

IncrementalIter is a template class that makes a normal iterator into one that can be used to incrementally by using external state (wrapped in Maybe<>) which is only initialised on the first use (subsequent uses carry on from the previous state).  This is the core abstraction that makes all this work.

There are two main SweepAction implementations - SweepActionSequence (which runs a sequence of sweep actions) and SweepActionForEach which runs a single sweep action for every element of some container.

Helper functions are provided to allocate sweep actions without explicitly specifying the template parameters.

This all allows us to express the sweep work much more clearly in GCRuntime::initSweepActions.

This does make pretty heavy use of templates which I guess might be contentious but was unavoidable for this approach.
Attachment #8889441 - Flags: review?(sphink)
Comment on attachment 8889441 [details] [diff] [review]
reorg-sweep

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

::: js/src/gc/GCRuntime.h
@@ +47,5 @@
>      Finished
>  };
>  
> +// Interface to a sweep action.
> +// Note that we don't need perfect forwarding for arguments here.

Why not?

I haven't thought about it at all. But I'd rather the comment be // We don't need perfect forwarding for arguments here because...

unless there isn't anything useful to say? Is it just because these will always be rvalue references? I don't know what I'm talking about.

@@ +1259,5 @@
>       */
>  
>      ActiveThreadData<JS::Zone*> sweepGroups;
>      ActiveThreadOrGCTaskData<JS::Zone*> currentSweepGroup;
> +    ActiveThreadData<UniquePtr<SweepAction<GCRuntime*, FreeOp*, SliceBudget&>>> sweepActions;

This reads a little weird:

  SweepAction sweepActions;

but I guess that's fine.

::: js/src/jsgc.cpp
@@ +5338,2 @@
>      sweepCache = nullptr;
> +    sweepActions->checkFinished();

I found this confusing. I wasn't sure if this was doing something important (finishing off whatever's left over) or just asserting. I think I'd like any of these better:


    MOZ_ASSERT(sweepActions->finished());
    MOZ_ASSERT(sweepActions->done());
    sweepActions->assertFinished();

Well, probably not the done() one.

@@ +5768,5 @@
> +// Construct a type based on all but the last type in a template parameter pack.
> +// For example:
> +//
> +//   AllButLast<Foo, X, Y, Z>::Type ==> Foo<X, Y>
> +//

This class needs a comment containing an ASCII rendering of an exploding head. Perhaps an animated one, with ^L between frames, so you can flip through them.

@@ +5770,5 @@
> +//
> +//   AllButLast<Foo, X, Y, Z>::Type ==> Foo<X, Y>
> +//
> +template <template <typename...> class Target, typename... Args>
> +class AllButLast

Hm. AllButLast may be too simple of a name, since it doesn't really describe what's happening. Maybe InstantiateFirstWithAllButLast? Or TemplatizeFirstOnAllButLast?

I'm just going to assume there isn't some simpler way to go about this, by reordering things or something.

And I admit that I'm impressed that you could get this to work! I can never get the base cases right in template metaprogramming.

@@ +5800,5 @@
> +template <typename Container>
> +class ContainerIter
> +{
> +    using Iter = decltype(mozilla::DeclVal<const Container>().begin());
> +    using Elem = decltype(*mozilla::DeclVal<Iter>());

Ooh, I didn't know about DeclVal. That could be useful.

@@ +5825,5 @@
> +    }
> +};
> +
> +template <typename Iter>
> +struct IncrementalIter

Please move the relevant part of the commit message into a comment here. (And random side note: is this better as IncrementalIter or StatefulIter?)

@@ +5952,5 @@
> +template <typename... Args, typename... Rest>
> +static UniquePtr<SweepAction<Args...>>
> +SweepSequence(UniquePtr<SweepAction<Args...>> first, Rest... rest)
> +{
> +    UniquePtr<SweepAction<Args...>> actions[] = { Move(first), Move(rest)... };

Wow.

@@ +5957,5 @@
> +    auto seq = MakeUnique<SweepActionSequence<Args...>>();
> +    if (!seq || !seq->init(actions, ArrayLength(actions)))
> +        return nullptr;
> +
> +    return UniquePtr<SweepAction<Args...>>(Move(seq)); // TODO: clang requires this cast, why?

I think it probably should? Hm... though I suspect std::unique_ptr would be ok without the cast.

You're casting from UniquePtr<SweepActionSequence> to UniquePtr<SweepAction>. SweepActionSequence is a subclass of SweepAction, so it seems like that should work if UniquePtr were covariant (as opposed to contravariant or C++'s default, invariant). And std::unique_ptr is covariant. I guess UniquePtr isn't?

Hm... from reading the UniquePtr documentation, it looks like this might work without the cast if you declared seq to be of type

  UniquePtr<SweepActionSequence<Args...>, DefaultDelete<SweepAction<Args...>>>

but I don't think you can do that with MakeUnique.

Or I could be way off base. I'm well over my head already. The cast seems ok to me.

@@ +5962,5 @@
> +}
> +
> +template <typename... Args>
> +static UniquePtr<typename AllButLast<SweepAction, Args...>::Type>
> +SweepForEachZone(JSRuntime* rt, UniquePtr<SweepAction<Args...>> action) {

{ on new line.

It's probably too verbose for the name, but maybe comment that this is really SweepForEachZoneInSweepGroup or something? (Hopefully I'm following what this is doing; I kind of got lost trying to figure out how the sweep group factors in.)

@@ +5973,5 @@
> +}
> +
> +template <typename... Args>
> +static UniquePtr<typename AllButLast<SweepAction, Args...>::Type>
> +SweepForEachAllocKind(AllocKinds kinds, UniquePtr<SweepAction<Args...>> action) {

{ on new line.

@@ +6023,5 @@
>          return NotFinished;
>  
>      for (;;) {
> +        if (sweepActions->run(this, &fop, budget) == NotFinished)
> +           return NotFinished;

Phew. That's a lot of template craziness for this line and the clean-looking initSweepActions. I definitely see the benefit in encapsulating the incremental iterator state. I'm not totally sold on whether it's worth the rest of the template stuff to provide the declarative initialization, especially for this one usage. Though at least it's constrained to this one source file and isn't going to slow down the whole build.

My leaning right now is to go ahead and land this. If maintenance bothers anyone enough to complain, they/we can replace it.
Attachment #8889441 - Flags: review?(sphink) → review+
(In reply to Steve Fink [:sfink] [:s:] from comment #2)
> > +// Note that we don't need perfect forwarding for arguments here.
> 
> Why not?

Good point.  The answer is that types are are not deduced here but come ultimately from the types of the arguments of a function pointer passed to SweepFunc and are then propagated backwards through the tree of actions.  So we already know the exact type (and whether it's a reference or not) and there's no need to accept anything and forward it.  I'll add a comment.

> > +    sweepActions->checkFinished();
> 
> I found this confusing. I wasn't sure if this was doing something important
> (finishing off whatever's left over) or just asserting.

I should stop using the word 'check' where I mean 'assert'.  Fixed.

> > +//   AllButLast<Foo, X, Y, Z>::Type ==> Foo<X, Y>
> 
> This class needs a comment containing an ASCII rendering of an exploding
> head. Perhaps an animated one, with ^L between frames, so you can flip
> through them.

This may be the best code review comment I have ever received.  I think I'm going to print it out and frame it.

I rewrote this so that it takes a whole template instantiation as a single parameter (rather than separate Target and Args...) an renamed it so that now it's:

//   RemoveLastTemplateParameter<Foo<X, Y, Z>>::Type ==> Foo<X, Y>

Hopefully that makes it clearer.  I also added some comments about how it works.

> > +template <typename... Args, typename... Rest>
> > +static UniquePtr<SweepAction<Args...>>
> > +SweepSequence(UniquePtr<SweepAction<Args...>> first, Rest... rest)
> > +{
> > +    UniquePtr<SweepAction<Args...>> actions[] = { Move(first), Move(rest)... };
> 
> Wow.

I really wanted to use initializer_list to pass a list of actions here, but their contents are always const which prohibits using them to pass unique_ptrs.

> Phew. That's a lot of template craziness for this line and the clean-looking
> initSweepActions. I definitely see the benefit in encapsulating the
> incremental iterator state. I'm not totally sold on whether it's worth the
> rest of the template stuff to provide the declarative initialization,
> especially for this one usage. Though at least it's constrained to this one
> source file and isn't going to slow down the whole build.
> 
> My leaning right now is to go ahead and land this. If maintenance bothers
> anyone enough to complain, they/we can replace it.

Yeah, I'm wasn't 100% sure either but it is nice to be able to see clearly how sweeping progresses.  The craziness is mainly around creating SweepActions with the right template parameters and it's isolated to this one area so I think it's OK.

Other comments addressed.
Pushed by jcoppeard@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/0c66a9949ff9
Refactor incremental sweeping to more clearly express the control flow r=sfink
Pushed by jcoppeard@mozilla.com:
https://hg.mozilla.org/integration/mozilla-inbound/rev/15da8084e961
Fix bustage due to missing explict keyword r=me on a CLOSED TREE
https://hg.mozilla.org/mozilla-central/rev/0c66a9949ff9
https://hg.mozilla.org/mozilla-central/rev/15da8084e961
Status: NEW → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla56
You need to log in before you can comment on or make changes to this bug.