958370 - PJS: Unify chunks and slices & partially self-host workstealing scheduler

Status: RESOLVED FIXED

(Core :: JavaScript Engine: JIT, defect)

Description

[Shu-yu Guo [:shu]]

Once the workstealing scheduler lands in bug 919638, we should simplify the chunking scheme and unify the concepts of chunks and slices, so that we only have one unit of work in PJS. This will simplify the bookkeeping we have to do right now to track which chunks are finished computing, etc.

The new scheduler can potentially create a lot more slices, causing more calls to the ForkJoin kernel and thus crossing the C++-JS boundary more often. We should also investigate self-hosting part of the scheduler so this doesn't cause unnecessary slowdown.

Comment 1

[Shu-yu Guo [:shu]]

Note to self: also ensure deterministic behavior wrt to warmup.

Comment 2

[Shu-yu Guo [:shu]]

Attachment: Unify chunks and slices; self-host the scheduler's slice processing loop.

This patch makes the slice the single unit of work in ForkJoin as well as
self-host part of the scheduler using helper intrinsics. The intrinsics are
currently not inlined and will be done in a future patch.

Please read the high level comments above ForkJoin for the new design.

Due to OMTC of the bounds function, mapPar-nested is failing due to interrupts.
It will be reenabled once bug 949296 lands.

Comment 3

[Shu-yu Guo [:shu]]

FilterPar could be cleaned up more by requiring fixed-size 32-long slices so it doesn't need to also deal with 32-bit chunks for the survivors bitset.

Comment 4

[Shu-yu Guo [:shu]]

Addenda about the patch: it also ensures determinism and should fix failures due to having too many cores.

Comment 5

[Niko Matsakis [:nmatsakis]]

Comment on attachment 8370685 [details] [diff] [review]
Unify chunks and slices; self-host the scheduler's slice processing loop.

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

This looks great. I confess I didn't read every detail of the changes to Array.js; I'm assuming if the tests pass etc that it's in reasonably good shape.

