829602 - ParallelDo intrinsic and self-hosted ParallelArray

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Niko Matsakis [:nmatsakis]]

Adds the self-hosted ParallelArray and supporting intrinsics.

Comment 1

[Niko Matsakis [:nmatsakis]]

Attachment: Patch 9: Add ParallelDo() intrinsic

Comment 2

[Niko Matsakis [:nmatsakis]]

Attachment: Patch 10: Self-hosted parallel array

Comment 3

[Niko Matsakis [:nmatsakis]]

Attachment: Patch 11: Adjust shell timeout function to allow execution of JS during the timeout

Comment 4

[David Mandelin [:dmandelin]]

I might not be able to get to these for a few days. Feel free to switch reviewers if you need them sooner.

Comment 5

[Shu-yu Guo [:shu]]

(In reply to David Mandelin [:dmandelin] from comment #4)
> I might not be able to get to these for a few days. Feel free to switch
> reviewers if you need them sooner.

Who else would be a suitable reviewer for a completely new feature?

Comment 6

[Till Schneidereit [:till]]

Comment on attachment 701096 [details] [diff] [review]
Patch 10: Self-hosted parallel array

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

Phew, that's quite a big patch. :)

I'm through with everything except for the tests, which I'll only do a cursory review of, and ParallelArray.js. So about 40% done or so. ;)

I'll review the rest tomorrow, but here's what I've got up to now.

General comments:

I Can't really review the changes in IonMonkey for more than very basic correctness. They do look very solid, but maybe dvander or somebody from the IM team should take a look at that part of the patch.

It seems you have put all parallel array-related functions before the equivalent array-related functions. I think it'd make slightly more sense to move them below, but this certainly isn't urgent (or important, even) in any way at all.

::: js/src/builtin/ParallelArray.cpp
@@ +26,2 @@
>  #include "jsobjinlines.h"
>  #include "jsarrayinlines.h"

Please sort these according to https://wiki.mozilla.org/JavaScript:SpiderMonkey:C%2B%2B_Coding_Style#Includes

@@ +36,2 @@
>  
> +// TODO: non-generic self hosted

Can you add a reference to a bug here?

@@ +42,5 @@
> +    { "scatter",   JSOP_NULLWRAPPER, 5, 0, "ParallelArrayScatter"   },
> +    { "filter",    JSOP_NULLWRAPPER, 2, 0, "ParallelArrayFilter"    },
> +    { "partition", JSOP_NULLWRAPPER, 1, 0, "ParallelArrayPartition" },
> +    { "flatten",   JSOP_NULLWRAPPER, 0, 0, "ParallelArrayFlatten" },
> +    /*{ "get",      JSOP_NULLWRAPPER, 1, 0, "ParallelArrayGet" },*/

Is this a todo? If so, please add a bug ref, too.

@@ +110,2 @@
>          return NULL;
> +    return ctorValue.toObject().toFunction();

Maybe assert that ctorValue is a function?

@@ +155,5 @@
> +                return false;
> +            if (paTypeObject->getPropertyCount() == 0) {
> +                if (!paTypeObject->addDefiniteProperties(cx, result))
> +                    return false;
> +                JS_ASSERT(paTypeObject->getPropertyCount() == NumFixedSlots);

So if property count is 0, NumFixedSlots has to be 0, too? Can you chance the assert to just `NumFixedSlots == 0` to make that a bit clearer, then?

@@ +224,5 @@
> +        Rooted<PropertyName *> lengthProp(cx, atom->asPropertyName());
> +        RootedValue lengthValue(cx);
> +        if (!cx->global()->getIntrinsicValue(cx, lengthProp, &lengthValue))
> +            return NULL;
> +        RootedObject lengthGetter(cx, &lengthValue.toObject());

Maybe assert that lengthValue is an Object?

@@ +250,4 @@
>  }
>  
>  JSObject *
> +js_InitParallelArrayClass(JSContext *cx, js::HandleObject obj)

AFAIK, we try not to introduce new js_ (and JS_) functions. Move this into the js namespace instead?

::: js/src/builtin/ParallelArray.h
@@ +11,3 @@
>  #include "jsapi.h"
>  #include "jscntxt.h"
>  #include "jsobj.h"

vertical space

@@ +12,5 @@
>  #include "jscntxt.h"
>  #include "jsobj.h"
> +#include "vm/ThreadPool.h"
> +#include "vm/ForkJoin.h"
> +#include "ion/Ion.h"

"ion" before "vm"

@@ +38,2 @@
>      //
> +    // NOTE: This object will NOT have the correct type object!  It is

Uber-nit: one space after "."

@@ +38,3 @@
>      //
> +    // NOTE: This object will NOT have the correct type object!  It is
> +    // up to you the caller to adjust the type object appropriately

IIUC, this is done in `construct`, right? If so, can you add a reference to that? (Or, maybe even make this private, should there be no reason for it to be public?)

::: js/src/builtin/ParallelArray.js
@@ +3,5 @@
> +//        or have native intrinsics provide both a sequential and a parallel
> +//        version.
> +// TODO: Use let over var when Ion compiles let.
> +// TODO: Private names.
> +// XXX: Hide buffer and other fields?

Do we have bugs on file for any of these? If so, please reference them here.

::: js/src/builtin/js2c.py
@@ +278,5 @@
>      lines = ExpandConstants(lines, consts)
>      lines = ExpandMacros(lines, macros)
>      Validate(lines, filename)
> +    #if not env['DEBUG']:
> +    #  lines = minifier.JSMinify(lines)

Is this change deliberate? If so, can you explain why?

::: js/src/ion/CodeGenerator.h
@@ +93,4 @@
>      bool visitApplyArgsGeneric(LApplyArgsGeneric *apply);
>      bool visitDoubleToInt32(LDoubleToInt32 *lir);
>      bool visitNewSlots(LNewSlots *lir);
> +    bool visitNewParallelArrayVMCall(LNewParallelArray *lir);

Should this be called `visitNewParallelArrayCallVM` in alignment with `visitNewArrayCallVM`?

::: js/src/ion/VMFunctions.cpp
@@ +13,4 @@
>  
>  #include "vm/StringObject-inl.h"
>  
> +#include "builtin/ParallelArray.h"

