972581 - Implement parallelized version of mapPar for typed object arrays

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Niko Matsakis [:nmatsakis]]

As a first step towards parallelizing the full set of operations over typed object arrays, implement a parallelized version of mapPar for 1, 2, and 3 dimensions.

Comment 1

[Niko Matsakis [:nmatsakis]]

Attachment: Bug972581-Part1.diff

Just a little cleanup.

Comment 2

[Niko Matsakis [:nmatsakis]]

Attachment: Bug972581-Part2.diff

More cleanup.

Comment 3

[Till Schneidereit [:till]]

Comment on attachment 8375958 [details] [diff] [review]
Bug972581-Part1.diff

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

sure

Comment 4

[Niko Matsakis [:nmatsakis]]

Attachment: Bug972581-Part3.diff

This patch implements parallel map for a depth of 1. It needs some cleanup and some optimization -- for example, it relies on a number of functions for which I defined parallel equivalents in C, but which ought to be inlined. But it seems to work, at least for simple tests. Anyway, I doubt I will push just yet, but Shu I'd appreciate a quick look.

Comment 5

[Till Schneidereit [:till]]

Comment on attachment 8375959 [details] [diff] [review]
Bug972581-Part2.diff

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

r=me, after checking with nmatsakis that the change to using opaque instead of derived pointers in some places is correct.

Comment 6

[Niko Matsakis [:nmatsakis]]

Note to self: regarding till's point about the change to opaque, we need a test that checks that out pointers are opaque!

Comment 7

[Shu-yu Guo [:shu]]

Comment on attachment 8375961 [details] [diff] [review]
Bug972581-Part3.diff

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

The general approach in mapThread looks good to me, though I just a did once-through. I noted the part I was most confused about (redirect).

Didn't really pay attention to the small helper functions and if they'll JIT well; that won't be too hard to fix.

::: js/src/builtin/TypedObject.js
@@ +962,5 @@
> +    return MapTypedParImpl(this, 1, thisType, a);
> +  else if (typeof a === "number")
> +    return ThrowError(JSMSG_TYPEDOBJECT_BAD_ARGS);
> +  else
> +    return ThrowError(JSMSG_TYPEDOBJECT_BAD_ARGS);

Nit: return after else