::: js/src/builtin/Array.js
@@ +653,5 @@
>   */
> +function NextSequentialSliceId(info, doneMarker) {
> +  var statuses = info.statuses;
> +  var length = statuses.length;
> +  for (var i = 0; i < length; i++) {

It seems a shame to always loop from 0 here. I know this is kind of the slow path, maybe it's ok, but it'd be nice to track the lowest complete value and just inc and return that. But eh. Let's leave it for a later bug (if it ever shows up on profiles).

@@ +708,5 @@
>  
> +  function mapThread(warmup) {
> +    var sliceId;
> +    while (true) {
> +      sliceId = ForkJoinGetSlice(InParallelSection() ? -1 : NextSequentialSliceId(slicesInfo, -1));

Why not use GET_SLICE here?

::: js/src/jit-test/lib/parallelarray-helpers.js
@@ +99,5 @@
>      for (var i = 0, l = a.length; i < l; i++) {
>        try {
>          assertStructuralEq(a[i], b[i]);
>        } catch (e) {
> +        print("...in index ", i, "of", l);

Nit: surely this has an extra space before `i`

::: js/src/vm/ForkJoin.cpp
@@ +484,3 @@
>  
>      RootedObject fun(cx, &args[0].toObject());
> +    RootedObject boundsFun(cx, &args[1].toObject());

Nit: Let's make these a notch more type safe by using Rooted<JSFunction*> here (and in the declaration of ForkJoinOperation).

@@ +544,5 @@
>      }
>      return "???";
>  }
>  
> +ForkJoinOperation::ForkJoinOperation(JSContext *cx, HandleObject fun, HandleObject boundsFun,

Nit: Change to HandleFunction or Handle<JSFunction*>, both for fun and boundsFun

@@ +552,5 @@
>      bailoutScript(cx),
>      bailoutBytecode(nullptr),
>      cx_(cx),
>      fun_(fun),
> +    boundsFun_(boundsFun),

Nit: ...and update the types of these fields too, naturally.

@@ +978,2 @@
>  {
>      // XXX use disqualified to set parallelIon to ION_DISABLED_SCRIPT?

Prexisting, but we should open an issue for this -- I think we could summarize it as "decide when to disqualify a script from further attempts at parallel execution"

::: js/src/vm/ForkJoin.h
@@ +43,5 @@
>  //
> +// The second argument, |boundsFunc|, is a function that must return an array
> +// of exactly two integers. This function is called before every attempt at
> +// execution: warmup, sequential, or parallel. The bounds are taken from a
> +// function call instead of as two static integers so that the bouds may be

s/instead of as two static integers/instead of two static integers/?

s/bouds/bounds/

Comment 6

[Shu-yu Guo [:shu]]

(In reply to Niko Matsakis [:nmatsakis] from comment #5)
> Comment on attachment 8370685 [details] [diff] [review]
> Unify chunks and slices; self-host the scheduler's slice processing loop.
> 
> Review of attachment 8370685 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> This looks great. I confess I didn't read every detail of the changes to
> Array.js; I'm assuming if the tests pass etc that it's in reasonably good
> shape.
> 

Thanks for quick review! Yeah it passes tests, except for the bug in bug 949296 as I explain at the very bottom.

> ::: js/src/builtin/Array.js
> @@ +653,5 @@
> >   */
> > +function NextSequentialSliceId(info, doneMarker) {
> > +  var statuses = info.statuses;
> > +  var length = statuses.length;
> > +  for (var i = 0; i < length; i++) {
> 
> It seems a shame to always loop from 0 here. I know this is kind of the slow
> path, maybe it's ok, but it'd be nice to track the lowest complete value and
> just inc and return that. But eh. Let's leave it for a later bug (if it ever
> shows up on profiles).

I changed the function to:

function NextSequentialSliceId(info, doneMarker) {
  var statuses = info.statuses;
  var length = statuses.length;
  for (var i = info.lastSequentialId; i < length; i++) {
    if (statuses[i] === SLICE_STATUS_DONE)
      continue;
    info.lastSequentialId = i;
    return i;
  }
  return doneMarker == undefined ? length : doneMarker;
}

info.lastSequentialId starts at 0.

> 
> @@ +708,5 @@
> >  
> > +  function mapThread(warmup) {
> > +    var sliceId;
> > +    while (true) {
> > +      sliceId = ForkJoinGetSlice(InParallelSection() ? -1 : NextSequentialSliceId(slicesInfo, -1));
> 
> Why not use GET_SLICE here?
> 

Oops, I was debugging something and forgot to change it back.

> ::: js/src/jit-test/lib/parallelarray-helpers.js
> @@ +99,5 @@
> >      for (var i = 0, l = a.length; i < l; i++) {
> >        try {
> >          assertStructuralEq(a[i], b[i]);
> >        } catch (e) {
> > +        print("...in index ", i, "of", l);
> 
> Nit: surely this has an extra space before `i`
> 
> ::: js/src/vm/ForkJoin.cpp
> @@ +484,3 @@
> >  
> >      RootedObject fun(cx, &args[0].toObject());
> > +    RootedObject boundsFun(cx, &args[1].toObject());
> 
> Nit: Let's make these a notch more type safe by using Rooted<JSFunction*>
> here (and in the declaration of ForkJoinOperation).
> 
> @@ +544,5 @@
> >      }
> >      return "???";
> >  }
> >  
> > +ForkJoinOperation::ForkJoinOperation(JSContext *cx, HandleObject fun, HandleObject boundsFun,
> 
> Nit: Change to HandleFunction or Handle<JSFunction*>, both for fun and
> boundsFun
> 
> @@ +552,5 @@
> >      bailoutScript(cx),
> >      bailoutBytecode(nullptr),
> >      cx_(cx),
> >      fun_(fun),
> > +    boundsFun_(boundsFun),
> 
> Nit: ...and update the types of these fields too, naturally.
> 

Nits fixed.

> @@ +978,2 @@
> >  {
> >      // XXX use disqualified to set parallelIon to ION_DISABLED_SCRIPT?
> 
> Prexisting, but we should open an issue for this -- I think we could
> summarize it as "decide when to disqualify a script from further attempts at
> parallel execution"
> 

Filed bug 969212.

> ::: js/src/vm/ForkJoin.h
> @@ +43,5 @@
> >  //
> > +// The second argument, |boundsFunc|, is a function that must return an array
> > +// of exactly two integers. This function is called before every attempt at
> > +// execution: warmup, sequential, or parallel. The bounds are taken from a
> > +// function call instead of as two static integers so that the bouds may be
> 
> s/instead of as two static integers/instead of two static integers/?
> 
> s/bouds/bounds/

The "as" is the preposition of "taken" to contrast with "taken from", I changed it to "instead of taken as two static ..."

Unfortunately I have to land this together with bug 949296 because there are intermittent failures due to us not ignoring DontStopIon interrupts.

Comment 7

[Shu-yu Guo [:shu]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/ad7777f1c0f5

Comment 8

[Phil Ringnalda (:philor)]

https://hg.mozilla.org/mozilla-central/rev/ad7777f1c0f5