Move before */*-inl.h

::: js/src/js.msg
@@ +388,4 @@
>  MSG_DEF(JSMSG_UNDEFINED_CURRENCY,     335, 0, JSEXN_TYPEERR, "undefined currency in NumberFormat() with currency style")
>  MSG_DEF(JSMSG_INVALID_TIME_ZONE,      336, 1, JSEXN_RANGEERR, "invalid time zone in DateTimeFormat(): {0}")
>  MSG_DEF(JSMSG_DATE_NOT_FINITE,        337, 0, JSEXN_RANGEERR, "date value is not finite in DateTimeFormat.format()")
> +MSG_DEF(JSMSG_PAR_ARRAY_MODE_FAILURE, 338, 2, JSEXN_ERR, "expected {0} but found {1}")

Can you maybe rename this to JSMSG_WRONG_VALUE so that it is reusable?

::: js/src/parjs-benchmarks/README.txt
@@ +14,5 @@
> +# The tests
> +
> +- Mandelbrot: A test of embarassingly parallel arithmetic.  Exercises
> +  the comprehension form of 2D parallel arrays.
> +- Allocator: A test of parallel allocation.  Ensures that 

Did something get cut here?

::: js/src/vm/SelfHosting.cpp
@@ +161,4 @@
>  }
>  
>  static JSBool
> +intrinsic_SetFunctionFlags(JSContext *cx, unsigned argc, Value *vp)

Much better than MakeConstructible, thanks!

@@ +250,5 @@
>  
>  JSBool
> +js::intrinsic_NewParallelArray(JSContext *cx, unsigned argc, Value *vp)
> +{
> +    // Usage: %NewParallelArray(init, ...args)

We don't support the `%Name` syntax, anymore

@@ +272,3 @@
>  js::intrinsic_DenseArray(JSContext *cx, unsigned argc, Value *vp)
>  {
>      // Usage: %DenseArray(length)

We don't support the `%Name` syntax, anymore

Comment 7

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 701093 [details] [diff] [review]
Patch 9: Add ParallelDo() intrinsic

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

::: js/src/vm/ParallelDo.cpp
@@ +411,5 @@
> +    HeapPtrObject fun_;
> +
> +  public:
> +    // For tests, make sure to keep this in sync with minItemsTestingThreshold.
> +    const static uint32_t max_bailouts = 3;

for constants like this, prefer MAX_BAILOUTS

@@ +576,5 @@
> +        return ok;
> +    }
> +
> +    inline bool
> +    hasScript(Vector<types::RecompileInfo> &scripts, JSScript *script) {

one line for this signature

Comment 8

[Till Schneidereit [:till]]

Comment on attachment 701096 [details] [diff] [review]
Patch 10: Self-hosted parallel array

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

Ok, I've got until the end of ParallelArrayBuild in ParallelArray.js this time.

Sorry for the large amount of feedback: It's mostly nits about naming and coding style, as explained in the following general comments:


We don't yet have any code style guidelines for JS code in Spidermonkey, but one thing that we should adopt from the platform style guide (https://developer.mozilla.org/en-US/docs/Developer_Guide/Coding_Style) is to use JavaDoc for function comments.

Also, I've pointed out style nits whenever I think it makes sense to align with the C/C++ style guide.

Generally, we have been using 4-space indents in self-hosted JS, so please adapt to that.

I asked for speaking names in various places. Doing the review, I had several situations where I misunderstood what a var was used for and only later figured it out after reading quite a bit of code, when a clearer name would have made that, er, clear from the beginning.

Is there any WIP version of the specification for Parallel Arrays that resembles the current ES(5.1 or 6) spec? If so, it'd be great to add comments about where the different steps in each function start to the code as is done in Array.js.

::: js/src/builtin/ParallelArray.js
@@ +7,5 @@
> +// XXX: Hide buffer and other fields?
> +
> +function ComputeNumChunks(length) {
> +  // Determine the number of chunks of size CHUNK_SIZE;
> +  // note that the final chunk may be smaller than CHUNK_SIZE.

As stated above: JavaDoc comments here and for all other functions, please.

@@ +15,5 @@
> +  return chunks + 1;
> +}
> +
> +function ComputeSliceBounds(len, id, n) {
> +  // Computes the bounds for slice |id| of |len| items, assuming |n|

Can you change `id` to `index` and `n` to `numSlices` and maybe `len` to `numItems` to make it a bit clearer what's going on?

@@ +16,5 @@
> +}
> +
> +function ComputeSliceBounds(len, id, n) {
> +  // Computes the bounds for slice |id| of |len| items, assuming |n|
> +  // total slices.  If len is not evenly divisible by n, then the

Nit: Only one space between sentences here and everywhere else. (Surprisingly, this is even mentioned in the C++ style guide.)

@@ +18,5 @@
> +function ComputeSliceBounds(len, id, n) {
> +  // Computes the bounds for slice |id| of |len| items, assuming |n|
> +  // total slices.  If len is not evenly divisible by n, then the
> +  // final thread may have a bit of extra work.  It might be better to
> +  // do the division more equitably.

Can you turn this into a TODO item or at least make it a bit clearer that it's a comment about a potential optimization, not about something the code does now?

@@ +25,5 @@
> +  var end = id === n - 1 ? len : slice * (id + 1);
> +  return [start, end];
> +}
> +
> +function ComputeAllSliceBounds(length, numSlices) {

Please change `length` to `sliceLength`.

@@ +27,5 @@
> +}
> +
> +function ComputeAllSliceBounds(length, numSlices) {
> +  // Computes the bounds for all slices of |length| items, assuming
> +  // that there are |slices| items.  The result is an array containing

I'm not sure I understand what you mean by "assuming that [...]".

Maybe the comment could be
"Compute the bounds of |numSlices| slices with |sliceLength| items each."

@@ +41,5 @@
> +  }
> +  return info;
> +}
> +
> +function TruncateEnd(start, end) {

Is this function still used? I can't find any references to it.
If yes: can you make it's body be just `return IntMin(start + 3, end)`?

@@ +56,5 @@
> +  var products = [];
> +  var sdimensionality = shape.length;
> +  for (var i = sdimensionality - 1; i >= 0; i--) {
> +    products.push(product);
> +    product *= shape[i];

Initialize `products` with `[1]`, change the loop condition to `i > 0` and switch the two statements in the loop around to save one iteration.

@@ +87,5 @@
> +}
> +
> +function StepIndices(shape, indices) {
> +  var i = shape.length - 1;
> +  while (i >= 0) {

Please make this a for loop:
`for (var i = shape.length; i-- > 0;)`

@@ +103,5 @@
> +  return (v | 0) === v;
> +}
> +
> +// I'd prefer to use Math.min, but we have no way to access a pristine
> +// copy.  global.Math.min might be modified by the user.

Take a look at "builtins/Utilities.js" and use (or add to) the functions named "std_*" there. Using that, this function could just be `std_Math_min(a,b)|0`

@@ +112,5 @@
> +}
> +
> +// Constructor
> +//
> +// We split the 3 construction cases so that we don't case on arguments.

I'd much prefer for the three construction functions to be named based on what sets them apart from the others.
"EmptyParallelArrayCtor", "BufferCopyingParallelArrayCtor", etc

(Although I have to admit that that doesn't seem that much nicer.)

@@ +122,5 @@
> +  this.get = ParallelArrayGet1;
> +}
> +
> +function ParallelArrayConstruct1(buffer) {
> +  var buffer = ToObject(buffer);

Redundant `var`

@@ +125,5 @@
> +function ParallelArrayConstruct1(buffer) {
> +  var buffer = ToObject(buffer);
> +  var length = buffer.length >>> 0;
> +  if (length !== buffer.length)
> +    ThrowError(JSMSG_PAR_ARRAY_BAD_ARG, "");

Maybe use " constructor" for the method name here and in the other *Construct* functions?

@@ +137,5 @@
> +  this.shape = [length];
> +  this.get = ParallelArrayGet1;
> +}
> +
> +function ParallelArrayConstruct2(shape, f) {

Speaking names, please. I assume `f` is a function? Then `fun` would be fine.

@@ +142,5 @@
> +  if (typeof shape === "number") {
> +    var length = shape >>> 0;
> +    if (length !== shape)
> +      ThrowError(JSMSG_PAR_ARRAY_BAD_ARG, "");
> +    ParallelArrayBuild(this, [length], f);

Why does this work for values > 0? AFAICT, ParallelArraybuild should derive length values of `undefined` for shape === 1 and `NaN` for shape > 1. I'm probably mistaken, but maybe you can comment on how/ why this works?

@@ +143,5 @@
> +    var length = shape >>> 0;
> +    if (length !== shape)
> +      ThrowError(JSMSG_PAR_ARRAY_BAD_ARG, "");
> +    ParallelArrayBuild(this, [length], f);
> +  } else {

Can you add an `if (!shape || typeof shape.length !== "number")` and the corresponding `ThrowError` here?

@@ +156,5 @@
> +    ParallelArrayBuild(this, shape1, f);
> +  }
> +}
> +
> +// We duplicate code here to avoid extra cloning.

Instead of duplicating this entire function, you can use an arguments.length check in ParallelArrayConstruct2, or simply add the last argument to that, too, as you're just passing it through to ParallelArrayBuild, anyway.

@@ +157,5 @@
> +  }
> +}
> +
> +// We duplicate code here to avoid extra cloning.
> +function ParallelArrayConstruct3(shape, f, m) {

Speaking names here, too.

@@ +194,5 @@
> +  self.offset = 0;
> +  self.shape = shape;
> +
> +  var length;
> +  var xw, yw, zw;

Speaking names here, too.

@@ +198,5 @@
> +  var xw, yw, zw;
> +  var computefunc;
> +
> +  switch (shape.length) {
> +  case 1:

Here and everywhere else: two-space indent for case labels, four for their content. Plus braces around multi-line content.

@@ +229,5 @@
> +  }
> +
> +  var buffer = self.buffer = DenseArray(length);
> +
> +  parallel: for (;;) { // see ParallelArrayMap() to explain why for(;;) etc

Can you move the explanation here? Both because it's the first occurence and because building a parallel array is kinda the base case.

@@ +315,5 @@
> +
> +  parallel: for (;;) {
> +
> +    // Avoid parallel compilation if we are already nested in another
> +    // parallel section or the user told us not to.  The somewhat

Either strike the "not", or add "parallelize".

@@ +320,5 @@
> +    // artificial style of this code is working around some ion
> +    // limitations:
> +    //
> +    // - Breaking out of named blocks does not currently work;
> +    // - Unreachable Code Elim. can't properly handle if (a && b)

Do we have bugs for these limitations? If so, might be nice to reference them so we can check if they're resolved later.

Comment 9

[Shu-yu Guo [:shu]]

I think JS code should still follow the general Mozilla policy of 2-space indent, self-hosted or not.

Also, I feel rather strongly against javadoc-style documentation, which I find verbose and ugly. Why are we doing that for self-hosted JS code? If the point is to document function types and what they do, I find a short description combined with a Haskell-like function type declaration much more palatable:

// Compute the square root. Throws on negative inputs.
// sqrt : Number -> Number

Comment 10

[Niko Matsakis [:nmatsakis]]

Attachment: Move clone-at-callsite flags from JSFunction* to JSScript*

Moves the clone-at-callsite flag from JSFunction* to JSScript*.  This is more space-efficient and also more logical; you can only set this flag on JS functions.  Shu is looking now at alternatives to clone at callsite but I want to land the code we have in the meantime.

Comment 11

[Niko Matsakis [:nmatsakis]]

Attachment: Add intrinsics for self-hosted ParallelArray.js

Comment 12

[Niko Matsakis [:nmatsakis]]

Attachment: Add definition of ParallelDo()

Carrying over r+ from dvander

Comment 13

[Niko Matsakis [:nmatsakis]]

Attachment: Inline various functions important to ParallelArray

Previous patches had the actual inline code, this patch just trigger that code

Comment 14

[Niko Matsakis [:nmatsakis]]

Attachment: Switch to self-hosted parallel array

Comment 15

[Niko Matsakis [:nmatsakis]]

Attachment: Inline parallel array constructor

Inlines calls like "new ParallelArray(...)" or to the "NewParallelArray(view, ...)" intrinsic.

Comment 16

[Niko Matsakis [:nmatsakis]]

Attachment: Add tests and benchmarks for the new parallel array impl

Comment 17

[Luke Wagner [:luke]]

Comment on attachment 715813 [details] [diff] [review]
Move clone-at-callsite flags from JSFunction* to JSScript*

I'm not up to date with these paths you are changing; I think bhackett is the more appropriate reviewer given the interaction with TI.

Comment 18

[Brian Hackett [Laid off!]]

Comment on attachment 715813 [details] [diff] [review]
Move clone-at-callsite flags from JSFunction* to JSScript*

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

::: js/src/jsscript.h
@@ +488,5 @@
> +                                                each callsite. This is temporarily needed
> +                                                for ParallelArray selfhosted code until
> +                                                type information can be made context
> +                                                sensitive. See discussion in bug
> +                                                826148. */

