Last Comment Bug 711304 - Implement a sequential version of RiverTrail's ParallelArray in SpiderMonkey
: Implement a sequential version of RiverTrail's ParallelArray in SpiderMonkey
Status: RESOLVED FIXED
:
Product: Core
Classification: Components
Component: JavaScript Engine (show other bugs)
: Other Branch
: All All
: -- normal (vote)
: ---
Assigned To: general
:
:
Mentors:
Depends on: 743480
Blocks:
  Show dependency treegraph
 
Reported: 2011-12-15 17:44 PST by Stephan Herhut [:masterofhats]
Modified: 2012-05-16 14:27 PDT (History)
14 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
proposed sequential implementation (41.90 KB, patch)
2011-12-15 17:44 PST, Stephan Herhut [:masterofhats]
no flags Details | Diff | Splinter Review
patch addressing jorendorff's suggestions (46.01 KB, patch)
2012-01-16 17:38 PST, Stephan Herhut [:masterofhats]
no flags Details | Diff | Splinter Review
adds the missing enumeration hook (47.26 KB, patch)
2012-01-16 18:00 PST, Stephan Herhut [:masterofhats]
no flags Details | Diff | Splinter Review
addresses review feedback and updates implementation to latest API spec (49.50 KB, patch)
2012-02-10 23:48 PST, Stephan Herhut [:masterofhats]
jorendorff: review+
Details | Diff | Splinter Review
sequential implementation of River Trail (50.02 KB, patch)
2012-03-12 15:32 PDT, Stephan Herhut [:masterofhats]
jorendorff: review+
Details | Diff | Splinter Review

Description Stephan Herhut [:masterofhats] 2011-12-15 17:44:45 PST
Created attachment 582154 [details] [diff] [review]
proposed sequential implementation

As a starting point for an integration of RiverTrail's ParallelArray API (see http://github.com/RiverTrail/RiverTrail/wiki) a sequential C++ implementation is needed.
Comment 1 Dave Herman [:dherman] 2011-12-20 22:39:16 PST
Are we looking at landing publicly visible API here? I've talked a little with Stephan about alternatives that would avoid Yet Another Array Type, but we hadn't come to conclusions.