@@ +1436,5 @@
> +  ForkJoin(mapThread, ShrinkLeftmost(slicesInfo), ForkJoinMode(mode));
> +  return outArray;
> +
> +  function redirect(typedObj, offset) {
> +    if (false && (!InParallelSection() || !outGrainTypeIsTransparent)) {

if (false) ?

@@ +1450,5 @@
> +      // if it does. But those don't exist yet.
> +      //
> +      // Moreover, checking if the type is transparent is an
> +      // overapproximation: users can manually declare opaque types
> +      // that nonetheless only contain scalar data.

This comment confuses me. Let me see if I understand:

The property we're trying to guarantee is to not let the in/out fat pointers we pass to the kernel functions to escape. This could happen in sequential mode or when the output grain type is opaque, meaning that output type may contain an opaque reference type Object or Any. In those cases, we make a copy of the fat pointer.

I'm not exactly sure *why* this comment confuses me. I think I'm overloading the use of "object" between "typed object" and "JS object" in my mind, and logically it kinda makes sense for a typed object to "contain" other typed objects, in that you have nested StructTypes, but here you really mean JS objects.

@@ +1480,5 @@
> +      // the different iterations cannot communicate typed object
> +      // pointers to one another during parallel exec, we need only
> +      // fear escaped typed objects from *other* slices, so we can
> +      // just set the target region once.
> +      var endOffset = std_Math_imul(outGrainTypeSize, indexEnd + 1);

Is the + 1 necessary, since indexEnd is already 1 beyond the last writable index?

Comment 8

[Niko Matsakis [:nmatsakis]]

(In reply to Shu-yu Guo [:shu] from comment #7)
> > +  function redirect(typedObj, offset) {
> > +    if (false && (!InParallelSection() || !outGrainTypeIsTransparent)) {
> 
> if (false) ?

Sorry, that's a FIXME -- `InParallelSection()` OUGHT to be replaced with a constant in ion, but for some reason it wasn't, and it was causing parallel execution to bailout. Or something. I haven't figured out the full story yet.

> I'm not exactly sure *why* this comment confuses me. I think I'm overloading
> the use of "object" between "typed object" and "JS object" in my mind, and
> logically it kinda makes sense for a typed object to "contain" other typed
> objects, in that you have nested StructTypes, but here you really mean JS
> objects.

I'll see if I can make it clearer, but your explanation was correct.

> 
> @@ +1480,5 @@
> > +      var endOffset = std_Math_imul(outGrainTypeSize, indexEnd + 1);
> 
> Is the + 1 necessary, since indexEnd is already 1 beyond the last writable
> index?

Ah, the classic off by one error. Good catch.

Comment 9

[Niko Matsakis [:nmatsakis]]

Attachment: Bug972581-Part1.diff

Comment 10

[Niko Matsakis [:nmatsakis]]

Attachment: Bug972581-Part2.diff

Basically same as before but added a test and fixed the if (false) business

Comment 11

[Niko Matsakis [:nmatsakis]]

Comment on attachment 8379139 [details] [diff] [review]
Bug972581-Part2.diff

Oops, clearing r? because I forgot to address the feedback comments. New version coming soon!

Comment 12

[Niko Matsakis [:nmatsakis]]

Attachment: Bug972581-Part2.diff

Comment 13

[Shu-yu Guo [:shu]]

Comment on attachment 8379151 [details] [diff] [review]
Bug972581-Part2.diff

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

LGTM. I didn't look very closely at the tests.

Most comments are small; main thing I'd like to see addressed is moving the PJS macros into Utilities.js.

::: js/src/builtin/TypedObject.cpp
@@ +2673,5 @@
> +
> +    JS_ASSERT(typedObj.typedMem() != nullptr); // must be attached already
> +
> +    typedObj.setPrivate(typedObj.owner().dataPointer() + offset);
> +    typedObj.setReservedSlot(JS_TYPEDOBJ_SLOT_BYTEOFFSET, Int32Value(offset));

I'm somewhat surprised there's no existing setOffset that encapsulates the slot.

::: js/src/builtin/TypedObject.js
@@ +953,5 @@
> +  if (!TypeDescrIsArrayType(thisType))
> +    return ThrowError(JSMSG_TYPEDOBJECT_BAD_ARGS);
> +
> +  // Arguments: [depth], func
> +  if (typeof a === "number" && typeof b === "function")

I imagine we want a IsCallable check instead of a typeof == function check.

@@ +958,5 @@
> +    return MapTypedParImpl(this, a, thisType, b);
> +  else if (typeof a === "function")
> +    return MapTypedParImpl(this, 1, thisType, a);
> +  else if (typeof a === "number")
> +    return ThrowError(JSMSG_TYPEDOBJECT_BAD_ARGS);

What is this branch for? It seems subsumed by the else below.

@@ +960,5 @@
> +    return MapTypedParImpl(this, 1, thisType, a);
> +  else if (typeof a === "number")
> +    return ThrowError(JSMSG_TYPEDOBJECT_BAD_ARGS);
> +  else
> +    return ThrowError(JSMSG_TYPEDOBJECT_BAD_ARGS);

Nit: return after else here and above. Blame Brendan.

@@ +1410,5 @@
> +    // that assume the value won't escape and copy it if it
> +    // does. But those don't exist yet.  Moreover, checking if the
> +    // type is transparent is an overapproximation: users can
> +    // manually declare opaque types that nonetheless only contain
> +    // scalar data.

I find this comment block easier to understand than before.

@@ +1455,5 @@
> +    var inTypedObject = inPointer.getDerivedIf(inGrainTypeIsComplex);
> +    var outPointer = new TypedObjectPointer(outGrainType, outArray, 0);
> +    var outTypedObject = outPointer.getOpaqueIf(outGrainTypeIsComplex);
> +    callFunction(std_Array_push, pointers, { inTypedObject: inTypedObject,
> +                                             outTypedObject: outTypedObject });

There're macros like ARRAY_PUSH #defined in Array.js.

We should move those and the PJS-specific macros from Array.js into Utilities.js. I imagine the PJS macros like GET_SLICE work right now only by virtue of TypedObject.js being #included after Array.js

Comment 14

[Niko Matsakis [:nmatsakis]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/a7c61b562512
https://hg.mozilla.org/integration/mozilla-inbound/rev/108209641936

Comment 15

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/a7c61b562512
https://hg.mozilla.org/mozilla-central/rev/108209641936