Can you put this comment above the shouldCloneAtCallsite field?  The comments to the right are pretty antiquated.

@@ +702,4 @@
>      bool enclosingScriptsCompiledSuccessfully() const;
>  
>    private:
> +    JSObject *enclosingScopeNoAssert() const {

This interface seems overly complicated.  Can you move this code to enclosingStaticScope and remove the assert in enclosingStaticScope()?

Comment 19

[Niko Matsakis [:nmatsakis]]

> Can you put this comment above the shouldCloneAtCallsite field?
> The comments to the right are pretty antiquated.

I could make that change easily enough; all the other surrounding comments are to the right, though.

> This interface seems overly complicated.  Can you move this code to
> enclosingStaticScope and remove the assert in enclosingStaticScope()?

Sure (obviously, the check that enclosingStaticScope() is only called if enclosingScriptsCompiledSuccessfully() holds will not be performed as a result).

Comment 20

[Till Schneidereit [:till]]

Comment on attachment 715814 [details] [diff] [review]
Add intrinsics for self-hosted ParallelArray.js

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

We've now got three different documentation styles for functions in Selfhosting.cpp. That seems a bit excessive to me, so I'd propose using the style that's used in the majority of SpiderMonkey:
/*
 * Short overview.
 *
 * Details, potentially long.
 */

Having said that, I really appreciate the content of your comments!

Other than (well, actually including) that, only micro-nits.

::: js/src/vm/SelfHosting.cpp
@@ +189,5 @@
> +    id = AtomToId(Atomize(cx, "cloneAtCallsite", strlen("cloneAtCallsite")));
> +    if (!JSObject::getGeneric(cx, flags, flags, id, &propv))
> +        return false;
> +    if (ToBoolean(propv))
> +        funScript->shouldCloneAtCallsite = true;

Could there ever be a reason for setting this to `false`? I guess not, but it feels a bit weird that this only checks for and acts on `cloneAtCallsite` being `true`.

@@ +228,5 @@
> +    // |warmup| is true if this is a warmup or recovery phase.
> +    // Typically, if |warmup| is true, you will want to do less work.
> +    //
> +    // The |feedback| argument is optional.  If provided, it should be
> +    // a closure.  This closure will either be invoked with a double

s/either//

@@ +234,5 @@
> +    // a successful parallel execution.  If the number is infinity, then
> +    // parallel execution was abandoned and |func| was simply invoked
> +    // sequentially.
> +    //
> +    // See ParallelArray.js for examples.

"builtin/ParallelArray.js"

@@ +258,5 @@
> +js::intrinsic_NewParallelArray(JSContext *cx, unsigned argc, Value *vp)
> +{
> +    // Usage: NewParallelArray(init, ...args)
> +    //
> +    // Creates a new parallel array using an initialization function init. All

"|init|"

@@ +260,5 @@
> +    // Usage: NewParallelArray(init, ...args)
> +    //
> +    // Creates a new parallel array using an initialization function init. All
> +    // subsequent arguments are passed to init. The new instance will be
> +    // passed as the 'this' value.

"|this|"

@@ +393,5 @@
> +    return true;
> +}
> +
> +JSBool
> +js::intrinsic_ForceSequential(JSContext *cx, unsigned argc, Value *vp)

The name sounds like it actively forces sequential execution. Maybe "ShouldRunSequentially" or something along those lines?

Comment 21

[Niko Matsakis [:nmatsakis]]

Comment on attachment 715813 [details] [diff] [review]
Move clone-at-callsite flags from JSFunction* to JSScript*

Moved to bug 843656

Comment 22

[Niko Matsakis [:nmatsakis]]

Comment on attachment 715815 [details] [diff] [review]
Add definition of ParallelDo()

Moved to bug 843684

Comment 23

[Niko Matsakis [:nmatsakis]]

Comment on attachment 715819 [details] [diff] [review]
Inline various functions important to ParallelArray

Moved to Bug 843684

Comment 24

[Niko Matsakis [:nmatsakis]]

Comment on attachment 715814 [details] [diff] [review]
Add intrinsics for self-hosted ParallelArray.js

Moved to bug 843684

Comment 25

[David Anderson [:dvander] - inactive, e-mail if emergency]

Comment on attachment 715821 [details] [diff] [review]
Inline parallel array constructor

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

::: js/src/ion/MCallOptimize.cpp
@@ +1183,5 @@
> +    current->add(call);
> +    current->push(newObject);
> +    if (!resumeAfter(call))
> +        return InliningStatus_Error;
> +    if (!resumeAfter(newObject))

It's uncommon to have two resumeAfter instructions going to the same pc, because if the first call invalidates, we'll skip the second, the result of the first will be the result of the entire opcode.

If that isn't a problem in rivertrail code, you can just ignore this, and leave a comment so people are careful not to cargo cult.

Comment 26

[Till Schneidereit [:till]]

Comment on attachment 715820 [details] [diff] [review]
Switch to self-hosted parallel array

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

Almost through, but everything from filter onwards will have to wait until later today or tomorrow.

I really like the comments and the improved naming: much easier to review the code now, thanks!

In general, everything's looking pretty impressive and clean, so really, most comments are just nits.

General micro-nit: s/.  /. /g

::: js/src/builtin/ParallelArray.cpp
@@ +13,5 @@
>  #include "vm/GlobalObject.h"
> +#include "vm/ThreadPool.h"
> +#include "vm/ForkJoin.h"
> +
> +#include "builtin/ParallelArray.h"

"builtin" before "vm" and "vm/*" in alphabetical order

@@ +18,5 @@
>  
> +#include "ion/Ion.h"
> +#include "ion/MIR.h"
> +#include "ion/MIRGraph.h"
> +#include "ion/IonCompartment.h"

"IonCompartment" before "Mir*"

@@ +117,2 @@
>          return NULL;
> +    JS_ASSERT(ctorValue.toObject().isFunction());

Should assert isObject here, too

@@ +167,3 @@
>  
> +                // addDefiniteProperties() above should have added one
> +                // property for of the fixed slots:

"for each of"

::: js/src/builtin/ParallelArray.h
@@ +39,3 @@
>      //
> +    // NOTE: This object will NOT have the correct type object! It is
> +    // up to you the caller to adjust the type object appropriately

"[..] you, the caller, [..]"

::: js/src/builtin/ParallelArray.js
@@ +29,5 @@
> +/**
> + * Divides |numItems| items amongst |numSlices| slices.  The result
> + * is an array containing multiple values per slice: the start
> + * index, end index, current position, and some padding.  The
> + * current position is initally the same as the start index.  To

"initially"

@@ +145,5 @@
> +function ParallelArrayConstructFromFunction(shape, func) {
> +  if (typeof shape === "number") {
> +    var length = shape >>> 0;
> +    if (length !== shape)
> +      ThrowError(JSMSG_PAR_ARRAY_BAD_ARG, "");

Add IsFunction check:
if (!IsCallable(func))
    ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(1, func));

@@ +146,5 @@
> +  if (typeof shape === "number") {
> +    var length = shape >>> 0;
> +    if (length !== shape)
> +      ThrowError(JSMSG_PAR_ARRAY_BAD_ARG, "");
> +    ParallelArrayBuild(this, [length], func);

Ah, I now get how I totally mis-interpreted this in my last review. The comment helped a lot with that, thanks.

@@ +147,5 @@
> +    var length = shape >>> 0;
> +    if (length !== shape)
> +      ThrowError(JSMSG_PAR_ARRAY_BAD_ARG, "");
> +    ParallelArrayBuild(this, [length], func);
> +  } else {

Can you add an `if (!shape || typeof shape.length !== "number")` and the corresponding `ThrowError` here?

@@ +166,5 @@
> + * |mode| argument was supplied to specify whether parallel execution
> + * was expected and so forth.  Only used during our internal unit
> + * tests.
> + */
> +function ParallelArrayConstructFromFunctionMode(shape, func, mode) {

Is there a reason for not just using this version of the function everywhere? Given that ParallelArrayBuild doesn't do anything weird with the |mode| arg, doing so shouldn't introduce any semantic or performance changes.

@@ +189,5 @@
> +/**
> + * Internal function used when constructing new parallel arrays.  The
> + * NewParallelArray() intrinsic takes a ctor function which it invokes
> + * with the given shape, buffer, offset.  The this parameter will be
> + * the newly constructed parallel array.

"newly-constructed"

@@ +196,5 @@
> +  this.shape = shape;
> +  this.buffer = buffer;
> +  this.offset = offset;
> +
> +  switch (shape.length) {

Maybe add a reference to bug 838906 here, too?

@@ +303,5 @@
> +  }
> +
> +  function fill2(indexStart, indexEnd) {
> +    var x = (indexStart / yDimension) | 0;
> +    var y = indexStart - x*yDimension;

Whitespace around `*`

@@ +314,5 @@
> +    }
> +  }
> +
> +  function fill3(indexStart, indexEnd) {
> +    var x = (indexStart / (yDimension*zDimension)) | 0;

ditto

@@ +315,5 @@
> +  }
> +
> +  function fill3(indexStart, indexEnd) {
> +    var x = (indexStart / (yDimension*zDimension)) | 0;
> +    var r = indexStart - x*yDimension*zDimension;

ditto

@@ +317,5 @@
> +  function fill3(indexStart, indexEnd) {
> +    var x = (indexStart / (yDimension*zDimension)) | 0;
> +    var r = indexStart - x*yDimension*zDimension;
> +    var y = (r / zDimension) | 0;
> +    var z = r - y*zDimension;

ditto

@@ +340,5 @@
> +  }
> +}
> +
> +/**
> + * Creates a new parallel array by applying |func(e, i, c)| for each

s/c/self/

@@ +341,5 @@
> +}
> +
> +/**
> + * Creates a new parallel array by applying |func(e, i, c)| for each
> + * element |e| with index |i| (|c| is the array itself).  Note that

The aside isn't needed with |c| changed to |self|

@@ +345,5 @@
> + * element |e| with index |i| (|c| is the array itself).  Note that
> + * this always operates on the outermost dimension only.
> + */
> +function ParallelArrayMap(func, mode) {
> +  var self = this;

Add check for |this| really being a ParallelArray instance.
Add IsCallable check:
if (!IsCallable(func))
    ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, func));

@@ +366,5 @@
> +
> +  // Sequential fallback:
> +  CHECK_SEQUENTIAL(mode);
> +  for (var i = 0; i < length; i++)
> +    buffer[i] = func(self.get(i), i, self);

Array.prototype.map has an `if (i in self)` check here. Do we need that for ParallelArray.prototype.map et al, too?

@@ +373,5 @@
> +  function mapSlice(sliceId, numSlices, warmup) {
> +    var chunkPos = info[SLICE_POS(sliceId)];
> +    var chunkEnd = info[SLICE_END(sliceId)];
> +
> +    if (warmup && chunkEnd > chunkPos)

chunkEnd > chunkPos + 1

@@ +393,5 @@
> + * Reduces the elements in a parallel array's outermost dimension
> + * using the given reduction function.
> + */
> +function ParallelArrayReduce(func, mode) {
> +  var self = this;

Add check for |this| really being a ParallelArray instance.
Add IsCallable check:
if (!IsCallable(func))
    ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, func));

@@ +435,5 @@
> +    // (*) This function is carefully designed so that the warmup
> +    // (which executes with chunkStart === chunkPos) will execute
> +    // all potential loads and stores. In particular, the warmup run
> +    // processes two chunks rather than one.  Moreover, it stores accumulator
> +    // into subreductions and then loads it again ensure that the load

"[..] again to ensure [..]"

@@ +436,5 @@
> +    // (which executes with chunkStart === chunkPos) will execute
> +    // all potential loads and stores. In particular, the warmup run
> +    // processes two chunks rather than one.  Moreover, it stores accumulator
> +    // into subreductions and then loads it again ensure that the load
> +    // is executed during the warmup, as it will certainly be run

s/run/executed/

@@ +475,5 @@
> + * of elements |0..i|.  This is the generalization
> + * of partial sum.
> + */
> +function ParallelArrayScan(func, mode) {
> +  var self = this;

Add check for |this| really being a ParallelArray instance.
Add IsCallable check:
if (!IsCallable(func))
    ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(0, func));

@@ +479,5 @@
> +  var self = this;
> +  var length = self.shape[0];
> +
> +  if (length === 0)
> +    ThrowError(JSMSG_PAR_ARRAY_REDUCE_EMPTY);

Maybe generalize to JSMSG_PAR_ARRAY_EMPTY with "reduce" or "scan" as additional arg to ThrowError?

@@ +505,5 @@
> +    for (var i = 1; i < numSlices - 1; i++)
> +      accumulator = intermediates[i] = func(accumulator, buffer[finalElement(i)]);
> +
> +    // Reset the current position information for each slice, but
> +    // convert from chunks to indicies (see comment on phase2()).

s/indicies/indices/

@@ +532,5 @@
> +    return accumulator;
> +  }
> +
> +  /**
> +   * In phase 1, we divide the source array into numSlices slices and

|numSlices|

@@ +533,5 @@
> +  }
> +
> +  /**
> +   * In phase 1, we divide the source array into numSlices slices and
> +   * compute scan on each slice sequentially as it were the entire

"[..] as if it were [..]"

@@ +537,5 @@
> +   * compute scan on each slice sequentially as it were the entire
> +   * array.  This function is responsible for computing one of those
> +   * slices.
> +   *
> +   * So, if we have an array [A,B,C,D,E,F,G,H,I], numSlices == 3, and our function

|numSlices == 3|

@@ +538,5 @@
> +   * array.  This function is responsible for computing one of those
> +   * slices.
> +   *
> +   * So, if we have an array [A,B,C,D,E,F,G,H,I], numSlices == 3, and our function
> +   * |f| is sum, then would wind up computing a result array like:

s/|f|/|func|/
s/would/we/

@@ +638,5 @@
> +    if (warmup)
> +      indexEnd = std_Math_min(indexEnd, indexPos + CHUNK_SIZE);
> +
> +    var intermediate = intermediates[sliceId - 1];
> +    for (; indexPos < indexEnd; indexPos++)

Braces, because the loop content spans two lines

@@ +651,5 @@
> + *
> + * - targets: The index targets[i] indicates where the ith element
> + *            should appear in the result.
> + *
> + * - zero: what zero value to use for indices in the output array that

I like "defaultValue", as used in the RiverTrail prototype's docs

@@ +652,5 @@
> + * - targets: The index targets[i] indicates where the ith element
> + *            should appear in the result.
> + *
> + * - zero: what zero value to use for indices in the output array that
> + *         are never targeted

.

@@ +654,5 @@
> + *
> + * - zero: what zero value to use for indices in the output array that
> + *         are never targeted
> + *
> + * - func: The conflict function.  Used to resolve what happens if two

ditto for "conflictFunction"

@@ +662,5 @@
> + *         targets[j]).  If no conflict function is provided, it is an
> + *         error if targets[i] == targets[j].
> + *
> + * - length: length of the output array (if not specified, uses
> + *           the length of the intput.

"defaults to length of input"?

@@ +667,5 @@
> + *
> + * - mode: internal debugging specification
> + */
> +function ParallelArrayScatter(targets, zero, func, length, mode) {
> +

remove empty line

@@ +668,5 @@
> + * - mode: internal debugging specification
> + */
> +function ParallelArrayScatter(targets, zero, func, length, mode) {
> +
> +  var self = this;

Add check for |this| really being a ParallelArray instance and |targets| being array-like.
Add IsCallable check:
if (!IsCallable(func))
    ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(2, func));

@@ +715,5 @@
> +  // |targets.length| approximately equals |length|, especially for
> +  // special cases like collision-free scatters and permutations.
> +
> +  if (targets.length >>> 0 !== targets.length)
> +    ThrowError(JSMSG_BAD_ARRAY_LENGTH, "");

"ParallelArray.prototype.scatter"

@@ +719,5 @@
> +    ThrowError(JSMSG_BAD_ARRAY_LENGTH, "");
> +
> +  var targetsLength = std_Math_min(targets.length, self.length);
> +
> +  if (length && length >>> 0 !== length)

the |length &&| doesn't seem necessary

@@ +720,5 @@
> +
> +  var targetsLength = std_Math_min(targets.length, self.length);
> +
> +  if (length && length >>> 0 !== length)
> +    ThrowError(JSMSG_BAD_ARRAY_LENGTH, "");

"ParallelArray.prototype.scatter"

@@ +747,5 @@
> +  }
> +
> +  function forceDivideOutputRange() {
> +    return mode && mode.strategy && mode.strategy == "divide-output-range";
> +    return func(elem1, elem2);

remove

@@ +803,5 @@
> +    // Subtle: because we will be mutating the localbuffers and
> +    // conflict arrays in place, we can never replay an entry in the
> +    // target array for fear of inducing a conflict where none existed
> +    // before.  Therefore, we must proceed not by chunks but rather by
> +    // individual indices,

s/,/./

@@ +807,5 @@
> +    // individual indices,
> +    var numSlices = ParallelSlices();
> +    var info = ComputeAllSliceBounds(targetsLength, numSlices);
> +
> +    var localbuffers = NewDenseArray(numSlices);

"localBuffers"

@@ +810,5 @@
> +
> +    var localbuffers = NewDenseArray(numSlices);
> +    for (var i = 0; i < numSlices; i++)
> +        localbuffers[i] = NewDenseArray(length);
> +    var localconflicts = NewDenseArray(numSlices);

"localConflicts"

@@ +818,5 @@
> +    // Initialize the 0th buffer, which will become the output.  For
> +    // the other buffers, we track which parts have been written to
> +    // using the conflict buffer so they do not need to be
> +    // initialized.
> +    var outputbuffer = localbuffers[0];

"outputBuffer"

@@ +820,5 @@
> +    // using the conflict buffer so they do not need to be
> +    // initialized.
> +    var outputbuffer = localbuffers[0];
> +    for (var i = 0; i < length; i++)
> +      outputbuffer[i] = zero;

Should this use UnsafeSetElement?

@@ +855,5 @@
> +    function mergeBuffers() {
> +      var buffer = localbuffers[0];
> +      var conflicts = localconflicts[0];
> +      for (var i = 1; i < numSlices; i++) {
> +        var otherbuffer = localbuffers[i];

"otherBuffer"

@@ +856,5 @@
> +      var buffer = localbuffers[0];
> +      var conflicts = localconflicts[0];
> +      for (var i = 1; i < numSlices; i++) {
> +        var otherbuffer = localbuffers[i];
> +        var otherconflicts = localconflicts[i];

"otherConflicts"

@@ +863,5 @@
> +            if (conflicts[j]) {
> +              buffer[j] = collide(otherbuffer[j], buffer[j]);
> +            } else {
> +              buffer[j] = otherbuffer[j];
> +              conflicts[j] = true;

Why no UnsafeSetElement in these three cases?

@@ +876,5 @@
> +    var buffer = NewDenseArray(length);
> +    var conflicts = NewDenseArray(length);
> +
> +    for (var i = 0; i < length; i++)
> +      buffer[i] = zero;

Should this use UnsafeSetElement?

@@ +894,5 @@
> +  }
> +
> +  function checkTarget(t) {
> +      if ((t | 0) !== t)
> +        ThrowError(JSMSG_PAR_ARRAY_BAD_ARG, ".prototype.scatter");

A more helpful error message would be pretty good here, I think. Going from "invalid arg" to "one of the entries in |targets| isn't an integer" seems quite a stretch.

Comment 27

[Till Schneidereit [:till]]

Comment on attachment 715820 [details] [diff] [review]
Switch to self-hosted parallel array

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

Very nice!

Only a few more feedback items and nits and this is good to go.

I thought about the private properties issue some more. How about storing them in a WeakMap and using a utility function to retrieve them as local vars at the beginning of all major methods? Something along the lines of
var {buffer, shape, ...} = GetInternalPAProperties(this);
I don't know enough about the interactions between TI and WeakMaps to be sure, but it seems to me that this would enable effective lookup while completely hiding the internal properties from user code.

Can you do another go-over and attach a version with the feedback addressed? That'd get a very quick r+.

::: js/src/builtin/ParallelArray.js
@@ +906,5 @@
> + * The familiar filter() operation applied across the outermost
> + * dimension.
> + */
> +function ParallelArrayFilter(func, mode) {
> +  var self = this;

Add check for |this| really being a ParallelArray instance.
Add IsCallable check:
if (!IsCallable(func))
    ThrowError(JSMSG_NOT_FUNCTION, DecompileArg(2, func));

@@ +928,5 @@
> +    // |survivors| containing a bitset for each chunk, indicating
> +    // which members of the chunk survived.  We also keep an array
> +    // |counts| containing the total number of items that are being
> +    // preserved from within one slice.
> +    var counts = NewDenseArray(numSlices);

Would typed arrays be more efficient here and in similar situations elsewhere? For one, you wouldn't need to initialize the counts to 0, but additionally, they should be more space-efficient and might enable faster lookup. It might even be possible to use one typed array with different views into it passed to the parallely-executed function, but you certainly know more about that than I do.

@@ +1019,5 @@
> +    // because we are already checking for when count==total.
> +    var chunkStart = info[SLICE_START(sliceId)];
> +    var chunkEnd = info[SLICE_END(sliceId)];
> +    for (var chunk = chunkStart; chunk < chunkEnd; chunk++) {
> +      var chunkBits = survivors[chunk];

Maybe add 
if (!chunkBits)
  continue;
?

@@ +1041,5 @@
> + * N must be evenly divisible by 4 in that case.
> + */
> +function ParallelArrayPartition(amount) {
> +  if (amount >>> 0 !== amount)
> +    ThrowError(JSMSG_BAD_ARRAY_LENGTH, ""); // XXX

Use JSMSG_PAR_ARRAY_BAD_ARG

@@ +1047,5 @@
> +  var length = this.shape[0];
> +  var partitions = (length / amount) | 0;
> +
> +  if (partitions * amount !== length)
> +    ThrowError(JSMSG_BAD_ARRAY_LENGTH, ""); // XXX

Use JSMSG_PAR_ARRAY_BAD_PARTITION

@@ +1061,5 @@
> + * a [X, Y, ...] vector, you get a [X*Y, ...] vector.
> + */
> +function ParallelArrayFlatten() {
> +  if (this.shape.length < 2)
> +    ThrowError(JSMSG_BAD_ARRAY_LENGTH, ""); // XXX

Use JSMSG_PAR_ARRAY_ALREADY_FLAT

@@ +1073,5 @@
> +//
> +// Accessors and utilities.
> +//
> +
> +/** Specialized variant of get() for one-dimensional case */

Beginning and end of comment on new lines here and below.

@@ +1076,5 @@
> +
> +/** Specialized variant of get() for one-dimensional case */
> +function ParallelArrayGet1(i) {
> +  if (i === undefined)
> +    return undefined;

Check for |i| being an integer?

@@ +1084,5 @@
> +/** Specialized variant of get() for two-dimensional case */
> +function ParallelArrayGet2(x, y) {
> +  var xDimension = this.shape[0];
> +  var yDimension = this.shape[1];
> +  if (x === undefined)

Check for |x, y| being integers?

@@ +1089,5 @@
> +    return undefined;
> +  if (x >= xDimension)
> +    return undefined;
> +  if (y === undefined)
> +    return NewParallelArray(ParallelArrayView, [yDimension], this.buffer, this.offset + x*yDimension);

Spaces around *

@@ +1092,5 @@
> +  if (y === undefined)
> +    return NewParallelArray(ParallelArrayView, [yDimension], this.buffer, this.offset + x*yDimension);
> +  if (y >= yDimension)
> +    return undefined;
> +  var offset = y + x*yDimension;

ditto

@@ +1101,5 @@
> +function ParallelArrayGet3(x, y, z) {
> +  var xDimension = this.shape[0];
> +  var yDimension = this.shape[1];
> +  var zDimension = this.shape[2];
> +  if (x === undefined)

Check for |x, y, z| being integers?

@@ +1107,5 @@
> +  if (x >= xDimension)
> +    return undefined;
> +  if (y === undefined)
> +    return NewParallelArray(ParallelArrayView, [yDimension, zDimension],
> +                            this.buffer, this.offset + x*yDimension*zDimension);

Spaces around *

@@ +1112,5 @@
> +  if (y >= yDimension)
> +    return undefined;
> +  if (z === undefined)
> +    return NewParallelArray(ParallelArrayView, [zDimension],
> +                            this.buffer, this.offset + y*zDimension + x*yDimension*zDimension);

ditto

@@ +1115,5 @@
> +    return NewParallelArray(ParallelArrayView, [zDimension],
> +                            this.buffer, this.offset + y*zDimension + x*yDimension*zDimension);
> +  if (z >= zDimension)
> +    return undefined;
> +  var offset = z + y*zDimension + x*yDimension*zDimension;

ditto

@@ +1131,5 @@
> +  // multipled by its corresponding entry in the |products|
> +  // array, counting in reverse.  So if |coords| is [a,b,c,d],
> +  // then you get |a*BCD + b*CD + c*D + d|.
> +  var offset = this.offset;
> +  var sdimensionality = this.shape.length;

sDimensionality

@@ +1132,5 @@
> +  // array, counting in reverse.  So if |coords| is [a,b,c,d],
> +  // then you get |a*BCD + b*CD + c*D + d|.
> +  var offset = this.offset;
> +  var sdimensionality = this.shape.length;
> +  var cdimensionality = coords.length;

cDimensionality

@@ +1134,5 @@
> +  var offset = this.offset;
> +  var sdimensionality = this.shape.length;
> +  var cdimensionality = coords.length;
> +  for (var i = 0; i < cdimensionality; i++) {
> +    if (coords[i] >= this.shape[i])

Check for coords[i] being an integer?

@@ +1152,5 @@
> +  return this.shape[0];
> +}
> +
> +function ParallelArrayToString() {
> +  var l = this.shape[0];

"length"

@@ +1158,5 @@
> +    return "";
> +
> +  var open, close;
> +  if (this.shape.length > 1) {
> +    open = "<"; close = ">";

new line after ;

@@ +1176,5 @@
> +/**
> + * Internal debugging tool: checks that the given `mode` permits
> + * sequential execution
> + */
> +function CheckSequential(mode) {

Maybe "AssertSequential" would be better? Took me a while to understand that this really does assert instead of returning true or false.

@@ +1180,5 @@
> +function CheckSequential(mode) {
> +  if (!mode || mode.mode === "seq")
> +    return;
> +
> +  ThrowError(JSMSG_WRONG_VALUE, "par", "seq");

How about
if (mode && mode.mode === "par")
  ThrowError(JSMSG_WRONG_VALUE, "par", "seq");
?
Also, JSMSG_WRONG_VALUE isn't defined in my js.msg. Is that contained in another patch?

@@ +1184,5 @@
> +  ThrowError(JSMSG_WRONG_VALUE, "par", "seq");
> +}
> +
> +/**
> + * Internal debugging tool: returns a function to be supplied

"[..] supplied to"

@@ +1187,5 @@
> +/**
> + * Internal debugging tool: returns a function to be supplied
> + * ParallelDo() that will check that the parallel results
> + * bailout/succeed as expected.  Returns null if not in no mode is
> + * supplied.

The last sentence seems to be a bit mutilated.

@@ +1207,5 @@
> +    else
> +      result = "bailout";
> +
> +    if (mode.expect === "mixed") {
> +      if (result !== "success" && result !== "bailout")

|result === "disqualified"| to make it clearer that this is what's being tested here?

@@ +1208,5 @@
> +      result = "bailout";
> +
> +    if (mode.expect === "mixed") {
> +      if (result !== "success" && result !== "bailout")
> +        ThrowError(JSMSG_WRONG_VALUE, mode.expect, result);

Seems a bit weird that this error indicates an expected result that can't ever occur in practice.

@@ +1244,5 @@
> +SetScriptHints(ParallelArrayGet1,       { cloneAtCallsite: true, inline: true });
> +SetScriptHints(ParallelArrayGet2,       { cloneAtCallsite: true, inline: true });
> +SetScriptHints(ParallelArrayGet3,       { cloneAtCallsite: true, inline: true });
> +
> +// Unit Test Functions

Either delete or activate these.

Comment 28

[Norbert Lindenberg]

(In reply to Till Schneidereit [:till] from comment #27)

> I thought about the private properties issue some more. How about storing
> them in a WeakMap and using a utility function to retrieve them as local
> vars at the beginning of all major methods? Something along the lines of
> var {buffer, shape, ...} = GetInternalPAProperties(this);
> I don't know enough about the interactions between TI and WeakMaps to be
> sure, but it seems to me that this would enable effective lookup while
> completely hiding the internal properties from user code.

That's what I ended up doing for the Intl objects:
https://bug769872.bugzilla.mozilla.org/attachment.cgi?id=715893

It has drawbacks, in particular WeakMap instances are per global, so an object loses its internal properties when moved to a different global. Private symbols are likely a better solution, but we don't have them yet.

Comment 29

[Norbert Lindenberg]

Comment on attachment 715820 [details] [diff] [review]
Switch to self-hosted parallel array

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

Just a few comments, not a review.

::: js/src/Makefile.in
@@ +916,4 @@
>  selfhosting_srcs := \
>    $(srcdir)/builtin/Utilities.js \
>    $(srcdir)/builtin/Array.js \
> +  $(srcdir)/builtin/ParallelArray.js \

Please keep this list in alphabetical order, except for Utilities.js.

::: js/src/builtin/ParallelArray.js
@@ +37,5 @@
> +function ComputeAllSliceBounds(numItems, numSlices) {
> +  var info = [];
> +  for (var i = 0; i < numSlices; i++) {
> +    var [start, end] = ComputeSliceBounds(numItems, i, numSlices);
> +    info.push(SLICE_INFO(start, end));

I don't see a reference to any specification on this bug, and without a spec it's hard to say whether using push here is correct. But most likely it's not, because using it this way gives client code an opportunity to interfere with the behavior of this function, e.g.:
Array.prototype.push = 17;

To avoid such interference, use
callFunction(std_Array_push, info, SLICE_INFO(start, end));

There are a number of other method calls in this file that likely should be calls to standard built-in functions; they all have to be treated that way.

@@ +110,5 @@
> +function ParallelArrayConstructEmpty() {
> +  this.buffer = [];
> +  this.offset = 0;
> +  this.shape = [0];
> +  this.get = ParallelArrayGet1;

Are you sure the spec would say [[Put]], not [[DefineOwnProperty]] for these operations? [[Put]] gives client code an opportunity to interfere with the behavior of this constructor, e.g., with
    Object.defineProperty(Object.prototype, "buffer", {
        set: function(value) {
            throw new Error("Gotcha!");
        },
        enumerable: false,
        configurable: true
    });

The safe way to do this in self-hosted code is:
    std_Object_defineProperty(this, "buffer", {value: [], writable: true, enumerable: true, configurable: true});

Intl.js has a little helper function, defineProperty, for this:
https://bug769872.bugzilla.mozilla.org/attachment.cgi?id=715893
and Jeff suggested replacing that function with an intrinsic.

There are a number of other property assignments of this kind in this file.

Comment 30

[Niko Matsakis [:nmatsakis]]

Attachment: Switch to self-hosted parallel array

Address Till's comments, adding FIXMEs in some cases.

Comment 31

[Niko Matsakis [:nmatsakis]]

Attachment: Add tests and benchmarks for the new parallel array impl

Comment 32

[Till Schneidereit [:till]]

Comment on attachment 718040 [details] [diff] [review]
Switch to self-hosted parallel array

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

Very nice!

r=me with the last few nits addressed. For all comments in my last review that you didn't address and that I didn't point out again, I'm assuming that you've got good reasons for ignoring them.

Also, I care less about the two spaces after a "." than it might seem, so feel free to leave them in. ;)

::: js/src/builtin/ParallelArray.cpp
@@ +15,3 @@
>  #include "vm/GlobalObject.h"
> +#include "vm/ThreadPool.h"
> +#include "vm/ForkJoin.h"

Alphabetical order, please

::: js/src/builtin/ParallelArray.h
@@ +13,5 @@
>  #include "jsobj.h"
>  
> +#include "ion/Ion.h"
> +#include "vm/ThreadPool.h"
> +#include "vm/ForkJoin.h"

Alphabetical order, please (sorry, didn't see this last time)

::: js/src/builtin/ParallelArray.js
@@ +40,5 @@
> +  // FIXME(bug 844890): Use typed arrays here.
> +  var info = [];
> +  for (var i = 0; i < numSlices; i++) {
> +    var [start, end] = ComputeSliceBounds(numItems, i, numSlices);
> +    ARRAY_PUSH(info, SLICE_INFO(start, end));

Sorry, I should have seen this. Thanks, Norbert, for catching it.

@@ +141,5 @@
> + * Wrapper around |ParallelArrayConstructFromComprehension()| for the
> + * case where 2 arguments are supplied.  This is typically what users will
> + * invoke. We provide an explicit two-argument version rather than
> + * relying on JS's semantics for absent arguments because it simplifies
> + * the ion code that does inlining of PA constructors.

Ah, I understand. Thanks for the comment.

@@ +172,5 @@
> +
> +  if (typeof shape === "number") {
> +    var length = shape >>> 0;
> +    if (length !== shape)
> +      ThrowError(JSMSG_PAR_ARRAY_BAD_ARG, "");

Missed that last time around: Can you insert a meaningful value for the second arg?

@@ +494,5 @@
> +  var self = this;
> +  var length = self.shape[0];
> +
> +  if (length === 0)
> +    ThrowError(JSMSG_PAR_ARRAY_REDUCE_EMPTY);

Nit: The message is still a bit off, here

@@ +679,5 @@
> + *   targets[j]).  If no conflict function is provided, it is an error
> + *   if targets[i] == targets[j].
> + *
> + * - length: length of the output array (if not specified, uses the
> + *   length of the intput.

Ok, your phrasing is as good as my suggestion. Please fix "intput." and add a closing brace, though.

@@ +1188,5 @@
> +  return this.shape[0];
> +}
> +
> +function ParallelArrayToString() {
> +  var l = this.shape[0];

You don't like "length" here?

@@ +1205,5 @@
> +  for (var i = 0; i < l - 1; i++) {
> +    result += open + String(this.get(i)) + close;
> +    result += ",";
> +  }
> +  result += open + String(this.get(l-1)) + close;

spaces around "-" (missed this earlier, sorry)

@@ +1222,5 @@
> +/**
> + * Internal debugging tool: returns a function to be supplied to
> + * ParallelDo() that will check that the parallel results
> + * bailout/succeed as expected.  Returns null if not in no mode is
> + * supplied.

Last sentence still doesn't seem right to me

Comment 33

[Till Schneidereit [:till]]

Comment on attachment 718042 [details] [diff] [review]
Add tests and benchmarks for the new parallel array impl

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

As just discussed on IRC, tests don't need reviewing.

So, r=me on those grounds, with the left-over files in jit-test/benchmarks removed.

Comment 34

[Niko Matsakis [:nmatsakis]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/84e8e319f735

Comment 35

[:Ms2ger (he/him; ⌚ UTC+1/+2)]

Backed out:

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

for failing the rootanalysis build, which is now unhidden:

https://tbpl.mozilla.org/php/getParsedLog.php?id=20243294&tree=Mozilla-Inbound

(Note that failure handling was broken at that point; this was fixed in <https://hg.mozilla.org/integration/mozilla-inbound/rev/fc74c83f5ed5>.)

Comment 36

[Niko Matsakis [:nmatsakis]]

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

Comment 37

[Ryan VanderMeulen [:RyanVM]]

Backed out for intermittent jit-test failures.
https://hg.mozilla.org/integration/mozilla-inbound/rev/37f8e72f5124

https://tbpl.mozilla.org/php/getParsedLog.php?id=20307072&tree=Mozilla-Inbound

TEST-UNEXPECTED-FAIL | testGCOutOfMemory | (function() {    var array = [];    for (var i = max >> 2; i != 0;) {        --i;        array.push({});    }})();

TEST-UNEXPECTED-FAIL | jit_test.py --no-jm        | /builds/slave/m-in-l64-000000000000000000000/build/js/src/jit-test/tests/parallelarray/bailout-executed.js: /builds/slave/m-in-l64-000000000000000000000/build/js/src/jit-test/tests/parallelarray/bailout-executed.js:17:0 Error: expected mixed but found disqualified

Comment 38

[Ryan VanderMeulen [:RyanVM]]

FWIW, the testGCOutOfMemory failure is being handled in bug 847579.

Comment 39

[Ryan VanderMeulen [:RyanVM]]

FYI, we hit this on a Windows build too:
https://tbpl.mozilla.org/php/getParsedLog.php?id=20315900&tree=Mozilla-Inbound

TEST-UNEXPECTED-FAIL | jit_test.py --no-jm        | e:\builds\moz2_slave\m-in-w32-pgo-00000000000000000\build\js\src\jit-test\tests\parallelarray\bailout-executed.js: e:\builds\moz2_slave\m-in-w32-pgo-00000000000000000\build\js\src\jit-test\tests\parallelarray\bailout-executed.js:17:0 Error: expected mixed but found disqualified

Comment 40

[Niko Matsakis [:nmatsakis]]

I have just now observed this error locally, but it's hard to reproduce.  I have a working theory of what causes it (GC or other transient error occurring at an inconvenient time) but it's hard to verify.  I'll try to see if I can force such errors to occur with more frequency and thus perhaps try to validate the hypothesis.

Comment 41

[Niko Matsakis [:nmatsakis]]

Attachment: Don't report test failures when method compilation is skipped

This is an attempt to resolve some of the random orange failures.  My hypothesis (not fully verified) is that these can occur when a GC or other similar event causes compilation of a method to be skipped.  Therefore, I have refined the test harness not to report an error in that case.

To some extent this is suboptimal, since the test result could best be categorized as "inconclusive" rather than "pass", but I think for now erring on the side of green is better.  The only real solution to this, I think, would be a kind of meta analysis across try runs on TBPL to watch out for tests that are yielding "inconclusive" results "too frequently".

Comment 42

[Niko Matsakis [:nmatsakis]]

Attachment: Eliminate use of branchTestBool()

This patch eliminates the use of branchTestBool() altogether, since it proved to be troublesome.  There is more explanation of my thoughts in the patch header itself.

Comment 43

[Niko Matsakis [:nmatsakis]]

Attachment: Switch to self-hosted parallel array

(Just refreshing this patch with the latest verison; carrying over r+ from till)

Comment 44

[Niko Matsakis [:nmatsakis]]

Attachment: Inline parallel array constructor

(Updating patch with latest version; carrying over r+ from dvander)

Comment 45

[Niko Matsakis [:nmatsakis]]

Attachment: Add tests and benchmarks for the new parallel array impl

(Updating this patch with the latest version; carrying over r+ from till)

Comment 46

[Nicolas B. Pierron [:nbp]]

Comment on attachment 721225 [details] [diff] [review]
Eliminate use of branchTestBool()

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

r=me once the following comments are addressed.

::: js/src/ion/CodeGenerator.cpp
@@ +907,5 @@
>          return false;
>  
>      // branch to the OOL failure code if false is returned
> +    masm.and32(Imm32(1), ReturnReg); // bool return type guarantees the low bit
> +    masm.branchTest32(Assembler::Zero, ReturnReg, ReturnReg, bail);

replace these 2 lines in all 3 functions by:
  masm.branchTest32(…, Imm32(1), …, bail)

Comment 47

[Till Schneidereit [:till]]

Comment on attachment 721224 [details] [diff] [review]
Don't report test failures when method compilation is skipped

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

As a band-aid, this seems fine. But as it causes us to retry compilation of scripts again and again that can't be compiled, it might entail a non-trivial performance hit, right? Did you test that or otherwise know that it isn't a problem?

Also, don't we have any way of finding out if the compilation failure is temporary? If not, then maybe we should add a counter that makes the failure permanent after n failed attempts?

::: js/src/vm/ParallelDo.cpp
@@ +458,5 @@
> +
> +              case Method_Skipped:
> +                // In fact, Method_Skipped can indicate both transient
> +                // and non-transient conditions, but to avoid random
> +                // orange we simplify by treating this return code as

Are we just avoiding random orange, here, or is this a failure mode that can occur in real code, too? If so, please change the comment accordingly. If not, can you explain in the comment why this only affects tbpl?

@@ +699,5 @@
> +                break;
> +            }
> +            JSString *result = JS_NewStringCopyZ(cx, resultString);
> +
> +            feedbackArgs[0].setString(result);

IIUC, this is called somewhat oftenly, right? If so, can you add the strings to the atoms table.

Comment 48

[Niko Matsakis [:nmatsakis]]

Till, I will revise the patch because I still see occasional failures, so this fix seems to be insufficient.  Not sure what the right fix will look like yet since I don't quite know what's causing the failures. :/

> Are we just avoiding random orange, here, or is this a failure mode that can occur in real code, too? If so, please change the comment accordingly. If not, can you explain in the comment why this only affects tbpl?

The goal is to avoid random orange, but the condition can occur in real code.  In real code, though, there are no 'mode' asserts, so execution just transparently occurs sequentially rather than in parallel (the same thing occurs with ion, where sometimes you wind up with interpreted execution instead of running with ion-compiled code simply due to an ill-timed GC run).

> IIUC, this is called somewhat oftenly, right? If so, can you add the strings to the atoms table.

It is only called in debug mode. Production code never specifies a mode as it is not part of the official API. I wasn't sure whether I should add an atom for such a case.

Comment 49

[Till Schneidereit [:till]]

(In reply to Niko Matsakis [:nmatsakis] from comment #48)
> Till, I will revise the patch because I still see occasional failures, so
> this fix seems to be insufficient.  Not sure what the right fix will look
> like yet since I don't quite know what's causing the failures. :/

That sucks; wish you good hunting!

> 
> > Are we just avoiding random orange, here, or is this a failure mode that can occur in real code, too? If so, please change the comment accordingly. If not, can you explain in the comment why this only affects tbpl?
> 
> The goal is to avoid random orange, but the condition can occur in real
> code.  In real code, though, there are no 'mode' asserts, so execution just
> transparently occurs sequentially rather than in parallel (the same thing
> occurs with ion, where sometimes you wind up with interpreted execution
> instead of running with ion-compiled code simply due to an ill-timed GC run).

Ah, ok. Depending on what your final solution will look like, maybe you can document this or similar code as working around a debug-only issue?

> 
> > IIUC, this is called somewhat oftenly, right? If so, can you add the strings to the atoms table.
> 
> It is only called in debug mode. Production code never specifies a mode as
> it is not part of the official API. I wasn't sure whether I should add an
> atom for such a case.

I see. In that case, I don't think atoms are required, no.

Comment 50

[Niko Matsakis [:nmatsakis]]

Attachment: Do not reset use count when invalidating a parallel IonScript

The use count refers strictly to sequential execution, so do not reset when invalidating a parallel IonScript.  This was leading to random orange because, in some scenarios, we would invalidate the parallel script but leave the sequential script intact (for example, if the script took actions that cannot be performed in par mode but which are legal in seq mode).  In that event, the use count would be reset to 0 but because the seq script was still compiled it would never be bumped during the sequential recovery runs, which means that the compiler would not compile it again for parallel mode since we would assume that it is never invoked (use count is zero, after all).

Comment 51

[Niko Matsakis [:nmatsakis]]

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

Try run: https://tbpl.mozilla.org/?tree=Try&rev=2d46e531c206

Comment 52

[Ryan VanderMeulen [:RyanVM]]

Backed out for causing frequent B2G mochitest crashes (as shown in comment 51's Try push too).
https://hg.mozilla.org/integration/mozilla-inbound/rev/5e2536a86e7f

Comment 53

[Niko Matsakis [:nmatsakis]]

Attachment: NULL out the lock field and check it in the destructor.

A careful read of the vm/ForkJoin code revealed that this destructor is insufficiently defensive.  I am not sure if this is related to the B2G mochitest failures but it can't hurt.

Comment 54

[Niko Matsakis [:nmatsakis]]

Attachment: Adjust ifdef strategy

The code as written had very fine-grained ifdefs.  Also, we included the forkjoin code even when ion is disabled, although it has little use then.  This version makes it easier to see what happens when either ion/threadsafe is not compiled in.

Comment 55

[Niko Matsakis [:nmatsakis]]

I can't say for certain what was causing those B2G mochitest failures.  I think it is possible that the case is the failure to initialize to NULL found in the first patch.

After applying attachment 725820 [details] [diff] [review], I ran a test run and observed no unexplained failures (in some cases I manually annotated with bugs that documented similar errors):

https://tbpl.mozilla.org/?tree=Try&rev=8388974976f4

After additionally applying attachment 725821 [details] [diff] [review], I ran a full try run including manual reruns of B2G mochitests and various other potentially worrisome tests.  Again I don't see any unexplained failures (in those cases where the automated search failed to uncover a match, I added manual annotations):

https://tbpl.mozilla.org/?tree=Try&rev=1cc629871e76

Comment 56

[Niko Matsakis [:nmatsakis]]

Comment on attachment 725820 [details] [diff] [review]
NULL out the lock field and check it in the destructor.

Moved to bug 852518.

Comment 57

[Niko Matsakis [:nmatsakis]]

Comment on attachment 725821 [details] [diff] [review]
Adjust ifdef strategy

Moved to bug 852518.

Comment 58

[Niko Matsakis [:nmatsakis]]

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

Comment 59

[Niko Matsakis [:nmatsakis]]

Try run: https://tbpl.mozilla.org/?tree=Try&rev=f17d111a6e0c

Comment 60

[Ed Morley [:emorley]]

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