There are serious issues of how ParallelArray behaves inconsistently based on how it was constructed (e.g., when built from a Uint8Array, map will coerce the kernel function results to a uint8, whereas when built from an Array, map won't coerce the results). IMO we should take seriously the alternative of just having parallel operations on Array, typed arrays, and Canvas.

Dave
Comment 2 David Mandelin [:dmandelin] 2011-12-21 16:35:01 PST
(In reply to Dave Herman [:dherman] from comment #1)
> Are we looking at landing publicly visible API here? 

It is first landing to IonMonkey, so we don't have to worry about that right away.

> I've talked a little with Stephan about alternatives that would avoid Yet Another 
> Array Type, but we hadn't come to conclusions.

It seems that at the least we should have vendor prefixing before landing to m-c.

> There are serious issues of how ParallelArray behaves inconsistently based
> on how it was constructed (e.g., when built from a Uint8Array, map will
> coerce the kernel function results to a uint8, whereas when built from an
> Array, map won't coerce the results). IMO we should take seriously the
> alternative of just having parallel operations on Array, typed arrays, and
> Canvas.

Hmmm, it seems we should have some discussion about this, but the bug is probably the wrong place. Maybe one of the JS engine mailing lists? It also seems like user input would be really helpful.
Comment 3 Stephan Herhut [:masterofhats] 2011-12-22 11:51:43 PST
(In reply to Dave Herman [:dherman] from comment #1)
> Are we looking at landing publicly visible API here? I've talked a little
> with Stephan about alternatives that would avoid Yet Another Array Type, but
> we hadn't come to conclusions.

This patch is not intended to nail down the final API but rather as a basis of compiler work. Even if we change the programmer facing parts later, we do not expect this to have a huge impact on the actual vectorizing compiler and parallel runtime implementation. At least not in the early stages.

> There are serious issues of how ParallelArray behaves inconsistently based
> on how it was constructed (e.g., when built from a Uint8Array, map will
> coerce the kernel function results to a uint8, whereas when built from an
> Array, map won't coerce the results). 

You argued against implicit coercions the last time we talked and very convincingly so. The proposed implementation, regardless of how the ParallelArray was constructed, always uses standard JS arrays as the underlying storage. For all other implementations, we will remove the implicit coercion of results soon, too. The goal is that the underlying storage of a ParallelArray object is not observable at all from JavaScript. However, we might still choose to use a more efficient implementation internally.

> IMO we should take seriously the
> alternative of just having parallel operations on Array, typed arrays, and
> Canvas.

We should pick up this discussion again. We have argued back and forth within the team and ended up sticking to ParallelArray. Where would be a good place to discuss?

I would propose, though, to have the API discussion whilst working on the compiler implementation at the same time. 

Stephan
Comment 4 Jeff Walden [:Waldo] (remove +bmo to email) 2011-12-22 13:30:12 PST
(In reply to David Mandelin from comment #2)
> > I've talked a little with Stephan about alternatives that would avoid Yet Another 
> > Array Type, but we hadn't come to conclusions.
> 
> It seems that at the least we should have vendor prefixing before landing to
> m-c.

Historically we haven't done this, relying on people using feature-testing to ensure compatibility.  Not saying we *shouldn't* prefix, just noting that we haven't.  (Given that my vague understanding is that the proxies spec changed quite substantially underneath us, it's not clear to me whether this strategy will work well for having a non-prefixed Proxy constructor and all that.  But I might just be woefully under-informed on this point.)
Comment 5 Jason Orendorff [:jorendorff] 2012-01-04 14:48:36 PST
This shouldn't land without thorough tests. The good news:

1. It is very easy to write tests for this kind of new feature, and I'll be happy to answer any questions you have. First, see js/src/jit-test/README; new tests could go in js/src/jit-test/tests/parallelarray/*.js.

2. Once you have tests, any patch that is a pure performance improvement requires few if any extra tests.
Comment 6 Jason Orendorff [:jorendorff] 2012-01-04 15:45:02 PST
This looks like a fun patch! I'll finish reviewing the code this week. Feel free to start writing tests in parallel. Ha ha.

In the meantime, a quick question about ParallelArray: is it meant to be a multidimensional array object at all? I ask because https://github.com/RiverTrail/RiverTrail/wiki/combine drops some hints in that direction, particularly the mysterious .getShape() method in the last example.

I share Dave Herman's API concerns. Even if it is going into Ion branch first, we should #ifdef the whole thing so that it's easy to turn off later (in case, for example, Ion should want to land before RiverTrail is fully ready).
Comment 7 Stephan Herhut [:masterofhats] 2012-01-04 16:13:36 PST
(In reply to Jason Orendorff [:jorendorff] from comment #6)
> This looks like a fun patch! I'll finish reviewing the code this week. Feel
> free to start writing tests in parallel. Ha ha.
 
Thanks for looking into it. I will get to work on the tests to make this a truly task parallel review :-) 

> In the meantime, a quick question about ParallelArray: is it meant to be a
> multidimensional array object at all? I ask because
> https://github.com/RiverTrail/RiverTrail/wiki/combine drops some hints in
> that direction, particularly the mysterious .getShape() method in the last
> example.

The patch implements only the API for 1d ParallelArray objects, which is a true subset of the multidimensional API. One reason is that we have not finalized, yet, how to represent multidimensional indices (another interesting API discussion to have). 

There are other subtle differences between the GitHub implementation and the patch. For instance, the patch uses closures and free variables to pass arguments to kernels whereas so far the GitHub version had the concept of extra arguments. We hope to update the GitHub version to the API used by the patch (for closures, this will happen soon thanks to Debugger.Environment).
 
> I share Dave Herman's API concerns. Even if it is going into Ion branch
> first, we should #ifdef the whole thing so that it's easy to turn off later
> (in case, for example, Ion should want to land before RiverTrail is fully
> ready).

AFAIK, this patch can be disabled by simply not initializing the ParallelArray prototype when setting up SpiderMonkey. It is a very well isolated and localized change. I would prefer having it turned on by default so that problems due to refactoring are caught early.

Also, we should discuss the API concerns. Any suggestions for a venue?
Comment 8 Jason Orendorff [:jorendorff] 2012-01-05 08:53:22 PST
(In reply to Stephan Herhut [:masterofhats] from comment #7)
> AFAIK, this patch can be disabled by simply not initializing the
> ParallelArray prototype when setting up SpiderMonkey. It is a very well
> isolated and localized change. I would prefer having it turned on by default
> so that problems due to refactoring are caught early.

OK, I'm convinced. Turning it off is commenting out a single line of code -- easier than flipping an ifdef in the build system, even...

> Also, we should discuss the API concerns. Any suggestions for a venue?

Great. We can talk on IRC or Skype. Let's wait for dherman to appear.
Comment 9 Jason Orendorff [:jorendorff] 2012-01-12 15:03:25 PST
(First half of the review, covering all the boring parts.)

The files should be called js/src/builtin/ParallelArray.h and .cpp. (The
js/src/js* naming convention is very old and we're moving away from it
now.)

In ion/IonSpewer.cpp:
>-    if (!c1Spewer.init("/tmp/ion.cfg"))
>+    if (!c1Spewer.init("ion.cfg"))
>         return false;
>-    if (!jsonSpewer.init("/tmp/ion.json"))
>+    if (!jsonSpewer.init("ion.json"))
>         return false;

This doesn't belong in this patch. However it's a totally reasonable thing to
fix; feel free to file a separate bug, with or without a patch.

In jsobj.h:
> extern Class ObjectClass;
> extern Class ProxyClass;
> extern Class RegExpClass;
> extern Class SlowArrayClass;
> extern Class StopIterationClass;
> extern Class StringClass;
> extern Class StrictArgumentsObjectClass;
> extern Class WeakMapClass;
>+extern Class ParallelArrayProtoClass;
>+extern Class ParallelArrayClass;
> extern Class WithClass;
> extern Class XMLFilterClass;

Nit: Please keep the list in alphabetical order!

In jsparallelarray.h:
>+#include "jscntxt.h"
>+#include "jsobj.h"
>+
>+namespace js {
>+
>+// this is where the actual or private implementation will go, once there is one
>+
>+}
>+

Please remove these lines for now, since they're not currently needed.

In jsparallelarray.cpp:
>+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-

This file contains Windows-style line endings. Please convert it to Unix
line endings. Also please remove the trailing whitespace at the end of
some lines.

In jsparallelarray.cpp:
>+ * The Original Code is Mozilla SpiderMonkey JavaScript 1.9 code, released
>+ * May 28, 2008.
>+
>+ * The Initial Developer of the Original Code is
>+ *   Mozilla Foundation
>+ * Portions created by the Initial Developer are Copyright (C) 2009
>+ * the Initial Developer. All Rights Reserved.

This doesn't look right. Instead, copy the corresponding parts from the
jsparallelarray.h file, which looks correct to me.

>+#include <string.h>
>+#include "jsapi.h"
>+#include "jscntxt.h"
>+#include "jsfriendapi.h"
>+#include "jsgc.h"
>+#include "jsobj.h"
>+#include "jsgc.h"
>+#include "jsgcmark.h"
>+#include "jsweakmap.h"
>+
>+#include "vm/GlobalObject.h"
>+
>+#include "jsgcinlines.h"
>+#include "jsobjinlines.h"

Include the minimum. In any case you don't need to include jsgc.h twice. ;-)

>+namespace js {
>+
>+// this is where the actual implementation will go, once there is one
>+
>+} /* namespace js */

Remove this.
Comment 10 Jason Orendorff [:jorendorff] 2012-01-12 18:15:15 PST
Further partial review. Most of these early comments are a bunch of
nitpicking-- style issues that are easy to address.

Note that int32 and uint32 have been removed. Use int32_t and uint32_t.
(You don't need to #include anything special; they are defined in
headers included from jsapi.h.)

In jsparallelarray.cpp:
>+static enum {

This is an error in GCC:

jsparallelarray.cpp:69: error: a storage class can only be specified for objects and functions

You can just remove 'static' for now, and give the constants distinctive
names. (Usually constants like these either get a name starting with
JSSLOT_, or they're private enums of a class.)

In ParallelArray_get:
>+    CallArgs args = CallArgsFromVp(argc, vp);
>+    JSObject *thiso;
>+    JSObject *array;
>+    uint32 index;
>+    uint32 length;
>+
>+    bool ok;
>+    thiso = NonGenericMethodGuard(cx, args, ParallelArray_get, &ParallelArrayClass, &ok);

Nit: declare variables as late as possible, in this case:

    CallArgs args = CallArgsFromVp(argc, vp);
    bool ok;
    JSObject *thiso = NonGenericMethodGuard(cx, args, ParallelArray_get, &ParallelArrayClass, &ok);
    ...

    uint32_t index;
    if (!ToUint32(cx, args[0], &index))
        ...

    uint32_t length = uint32_t(thiso->getSlot(FIELD_LENGTH).toInt32());

and so on.

>+    if (!thiso) {
>+        return ok;
>+    }

Nit: If the body of a compound statement is just one line, and the
head is just one line, skip the braces.

However if *any* of the bodies of an if/else-if/else chain is more than
one line, *all* of them get curly braces.

>+    length = uint32(thiso->getSlot(FIELD_LENGTH).toInt32());
...
>+    array = &(thiso->getSlot(FIELD_BUFFER).toObject());

It seems worthwhile to add inline functions for these two common queries.

>+static JSBool
>+ParallelArray_build(JSContext *cx, uint32 length, Value thisv, JSObject *elementalFun, 

Use 'const Value &' to pass a Value.

>+                    JSBool passElement, CallArgs &cArgs)

To avoid confusion with the InvokeArgsGuard in the body of this
function, it might be best to make the last parameter:
    Value *vp

and change the callers to pass:
    &args.rval()

Your call.

In ParallelArray_build:
>+    AutoObjectRooter aor(cx, buffer);

AutoRooters are obsolete, as our GC currently conservatively scans the C
stack. Remove all these.

>+    buffer->ensureDenseArrayInitializedLength(cx, length, 0);

This method is inline, and the definition isn't in any of the headers
you've included. Add this one:
    #include "jsarrayinlines.h"

I'm going to ask around and see if this is the right method to call. It
seems like passing (length, 0) as you did will set a deoptimizing flag
on the array, indicating it's not packed--this is really bad. But
passing (0, length) causes that method to memset the array contents,
which we also do not want. I'll get back to you.

>+    InvokeArgsGuard iArgs;

Nit: Name this 'args' or 'ag', not 'iArgs'. 

>+    for (uint32 cnt = 0; cnt < length; cnt++) {

Nit: Use 'i' instead of 'cnt'.

>+        /* prepare call frame on stack */
>+        if (!iArgs.pushed() && !cx->stack.pushInvokeArgs(cx, 1, &iArgs))
>+            return false;

Please do this setup outside the loop. You don't need to check args.pushed().

(args.setCallee(), however, must be done inside the loop, because each
call to Invoke() overwrites the callee slot.)

>+            iArgs[0] = Int32Value(int32(cnt));

This is incorrect if the array is more than 0x7fffffff elements.

Instead:  args[0].setNumber(i);

>+        }
>+        /* set value of this */
>+        iArgs.thisv() = thisv;

Nit: Add a blank line before this comment (and any such comment, except
at the beginning of a block).

>+        ok = Invoke(cx, iArgs);
>+        if (!ok) {
>+            /* abort */
>+            return ok;
>+        }

Instead, write:
    if (!Invoke(cx, args))
        return false;
and remove the unnecessary local variable 'ok'.

>+    /* create ParallelArray wrapper class */
>+    array = NewBuiltinClassInstance(cx, &ParallelArrayClass);
>+    if (!array) {
>+        return false;
>+    }
>+    array->setSlot(FIELD_LENGTH, Int32Value(int32(length)));
>+    array->setSlot(FIELD_BUFFER, ObjectValue(*buffer));

This code is repeated several times. How about factoring it out into a function?

static JSObject *
NewParallelArray(JSContext *cx, uint32_t length, JSObject *buffer)
{
    ...
}

Then all the code using these FIELD_ constants will be in three short
functions (New, GetLength, GetBuffer) right at the top of the file.
Comment 11 Jason Orendorff [:jorendorff] 2012-01-13 15:05:07 PST
Part 3 of 4.

Nits: Throughout, please remove little comments saying /* abort */.

Also take a look at existing source code and try to use idiomatic
names. 'thiso' is right out!  :)

In ParallelArray_build:
>+                    JSBool passElement, CallArgs &cArgs)

I missed this. Make the passElement parameter plain C++ 'bool', please.

In ParallelArray_construct:
>+    if (args.length() == 1) { /* init using an array value */

Nit: Line break after the curly brace here (and elsewhere).

>+        if (!args[0].isObject()) 
>+            return false;

Need to report an error before returning false.

>+        JSObject *src = &(args[0].toObject());
>+        if (!src) 
>+            return false;

It is impossible for src to be null, so the check can be removed.

>+        Value elem;
>+        for (uint32 cnt = 0; cnt < srcLen; cnt++) {

Move the declaration of elem into the block.

>+            if (src->isDenseArray() && (cnt < src->getDenseArrayInitializedLength())) {
>+                elem = src->getDenseArrayElement(cnt);
>+                if (elem.isMagic(JS_ARRAY_HOLE)) {
>+                    elem.setUndefined();
>+                }
>+            } else if (!(src->isArguments() && src->asArguments()->getElement(cnt, &elem))) {
>+                /* generic case */
>+                if (!src->getElement(cx, src, cnt, &elem)) {
>+                    /* abort */
>+                    return false;
>+                }
>+            }

The logic here is too clever. How about this:

    if (src->isDenseArray() && ...) {
        elem = ...
        ...
    } else if (src->isArguments()) {
        if (!src->asArguments()->getElement(i, &elem))
            return false;
    } else {
        /* generic case */
        if (!src->getElement(cx, src, i, &elem))
            return false;
    }

Three cases--one, two, three.

The code as written would misbehave if ArgumentsObject::getElement were
to fail and return false -- though maybe that can't happen currently?

(In SpiderMonkey, errors are stateful; see JSContext::exception. Because
of this, you are not supposed to continue doing things after a function
returns false to you; you should either return false, propagating the
error, or handle the error before proceeding.)

Actually I don't think it's worth having a special case for arguments
here. The generic code would work on arguments and arrays too. But, as
you like.

>+        return true;
>+    } else {                  /* init using length and function */

Style nit: In cases like this where control can't flow off the end of
the if-block, don't use else. That is, instead of:

    if (E0) {
       S0;
       return E1;
    } else {
       S1;
       S2;
    }

write:

    if (E0) {
        S0;
        return E1;
    }
    S1;
    S2;

even if neither case is an error case! (Another quirky house rule,
dating back to Netscape days I think.)

>+        JSObject *elementalFun = js_ValueToCallableObject(cx, &args[1], JSV2F_SEARCH_STACK);
>+        if (!elementalFun) {
>+            JS_ReportError(cx, "ParallelArray expects a function as second argument");
>+            return false;
>+        }

In this case js_ValueToCallableObject has already reported the error for
you, so don't call JS_ReportError. Just return false.

However - everywhere the new code uses JS_ReportError, it should be
using JS_ReportErrorNumber. Add new entries to js/src/js.msg as
needed. Most of them should be TypeErrors.

>+        /* undefined probably is not a good idea, as this then turns into the global object */
>+        return ParallelArray_build(cx, length, UndefinedValue(), elementalFun, JS_FALSE, args);

I think undefined is a fine choice. It doesn't matter much, as the
function won't ordinarily refer to 'this', right?

In ParallelArray_map:
>+    ok = ParallelArray_build(cx, length, ObjectValue(*thiso), elementalFun, JS_TRUE, args);
>+
>+    return ok;

Use 'true' instead of 'JS_TRUE'.

Go ahead and just 'return ParallelArray_build(...);' and eliminate the
local variable 'ok'.

ParallelArray_combine seems to be identical to ParallelArray_map except
for a boolean constant. Please common up the code, as you have for scan
and reduce.

>+    /* special case of empty arrays */
>+    if (length == 0) {
>+        args.rval() = (isScan ? ObjectValue(*result) : UndefinedValue());
>+        return true;
>+    }
>+
>+    /* extract first argument, the elemental function */
>+    elementalFun = js_ValueToCallableObject(cx, &args[0], JSV2F_SEARCH_STACK);
>+    if (!elementalFun) {
>+        return false;
>+    }

I think a missing elemental function argument should be detected even if
the array happens to be empty. If you agree, swap the order of these two
chunks of code.

>+    InvokeArgsGuard iArgs;
>+    for (uint32 cnt = 1; cnt < length; cnt++) {
>+        /* prepare call frame on stack */
>+        if (!iArgs.pushed() && !cx->stack.pushInvokeArgs(cx, 2, &iArgs))
>+            return false;

As before, call pushInvokeArgs just once, outside the loop, and don't
check args.push().

>+        /* call */
>+        ok = Invoke(cx, iArgs);
>+
>+        if (!ok) {
>+            /* abort */
>+            return ok;
>+        }

    if (!Invoke(cx, args))
        return false;

In ParallelArray_filter:
>+    if (!args[0].isObject()) {
>+        return false;
>+    }
>+    JSObject &mask = args[0].toObject();
>+
>+    if (!mask.isArray()) 
>+        return false;

Both of these must report an error before returning.

Note that isArray() returns false for typed arrays and for ParallelArray
objects. It only returns true for actual JS arrays. This seems too
restrictive, especially since the rest of the code will work fine
no matter what kind of object args[0] is.

>+    Value elem;
>+    jsid id;
>+    for (uint32 cnt = 0; cnt < length; cnt++) {
>+        if (!IndexToId(cx, cnt, &id))
>+            return false;
>+        if (!JS_LookupPropertyById(cx, &mask, id, &elem)) {
>+            /* abort */
>+            return false;
>+        }

    for (uint32_t i = 0; i < length; i++) {
        Value elem;
        if (mask.getElement(cx, &mask, cnt, &elem))
            return false;

'id' can be removed. As before, move the declaration of 'elem' into the
loop and rename the loop variable to 'i'.

>+    /* grab the scatter vector */
>+    if (!args[0].isObject()) {
>+        return false;
>+    }
>+    JSObject &targets = args[0].toObject();
>+
>+    if (!targets.isArray()) {
>+        return false;
>+    }

Same comment as in ParallelArray_filter.

>+    if (!JS_GetArrayLength(cx, &targets, &scatterLen)) {
>+        return false;
>+    }
>+
>+    if (scatterLen > uint32(thiso->getSlot(FIELD_LENGTH).toInt32())) {
>+        /* abort: to many indices */
>+        return false;
>+    }

"too many"

Also, this needs to report an error.

...But actually... why reject this? Doesn't the rest of the code handle
this case just fine? The only special thing about this case is that
conflicts are certain.

>+    /* next, default value */
>+    Value &defValue = UndefinedValue();

Remove the & here. This is an error in GCC.

>+    /* optional length */
>+    uint32 length;
>+    if (args.length() >= 4) {
>+        if (!ToUint32(cx, args[3], &length))
>+            return false;
>+    } else {
>+        length = scatterLen;
>+    }

The default length should be this ParallelArray's length, not scatterLen, right?

>+    /* iterate over the scatter vector */
>+    Value elem;
>+    jsid id;
>+    uint32 targetIdx;
>+    bool *visited = NULL;
>+    if (!defValue.isUndefined() || conflictFun) {
>+        visited = new bool[length];
>+        /* and next session, we'll learn memset */
>+        for (uint32 cnt = 0; cnt < length; cnt++) {
>+            visited[cnt] = false;
>+        }
>+    }

This can be remembered by initializing the array to all holes. Then you
don't need to allocate and initialize extra storage.

>+    for (uint32 cnt = 0; cnt < scatterLen; cnt++) {
>+        /* read target index */
>+        if (!IndexToId(cx, cnt, &id))
>+            return false;
>+        if (!JS_LookupPropertyById(cx, &targets, id, &elem)) {
>+            /* abort */
>+            return false;
>+        }

Again, use targets.getElement().

>+        if (targetIdx >= length) {
>+            /* abort: index out of bounds */
>+            return false;
>+        }

Report an error.

>+            Invoke(cx, iArgs);

Check the return value and return false if this fails.

>+ParallelArray_forward_method(JSContext *cx, JSObject *thiso, CallArgs &args, PropertyName *property)

Nit: please name the second and last parameters 'obj' and 'name'
respectively.

In ParallelArray_forward_method:
>+    Value buffer = thiso->getSlot(FIELD_BUFFER);
>+    AutoValueRooter toString(cx);
>+
>+    if (!buffer.toObject().getProperty(cx, property, toString.addr())) {
>+        return false;
>+    }
>+
>+    if (!toString.value().toObject().isFunction()) {
>+        return false;
>+    }
>+
>+    /* delegate call to Array.toString with internal buffer as |this| */
>+    InvokeArgsGuard iArgs;
>+    if (!cx->stack.pushInvokeArgs(cx, 0, &iArgs))
>+        return false;
>+
>+    iArgs.calleev() = toString.value();
>+    iArgs.thisv() = buffer;
>+    if (!Invoke(cx, iArgs)) {
>+        return false;
>+    }
>+
>+    args.rval() = iArgs.rval();
>+    return true;

Take a look at the source code of JS_CallFunctionName in jsapi.cpp. I
think you can condense the above to something like this:

    Value fn;
    return js_GetMethod(cx, obj, ATOM_TO_JSID(name), JSGET_NO_METHOD_BARRIER, &fn) &&
           Invoke(cx, ObjectValue(*obj), method, 0, NULL, &args.rval());

The many-argument version of Invoke basically just does all the things
you're doing explicitly here.

>+static JSBool
>+ParallelArray_toString(JSContext *cx, uintN argc, Value *vp)
>+{
>+    CallArgs args = CallArgsFromVp(argc, vp);
>+    JSObject *thiso;
>+    bool ok;
>+
>+    /* make sure we are called on a ParallelArray */
>+    thiso = NonGenericMethodGuard(cx, args, ParallelArray_toString, &ParallelArrayClass, &ok);
>+    if (!thiso) {
>+        return ok;
>+    }
>+
>+    return ParallelArray_forward_method(cx, thiso, args, cx->runtime->atomState.toStringAtom);
>+}
>+
>+static JSBool
>+ParallelArray_toLocaleString(JSContext *cx, uintN argc, Value *vp)
>+{
>+    CallArgs args = CallArgsFromVp(argc, vp);
>+    JSObject *thiso;
>+    bool ok;
>+
>+    /* make sure we are called on a ParallelArray */
>+    thiso = NonGenericMethodGuard(cx, args, ParallelArray_toLocaleString, &ParallelArrayClass, &ok);
>+    if (!thiso) {
>+        return ok;
>+    }
>+
>+    return ParallelArray_forward_method(cx, thiso, args, cx->runtime->atomState.toLocaleStringAtom);
>+}
>+
>+static JSBool
>+ParallelArray_toSource(JSContext *cx, uintN argc, Value *vp)
>+{
>+    CallArgs args = CallArgsFromVp(argc, vp);
>+    JSObject *thiso;
>+    bool ok;
>+
>+    /* make sure we are called on a ParallelArray */
>+    thiso = NonGenericMethodGuard(cx, args, ParallelArray_toSource, &ParallelArrayClass, &ok);
>+    if (!thiso) {
>+        return ok;
>+    }
>+
>+    return ParallelArray_forward_method(cx, thiso, args, cx->runtime->atomState.toSourceAtom);
>+}

Eliminate (even more) redundancy here. Each of these functions only needs one line of code:

    return ParallelArray_forward_method(cx, argc, vp, ParallelArray_toSource,
                                        cx->runtime->atomState.toSourceAtom);

(well maybe that is two lines)

In ParallelArray_length_getter:
>+    if (obj->getClass() != &ParallelArrayClass) {
>+        return false;
>+    }

Don't return false without reporting an error. In this case, use
NonGenericMethodGuard instead of checking obj's class directly.

>+    *vp = obj->getSlot(FIELD_LENGTH);

This is not correct if the length is greater than 0x7fffffff.

Instead:
    vp->setNumber(GetParallelArrayLength(obj));
Comment 12 Jason Orendorff [:jorendorff] 2012-01-16 14:51:13 PST
Comment on attachment 582154 [details] [diff] [review]
proposed sequential implementation

This is a cool idea and it's been a fun patch to review. Here is the last part of my 4-part review. We still need to grab dherman and review the API, and then we should do a second code review with an updated patch I guess. I expect it will go a lot faster--but I need to chat with Waldo about some of these js::ObjectOps functions, and of course tests are required.

The rest of this review involves the js::ObjectOps implementations. A lot
of the implementations look like this:

>+    JS_ReportError(cx, "ParallelArray objects are immutable");
>+
>+    return JS_FALSE;

which should be replaced with a JS_ReportErrorNumber call using a new
js.msg entry.

In ParallelArray_lookupGeneric:
>+    if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom) ||
>+        JSID_IS_ATOM(id, cx->runtime->atomState.protoAtom) ||
>+        IsDenseArrayId(cx, buffer, id)) {
>+        *propp = (JSProperty *) 1; /* TRUE */

Nit: move the curly brace to its own separate line, like this:

    if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom) ||
        JSID_IS_ATOM(id, cx->runtime->atomState.protoAtom) ||
        IsDenseArrayId(cx, buffer, id))
    {
        *propp = ...

This function should copy array_lookupGeneric or
TypedArray::obj_lookupGeneric more closely.

In particular there should definitely be no exception for protoAtom.

For lengthAtom, probably what you've got here is fine, but we need to
figure out what API we want and then I need to talk it over with Waldo.

In ParallelArray_lookupElement:
>+    if (JSObject *proto = obj->getProto())
>+        return proto->lookupElement(cx, index, objp, propp);
>+
>+    *objp = NULL;
>+    *propp = NULL;
>+    return true;

There is similar "delegate to the proto chain" code in several of these
functions. Some are phrased this way, and some are phrased the opposite
way:

In ParallelArray_getGeneric:
>+    JSObject *proto = obj->getProto();
>+    if (!proto) {
>+        vp->setUndefined();
>+        return JS_TRUE;
>+    }
>+
>+    return proto->getGeneric(cx, receiver, id, vp);

I have no preference between the two but it'd be better to be consistent.

In ParallelArray_getGeneric:
>+    if (JSID_IS_ATOM(id, cx->runtime->atomState.protoAtom)) {
>+        vp->setObjectOrNull(obj->getProto());
>+        return JS_TRUE;
>+    }

Please delete this. (The .__proto__ property of ParallelArrays should
still work fine without it, because this code delegates to the proto
chain at the end.)

>+    if (IsDenseArrayId(cx, buffer, id)) {
>+        return buffer->getGeneric(cx, receiver, id, vp);
>+        //return JS_LookupPropertyById(cx, buffer, id, vp);

Remove the commented-out line.

In ParallelArray_getElement:
>+    if (index < uint32(obj->getSlot(FIELD_LENGTH).toInt32())) {
>+        return obj->getSlot(FIELD_BUFFER).toObject().getElement(cx, receiver, index, vp);

Use IsDenseArrayIndex in the first line here, and
.toObject().getDenseArrayElement(index) in the second line.

>+static JSBool
>+ParallelArray_defineGeneric(JSContext *cx, JSObject *obj, jsid id, const Value *value,
>+                            JSPropertyOp getter, StrictPropertyOp setter, uintN attrs)
>+{
>+    if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom) ||
>+        JSID_IS_ATOM(id, cx->runtime->atomState.protoAtom)) {
>+        return JS_TRUE;
>+    }
>+
>+    JS_ReportError(cx, "ParallelArray objects are immutable");
>+    return JS_FALSE;
>+}

This is too lenient. Could you remove the exception for .lengthAtom and
.protoAtom please? Setting or defining any property of a ParallelArray
might as well throw. (Being strict now gives us the ability to lighten
up later.)

>+static JSBool
>+ParallelArray_setProperty(JSContext *cx, JSObject *obj, PropertyName *name, Value *vp, JSBool strict)
>+{
>+    return ParallelArray_setGeneric(cx, obj, ATOM_TO_JSID(name), vp, strict);
>+}
>+static JSBool
>+ParallelArray_setElement(JSContext *cx, JSObject *obj, uint32 index, Value *vp, JSBool strict)

Style nit: Add a blank line between these two functions.

>+
>+
>+static JSBool
>+ParallelArray_setSpecial(JSContext *cx, JSObject *obj, SpecialId sid, Value *vp, JSBool strict)

Micro-nit: There is an extra blank line before this function; please
remove it. (Another quirky house style rule.)

>+static JSBool
>+ParallelArray_getGenericAttributes(JSContext *cx, JSObject *obj, jsid id, uintN *attrsp)
>+{
>+    *attrsp = JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom)
>+        ? JSPROP_PERMANENT : JSPROP_ENUMERATE;
>+    return JS_TRUE;
>+}

When id is 'length', we want
    JSPROP_PERMANENT | JSPROP_READONLY
and when id is an element, we want
    JSPROP_PERMANENT | JSPROP_READONLY | JSPROP_ENUMERATE

>+static JSBool
>+ParallelArray_getElementAttributes(JSContext *cx, JSObject *obj, uint32 index, uintN *attrsp)
>+{
>+    *attrsp = JSPROP_ENUMERATE;
>+    return true;
>+}

    JSPROP_PERMANENT | JSPROP_READONLY | JSPROP_ENUMERATE

>+static JSBool
>+ParallelArray_deleteGeneric(JSContext *cx, JSObject *obj, jsid id, Value *rval, JSBool strict)
>+{
>+    JS_ReportError(cx, "ParallelArray objects are immutable");
>+
>+    return JS_FALSE;
>+}

Since you wrote this, the deleteGeneric hook has been removed.

>+Class js::ParallelArrayProtoClass = {
>+    "ParallelArray",
>+    JSCLASS_HAS_CACHED_PROTO(JSProto_ParallelArray),
[...]
>+Class js::ParallelArrayClass = {
>+    "ParallelArray",
>+    JSCLASS_HAS_RESERVED_SLOTS(FIELD_MAX) |
>+    JSCLASS_HAS_CACHED_PROTO(JSProto_ParallelArray),

I'm having a hard time figuring out what the right thing is here. For
typed arrays, we apparently set the JSCLASS_HAS_CACHED_PROTO(...) flag
only for the proto class ("slowClass" as the source code calls it) and
not for the class of actual typed-array instances ("fastClass") -- but
createTypedArray is magical, so I'm not sure that is necessary or
sufficient for a new type.

I'll ask bhackett or Waldo for help with this part.

In js::ParallelArrayClass:
>+#if 1

Please remove this.

Clearing the review flag. (That means it's your turn, Stephan. Looking good so far.)
Comment 13 Stephan Herhut [:masterofhats] 2012-01-16 17:38:14 PST
Created attachment 589074 [details] [diff] [review]
patch addressing jorendorff's suggestions

Here is an updated patch. I have addressed all comments except for

>>+    if (!JS_GetArrayLength(cx, &targets, &scatterLen)) {
>>+        return false;
>>+    }
>>+
>>+    if (scatterLen > uint32(thiso->getSlot(FIELD_LENGTH).toInt32())) {
>>+        /* abort: to many indices */
>>+        return false;
>>+    }
>
>"too many"
>
>Also, this needs to report an error.
>
>...But actually... why reject this? Doesn't the rest of the code handle
>this case just fine? The only special thing about this case is that
>conflicts are certain.

This handles the case where the scatter vector is longer than the source array. So more values are scattered than are actually available. It could easily be rewritten to use |undefined| in such cases but I would rather throw to warn the programmer that the code is most likely not doing what he wants.

>In ParallelArray_length_getter:
>>+    if (obj->getClass() != &ParallelArrayClass) {
>>+        return false;
>>+    }
>
>Don't return false without reporting an error. In this case, use
>NonGenericMethodGuard instead of checking obj's class directly.

This is a getter, so NonGenericMethodGuard does not fit well. Is there an equivalent for a getter? Can it even happen that this getter is called on a different object? The only thing that came to my mind were prototype chains. Shouldn't I chase down the chain for the ParallelArray object in that case?

I have included some test. Unfortunately, one fails. It seems I have not implemented the interface sufficiently for Object.keys to work. I would want 

Object.keys([1,2,3]) == Object.keys(new ParallelArray([1,2,3]))

but Object.keys returns "" for ParallelArray objects. Help welcome.
Comment 14 Stephan Herhut [:masterofhats] 2012-01-16 18:00:04 PST
Created attachment 589078 [details] [diff] [review]
adds the missing enumeration hook

Thanks to the hint by Mook_as, Object.keys now works as intended. The enumerate hook was previously not implemented. 

Now all tests pass. Remains the question on how to implement the length getter correctly.
Comment 15 Jason Orendorff [:jorendorff] 2012-02-08 12:05:20 PST
Comment on attachment 589078 [details] [diff] [review]
adds the missing enumeration hook

In ParallelArray_build:
>+    JSBool ok = true;

Nit: remove this; it's unused and causes a warning in GCC.

In ParallelArray_filter:
>+        if (js_ValueToBoolean(elem)) {
>+            resBuffer->setDenseArrayElementWithType(cx, pos++, buffer->getDenseArrayElement(i));
>+        }

Nit: Remove the curly braces around this one-line single statement; do the same throughout the file, about 19 places.

In ParallelArray_scatter:
>+        for (uint32_t i = 0; i < length; i++) {
>+            if (resBuffer->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE)) 
>+                resBuffer->setDenseArrayElementWithType(cx, i, defValue);
>+            
>+        }

Nit: Remove the blank line, and in general remove all trailing whitespace at the end of lines.

>+    
>+

Super micro nit: House style never uses two blank lines together; delete one.

In ParallelArray_lookupGeneric:
>+        *propp = (JSProperty *) 1; /* TRUE */
>+        *objp = NULL;

It needs to be *objp = obj; and the test case is:

var desc = Object.getOwnPropertyDescriptor(ParallelArray([9]), "length");

which you can add as a jit-test. You should check that the results are as expected:

  js> Object.getOwnPropertyDescriptor(ParallelArray([9]), "length");
  ({configurable:false, enumerable:false, value:1, writable:false})
  js> Object.getOwnPropertyDescriptor(ParallelArray([9]), "0");
  ({configurable:false, enumerable:true, value:9, writable:false})

>+Class js::ParallelArrayClass = {
>+    "ParallelArray",
>+    JSCLASS_HAS_RESERVED_SLOTS(JSSLOT_PA_MAX) |
>+    JSCLASS_HAS_CACHED_PROTO(JSProto_ParallelArray),

This class also needs the Class::NON_NATIVE flag in order for Object.getOwnPropertyDescriptor to work properly.

This code is good. It's easy to think of more tests that could be added, but we're basically there. We just need to pin dherman down and talk about APIs.
Comment 16 Jason Orendorff [:jorendorff] 2012-02-09 15:58:06 PST
Just got off the phone with Dave. Everything looks great. He'll comment here, tomorrow if possible, and we'll get this landed. We'll turn it off for final releases.
Comment 17 Stephan Herhut [:masterofhats] 2012-02-09 17:53:07 PST
That's great news. I will clean up the patch, add the test case and do a quick check whether it still implements the correct API.
Comment 18 Stephan Herhut [:masterofhats] 2012-02-10 23:48:25 PST
Created attachment 596276 [details] [diff] [review]
addresses review feedback and updates implementation to latest API spec

I have addresses the comments and updated the implementation to reflect the latest API specification. In particular, the following functions have changed:

ParallelArray_filter

filter now expects an elemental function instead of a mask array as first argument. 

ParallelArray_mapOrCombine and ParallelArray_build

map now supports extra arguments that are implicitly indexed and passed through to elemental functions. So for pa.map(f, extra) the function f will be applied to pa[i] and extra[i] for all legal indices i.

The changes should be quick to review.
Comment 19 Dave Herman [:dherman] 2012-02-17 10:54:24 PST
Green light, for my part.

Dave
Comment 20 Jason Orendorff [:jorendorff] 2012-03-12 13:36:46 PDT
Comment on attachment 596276 [details] [diff] [review]
addresses review feedback and updates implementation to latest API spec

OK, let's proceed then.
Comment 21 Stephan Herhut [:masterofhats] 2012-03-12 15:32:58 PDT
Created attachment 605165 [details] [diff] [review]
sequential implementation of River Trail

- updated to latest changes in HG
- changed use of JSObject value to JSObject reference
- added extra test case for scatter method
- added error message for scatter method
Comment 22 David Anderson [:dvander] 2012-03-13 16:24:53 PDT
http://hg.mozilla.org/projects/ionmonkey/rev/41f7074395a9

Note You need to log in before you can comment on or make changes to this bug.