Bug 778559 - Implement ParallelArray API with sequential execution (r=dmandelin)
authorShu-yu Guo <shu@rfrn.org>
Fri, 17 Aug 2012 10:38:59 -0700
changeset 108131 ea2ad8970f3e50e2ef2685ef568316448aae719a
parent 108130 a0cf81efe4aa940dccc4c06b8fbe215ec71771c3
child 108132 8200500fbee52eea0fc23f2e5ffed11dfb0f968b
push id1490
push userakeybl@mozilla.com
push dateMon, 08 Oct 2012 18:29:50 +0000
treeherdermozilla-beta@f335e7dacdc1 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdmandelin
bugs778559
milestone17.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 778559 - Implement ParallelArray API with sequential execution (r=dmandelin)
js/src/Makefile.in
js/src/builtin/ParallelArray-inl.h
js/src/builtin/ParallelArray.cpp
js/src/builtin/ParallelArray.h
js/src/jit-test/tests/parallelarray/comprehension-1.js
js/src/jit-test/tests/parallelarray/comprehension-2.js
js/src/jit-test/tests/parallelarray/comprehension-fn-args.js
js/src/jit-test/tests/parallelarray/comprehension-scale.js
js/src/jit-test/tests/parallelarray/comprehension-throws.js
js/src/jit-test/tests/parallelarray/constructor-1.js
js/src/jit-test/tests/parallelarray/constructor-2.js
js/src/jit-test/tests/parallelarray/constructor-3.js
js/src/jit-test/tests/parallelarray/constructor-4.js
js/src/jit-test/tests/parallelarray/element-1.js
js/src/jit-test/tests/parallelarray/element-2.js
js/src/jit-test/tests/parallelarray/element-3.js
js/src/jit-test/tests/parallelarray/element-4.js
js/src/jit-test/tests/parallelarray/enumerate-1.js
js/src/jit-test/tests/parallelarray/filter-1.js
js/src/jit-test/tests/parallelarray/filter-2.js
js/src/jit-test/tests/parallelarray/filter-3.js
js/src/jit-test/tests/parallelarray/filter-4.js
js/src/jit-test/tests/parallelarray/flatten-1.js
js/src/jit-test/tests/parallelarray/flatten-2.js
js/src/jit-test/tests/parallelarray/flatten-throws.js
js/src/jit-test/tests/parallelarray/get-1.js
js/src/jit-test/tests/parallelarray/get-2.js
js/src/jit-test/tests/parallelarray/get-3.js
js/src/jit-test/tests/parallelarray/get-4.js
js/src/jit-test/tests/parallelarray/get-5.js
js/src/jit-test/tests/parallelarray/get-throws.js
js/src/jit-test/tests/parallelarray/length-1.js
js/src/jit-test/tests/parallelarray/length-2.js
js/src/jit-test/tests/parallelarray/length-3.js
js/src/jit-test/tests/parallelarray/map-1.js
js/src/jit-test/tests/parallelarray/map-2.js
js/src/jit-test/tests/parallelarray/map-3.js
js/src/jit-test/tests/parallelarray/map-fn-args.js
js/src/jit-test/tests/parallelarray/map-throws.js
js/src/jit-test/tests/parallelarray/partition-1.js
js/src/jit-test/tests/parallelarray/partition-throws.js
js/src/jit-test/tests/parallelarray/reduce-1.js
js/src/jit-test/tests/parallelarray/reduce-2.js
js/src/jit-test/tests/parallelarray/reduce-3.js
js/src/jit-test/tests/parallelarray/reduce-fn-args.js
js/src/jit-test/tests/parallelarray/reduce-throws.js
js/src/jit-test/tests/parallelarray/scan-1.js
js/src/jit-test/tests/parallelarray/scan-2.js
js/src/jit-test/tests/parallelarray/scan-3.js
js/src/jit-test/tests/parallelarray/scan-fn-args.js
js/src/jit-test/tests/parallelarray/scan-throws.js
js/src/jit-test/tests/parallelarray/scatter-1.js
js/src/jit-test/tests/parallelarray/scatter-2.js
js/src/jit-test/tests/parallelarray/scatter-3.js
js/src/jit-test/tests/parallelarray/scatter-4.js
js/src/jit-test/tests/parallelarray/scatter-5.js
js/src/jit-test/tests/parallelarray/scatter-6.js
js/src/jit-test/tests/parallelarray/scatter-7.js
js/src/jit-test/tests/parallelarray/scatter-8.js
js/src/jit-test/tests/parallelarray/scatter-9.js
js/src/jit-test/tests/parallelarray/scatter-throws.js
js/src/jit-test/tests/parallelarray/shape-1.js
js/src/jit-test/tests/parallelarray/shape-2.js
js/src/jit-test/tests/parallelarray/surfaces-1.js
js/src/jit-test/tests/parallelarray/surfaces-2.js
js/src/js.msg
js/src/jsapi.cpp
js/src/jsatom.tbl
js/src/jsproto.tbl
--- a/js/src/Makefile.in
+++ b/js/src/Makefile.in
@@ -115,16 +115,17 @@ CPPSRCS		= \
 		Debugger.cpp \
 		GlobalObject.cpp \
 		ObjectImpl.cpp \
 		Stack.cpp \
 		String.cpp \
 		BytecodeCompiler.cpp \
 		BytecodeEmitter.cpp \
 		FoldConstants.cpp \
+		ParallelArray.cpp \
 		ParseMaps.cpp \
 		ParseNode.cpp \
 		Parser.cpp \
 		SemanticAnalysis.cpp \
 		SPSProfiler.cpp \
 		TokenStream.cpp \
 		TreeContext.cpp \
 		TestingFunctions.cpp \
new file mode 100644
--- /dev/null
+++ b/js/src/builtin/ParallelArray-inl.h
@@ -0,0 +1,195 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et tw=99 ft=cpp:
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef ParallelArray_inl_h__
+#define ParallelArray_inl_h__
+
+#include "builtin/ParallelArray.h"
+
+#include "jsobjinlines.h"
+
+namespace js {
+
+inline uint32_t
+ParallelArrayObject::IndexInfo::scalarLengthOfDimensions()
+{
+    JS_ASSERT(isInitialized());
+    return dimensions[0] * partialProducts[0];
+}
+
+inline uint32_t
+ParallelArrayObject::IndexInfo::toScalar()
+{
+    JS_ASSERT(isInitialized());
+    JS_ASSERT(indices.length() <= partialProducts.length());
+
+    if (indices.length() == 0)
+        return 0;
+    if (dimensions.length() == 1)
+        return indices[0];
+
+    uint32_t index = indices[0] * partialProducts[0];
+    for (uint32_t i = 1; i < indices.length(); i++)
+        index += indices[i] * partialProducts[i];
+    return index;
+}
+
+inline bool
+ParallelArrayObject::IndexInfo::fromScalar(uint32_t index)
+{
+    JS_ASSERT(isInitialized());
+    if (!indices.resize(partialProducts.length()))
+        return false;
+
+    if (dimensions.length() == 1) {
+        indices[0] = index;
+        return true;
+    }
+
+    uint32_t prev = index;
+    uint32_t d;
+    for (d = 0; d < partialProducts.length() - 1; d++) {
+        indices[d] = prev / partialProducts[d];
+        prev = prev % partialProducts[d];
+    }
+    indices[d] = prev;
+
+    return true;
+}
+
+inline bool
+ParallelArrayObject::IndexInfo::initialize(uint32_t space)
+{
+    // Initialize using a manually set dimension vector.
+    JS_ASSERT(dimensions.length() > 0);
+    JS_ASSERT(space <= dimensions.length());
+
+    // Compute the partial products of the dimensions.
+    //
+    // NB: partialProducts[i] is the scalar length of dimension i. The scalar
+    // length of the entire space is thus dimensions[0] * partialProducts[0].
+    uint32_t ndims = dimensions.length();
+    if (!partialProducts.resize(ndims))
+        return false;
+    partialProducts[ndims - 1] = 1;
+    for (uint32_t i = ndims - 1; i > 0; i--)
+        partialProducts[i - 1] = dimensions[i] * partialProducts[i];
+
+    // Reserve indices.
+    return indices.reserve(ndims) && indices.resize(space);
+
+}
+
+inline bool
+ParallelArrayObject::IndexInfo::initialize(JSContext *cx, HandleParallelArrayObject source,
+                                           uint32_t space)
+{
+    // Initialize using a dimension vector gotten from a parallel array
+    // source.
+    if (!source->getDimensions(cx, dimensions))
+        return false;
+
+    return initialize(space);
+}
+
+inline bool
+ParallelArrayObject::DenseArrayToIndexVector(JSContext *cx, HandleObject obj,
+                                             IndexVector &indices)
+{
+    uint32_t length = obj->getDenseArrayInitializedLength();
+    if (!indices.resize(length))
+        return false;
+
+    // Read the index vector out of the dense array into an actual Vector for
+    // ease of access. We're guaranteed that the elements of the dense array
+    // are uint32s, so just cast.
+    const Value *src = obj->getDenseArrayElements();
+    const Value *end = src + length;
+    for (uint32_t *dst = indices.begin(); src < end; dst++, src++)
+        *dst = static_cast<uint32_t>(src->toInt32());
+
+    return true;
+}
+
+inline bool
+ParallelArrayObject::is(const Value &v)
+{
+    return v.isObject() && is(&v.toObject());
+}
+
+inline bool
+ParallelArrayObject::is(JSObject *obj)
+{
+    return obj->hasClass(&class_);
+}
+
+inline ParallelArrayObject *
+ParallelArrayObject::as(JSObject *obj)
+{
+    JS_ASSERT(is(obj));
+    return static_cast<ParallelArrayObject *>(obj);
+}
+
+inline JSObject *
+ParallelArrayObject::dimensionArray()
+{
+    JSObject &dimObj = getSlot(SLOT_DIMENSIONS).toObject();
+    JS_ASSERT(dimObj.isDenseArray());
+    return &dimObj;
+}
+
+inline JSObject *
+ParallelArrayObject::buffer()
+{
+    JSObject &buf = getSlot(SLOT_BUFFER).toObject();
+    JS_ASSERT(buf.isDenseArray());
+    return &buf;
+}
+
+inline uint32_t
+ParallelArrayObject::bufferOffset()
+{
+    return static_cast<uint32_t>(getSlot(SLOT_BUFFER_OFFSET).toInt32());
+}
+
+inline uint32_t
+ParallelArrayObject::outermostDimension()
+{
+    return static_cast<uint32_t>(dimensionArray()->getDenseArrayElement(0).toInt32());
+}
+
+inline bool
+ParallelArrayObject::isOneDimensional()
+{
+    return dimensionArray()->getDenseArrayInitializedLength() == 1;
+}
+
+inline bool
+ParallelArrayObject::inOutermostDimensionRange(uint32_t index)
+{
+    return index < outermostDimension();
+}
+
+inline bool
+ParallelArrayObject::inOutermostDimensionRange(JSContext *cx, HandleId id)
+{
+    uint32_t i;
+    return js_IdIsIndex(id, &i) && inOutermostDimensionRange(i);
+}
+
+inline bool
+ParallelArrayObject::getDimensions(JSContext *cx, IndexVector &dims)
+{
+    RootedObject obj(cx, dimensionArray());
+    if (!obj)
+        return false;
+    return DenseArrayToIndexVector(cx, obj, dims);
+}
+
+} // namespace js
+
+#endif // ParallelArray_inl_h__
new file mode 100644
--- /dev/null
+++ b/js/src/builtin/ParallelArray.cpp
@@ -0,0 +1,1937 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et tw=99 ft=cpp:
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "builtin/ParallelArray.h"
+#include "builtin/ParallelArray-inl.h"
+
+#include "jsapi.h"
+#include "jsobj.h"
+#include "jsarray.h"
+#include "jsprf.h"
+
+#include "gc/Marking.h"
+#include "vm/GlobalObject.h"
+#include "vm/Stack.h"
+#include "vm/StringBuffer.h"
+
+#include "jsobjinlines.h"
+#include "jsarrayinlines.h"
+
+using namespace js;
+using namespace js::types;
+
+//
+// Utilities
+//
+
+typedef ParallelArrayObject::IndexVector IndexVector;
+typedef ParallelArrayObject::IndexInfo IndexInfo;
+
+bool
+ParallelArrayObject::IndexInfo::isInitialized()
+{
+    return (dimensions.length() > 0 &&
+            indices.capacity() >= dimensions.length() &&
+            partialProducts.length() == dimensions.length());
+}
+
+static inline JSObject *
+NewDenseArrayWithType(JSContext *cx, uint32_t length, HandleObject source = NullPtr())
+{
+    RootedObject buffer(cx);
+    if (source)
+        buffer = NewDenseCopiedArray(cx, length, source->getDenseArrayElements());
+    else
+        buffer = NewDenseAllocatedArray(cx, length);
+
+    if (!buffer)
+        return NULL;
+
+    if (!source)
+        buffer->ensureDenseArrayInitializedLength(cx, length, 0);
+
+    RootedTypeObject newtype(cx, GetTypeCallerInitObject(cx, JSProto_Array));
+    if (!newtype)
+        return NULL;
+    buffer->setType(newtype);
+
+    return *buffer.address();
+}
+
+// Check if obj is a parallel array, and if so, cast to pa and initialize
+// the IndexInfo accordingly.
+//
+// This function is designed to be used in conjunction with
+// GetElementFromArrayLikeObject; see below.
+static bool
+MaybeGetParallelArrayObjectAndLength(JSContext *cx, HandleObject obj,
+                                     MutableHandle<ParallelArrayObject *> pa,
+                                     IndexInfo *iv, uint32_t *length)
+{
+    if (ParallelArrayObject::is(obj)) {
+        pa.set(ParallelArrayObject::as(obj));
+        if (!pa->isOneDimensional() && !iv->initialize(cx, pa, 1))
+            return false;
+        *length = pa->outermostDimension();
+    } else if (!js_GetLengthProperty(cx, obj, length)) {
+        return false;
+    }
+
+    return true;
+}
+
+// Store the i-th element of the array-like object obj into vp.
+//
+// If pa is not null, then pa is obj casted to a ParallelArrayObject
+// and iv is initialized according to the dimensions of pa. In this case,
+// we get the element using the ParallelArrayObject.
+//
+// Otherwise we do what is done in GetElement in jsarray.cpp.
+static bool
+GetElementFromArrayLikeObject(JSContext *cx, HandleObject obj, HandleParallelArrayObject pa,
+                              IndexInfo &iv, uint32_t i, MutableHandleValue vp)
+{
+    // Are we indexing a parallel array object?
+    if (pa) {
+        // If the array is one dimensional, we can skip using the IndexInfo.
+        if (pa->isOneDimensional() && pa->getElementFromOnlyDimension(cx, i, vp))
+            return true;
+
+        JS_ASSERT(iv.isInitialized());
+        JS_ASSERT(iv.indices.length() == 1);
+        iv.indices[0] = i;
+        if (pa->getParallelArrayElement(cx, iv, vp))
+            return true;
+    }
+
+    if (obj->isDenseArray() && i < obj->getDenseArrayInitializedLength()) {
+        vp.set(obj->getDenseArrayElement(i));
+        if (!vp.isMagic(JS_ARRAY_HOLE))
+            return true;
+    }
+
+    if (obj->isArguments()) {
+        if (obj->asArguments().maybeGetElement(static_cast<uint32_t>(i), vp))
+            return true;
+    }
+
+    bool present;
+    if (!obj->getElementIfPresent(cx, obj, i, vp, &present))
+        return false;
+    if (!present)
+        vp.setUndefined();
+
+    return true;
+}
+
+// Copy an array like object obj into an IndexVector, indices, using
+// ToUint32.
+static inline bool
+ArrayLikeToIndexVector(JSContext *cx, HandleObject obj, IndexVector &indices)
+{
+    IndexInfo iv(cx);
+    RootedParallelArrayObject pa(cx);
+    uint32_t length;
+
+    if (!MaybeGetParallelArrayObjectAndLength(cx, obj, &pa, &iv, &length))
+        return false;
+
+    if (!indices.resize(length))
+        return false;
+
+    RootedValue elem(cx);
+    for (uint32_t i = 0; i < length; i++) {
+        if (!GetElementFromArrayLikeObject(cx, obj, pa, iv, i, &elem) ||
+            !ToUint32(cx, elem, &indices[i]))
+        {
+            return false;
+        }
+    }
+
+    return true;
+}
+
+template <bool impl(JSContext *, CallArgs)>
+static inline
+JSBool NonGenericMethod(JSContext *cx, unsigned argc, Value *vp)
+{
+    CallArgs args = CallArgsFromVp(argc, vp);
+    return CallNonGenericMethod(cx, ParallelArrayObject::is, impl, args);
+}
+
+//
+// Operations Overview
+//
+// The different execution modes implement different versions of a set of
+// operations with the same signatures, detailed below.
+//
+// build
+// -----
+// The comprehension form. Build a parallel array from a dimension vector and
+// using elementalFun, writing the results into buffer. The dimension vector
+// and its partial products are kept in iv. The function elementalFun is passed
+// indices as multiple arguments.
+//
+// bool build(JSContext *cx,
+//            IndexInfo &iv,
+//            HandleObject elementalFun,
+//            HandleObject buffer)
+//
+// map
+// ---
+// Map elementalFun over the elements of the outermost dimension of source,
+// writing the results into buffer. The buffer must be as long as the
+// outermost dimension of the source. The elementalFun is passed
+// (element, index, collection) as arguments, in that order.
+//
+// bool map(JSContext *cx,
+//          HandleParallelArrayObject source,
+//          HandleObject elementalFun,
+//          HandleObject buffer)
+//
+// reduce
+// ------
+// Reduce source in the outermost dimension using elementalFun. If vp is not
+// null, then the final value of the reduction is stored into vp. If buffer is
+// not null, then buffer[i] is the final value of calling reduce on the
+// subarray from [0,i]. The elementalFun is passed 2 values to be
+// reduced. There is no specified order in which the elements of the array are
+// reduced. If elementalFun is not commutative and associative, there is no
+// guarantee that the final value is deterministic.
+//
+// bool reduce(JSContext *cx,
+//             HandleParallelArrayObject source,
+//             HandleObject elementalFun,
+//             HandleObject buffer,
+//             MutableHandleValue vp)
+//
+// scatter
+// -------
+// Reassign elements in source in the outermost dimension according to a
+// scatter vector, targets, writing results into buffer. The targets object
+// should be array-like. The element source[i] is reassigned to the index
+// targets[i]. If multiple elements map to the same target index, the
+// conflictFun is used to resolve the resolution. If nothing maps to i for
+// some i, defaultValue is used for that index. Note that buffer can be longer
+// than the source, in which case all the remaining holes are filled with
+// defaultValue.
+//
+// bool scatter(JSContext *cx,
+//              HandleParallelArrayObject source,
+//              HandleObject targets,
+//              const Value &defaultValue,
+//              HandleObject conflictFun,
+//              HandleObject buffer)
+//
+// filter
+// ------
+// Filter the source in the outermost dimension using an array of truthy
+// values, filters, writing the results into buffer. All elements with index i
+// in outermost dimension such that filters[i] is not truthy are removed.
+//
+// bool filter(JSContext *cx,
+//             HandleParallelArrayObject source,
+//             HandleObject filters,
+//             HandleObject buffer)
+//
+
+ParallelArrayObject::SequentialMode ParallelArrayObject::sequential;
+ParallelArrayObject::ParallelMode ParallelArrayObject::parallel;
+ParallelArrayObject::FallbackMode ParallelArrayObject::fallback;
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::SequentialMode::build(JSContext *cx, IndexInfo &iv,
+                                           HandleObject elementalFun, HandleObject buffer)
+{
+    JS_ASSERT(iv.isInitialized());
+
+    uint32_t length = iv.scalarLengthOfDimensions();
+
+    InvokeArgsGuard args;
+    if (!cx->stack.pushInvokeArgs(cx, iv.dimensions.length(), &args))
+        return ExecutionFailed;
+
+    for (uint32_t i = 0; i < length; i++) {
+        args.setCallee(ObjectValue(*elementalFun));
+        args.setThis(UndefinedValue());
+
+        // Compute and set indices.
+        iv.fromScalar(i);
+        for (size_t j = 0; j < iv.indices.length(); j++)
+            args[j].setNumber(iv.indices[j]);
+
+        if (!Invoke(cx, args))
+            return ExecutionFailed;
+
+        buffer->setDenseArrayElementWithType(cx, i, args.rval());
+    }
+
+    return ExecutionSucceeded;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::SequentialMode::map(JSContext *cx, HandleParallelArrayObject source,
+                                         HandleObject elementalFun, HandleObject buffer)
+{
+    JS_ASSERT(is(source));
+    JS_ASSERT(source->outermostDimension() == buffer->getDenseArrayInitializedLength());
+    JS_ASSERT(buffer->isDenseArray());
+
+    uint32_t length = source->outermostDimension();
+
+    IndexInfo iv(cx);
+    if (!source->isOneDimensional() && !iv.initialize(cx, source, 1))
+        return ExecutionFailed;
+
+    InvokeArgsGuard args;
+    if (!cx->stack.pushInvokeArgs(cx, 3, &args))
+        return ExecutionFailed;
+
+    RootedValue elem(cx);
+    for (uint32_t i = 0; i < length; i++) {
+        args.setCallee(ObjectValue(*elementalFun));
+        args.setThis(UndefinedValue());
+
+        if (source->isOneDimensional()) {
+            if (!source->getElementFromOnlyDimension(cx, i, &elem))
+                return ExecutionFailed;
+        } else {
+            iv.indices[0] = i;
+            if (!source->getParallelArrayElement(cx, iv, &elem))
+                return ExecutionFailed;
+        }
+
+        // The arguments are in eic(h) order.
+        args[0] = elem;
+        args[1].setNumber(i);
+        args[2].setObject(*source);
+
+        if (!Invoke(cx, args))
+            return ExecutionFailed;
+
+        buffer->setDenseArrayElementWithType(cx, i, args.rval());
+    }
+
+    return ExecutionSucceeded;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::SequentialMode::reduce(JSContext *cx, HandleParallelArrayObject source,
+                                            HandleObject elementalFun, HandleObject buffer,
+                                            MutableHandleValue vp)
+{
+    JS_ASSERT(is(source));
+    JS_ASSERT_IF(buffer, buffer->isDenseArray());
+    JS_ASSERT_IF(buffer, buffer->getDenseArrayInitializedLength() >= 1);
+
+    uint32_t length = source->outermostDimension();
+
+    // The accumulator: the objet petit a.
+    //
+    // "A VM's accumulator register is Objet petit a: the unattainable object
+    // of desire that sets in motion the symbolic movement of interpretation."
+    //     -- PLT Žižek
+    RootedValue acc(cx);
+    IndexInfo iv(cx);
+
+    if (source->isOneDimensional()) {
+        if (!source->getElementFromOnlyDimension(cx, 0, &acc))
+            return ExecutionFailed;
+    } else {
+        if (!iv.initialize(cx, source, 1))
+            return ExecutionFailed;
+        iv.indices[0] = 0;
+        if (!source->getParallelArrayElement(cx, iv, &acc))
+            return ExecutionFailed;
+    }
+
+    if (buffer)
+        buffer->setDenseArrayElementWithType(cx, 0, acc);
+
+    InvokeArgsGuard args;
+    if (!cx->stack.pushInvokeArgs(cx, 2, &args))
+        return ExecutionFailed;
+
+    RootedValue elem(cx);
+    for (uint32_t i = 1; i < length; i++) {
+        args.setCallee(ObjectValue(*elementalFun));
+        args.setThis(UndefinedValue());
+
+        if (source->isOneDimensional()) {
+            if (!source->getElementFromOnlyDimension(cx, i, &elem))
+                return ExecutionFailed;
+        } else {
+            iv.indices[0] = i;
+            if (!source->getParallelArrayElement(cx, iv, &elem))
+                return ExecutionFailed;
+        }
+
+        // Set the two arguments to the elemental function.
+        args[0] = acc;
+        args[1] = elem;
+
+        if (!Invoke(cx, args))
+            return ExecutionFailed;
+
+        // Update the accumulator.
+        acc = args.rval();
+        if (buffer)
+            buffer->setDenseArrayElementWithType(cx, i, args.rval());
+    }
+
+    vp.set(acc);
+
+    return ExecutionSucceeded;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::SequentialMode::scatter(JSContext *cx, HandleParallelArrayObject source,
+                                             HandleObject targets, const Value &defaultValue,
+                                             HandleObject conflictFun, HandleObject buffer)
+{
+    JS_ASSERT(buffer->isDenseArray());
+
+    uint32_t length = buffer->getDenseArrayInitializedLength();
+
+    IndexInfo iv(cx);
+    if (!source->isOneDimensional() && !iv.initialize(cx, source, 1))
+        return ExecutionFailed;
+
+    // Index vector and parallel array pointer for targets, in case targets is
+    // a ParallelArray object. If not, these are uninitialized.
+    IndexInfo tiv(cx);
+    RootedParallelArrayObject targetsPA(cx);
+
+    // The length of the scatter vector.
+    uint32_t targetsLength;
+
+    if (!MaybeGetParallelArrayObjectAndLength(cx, targets, &targetsPA, &tiv, &targetsLength))
+        return ExecutionFailed;
+
+    // Iterate over the scatter vector.
+    RootedValue elem(cx);
+    RootedValue telem(cx);
+    RootedValue targetElem(cx);
+    for (uint32_t i = 0; i < targetsLength; i++) {
+        uint32_t targetIndex;
+
+        if (!GetElementFromArrayLikeObject(cx, targets, targetsPA, tiv, i, &telem) ||
+            !ToUint32(cx, telem, &targetIndex))
+        {
+            return ExecutionFailed;
+        }
+
+        if (targetIndex >= length) {
+            JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
+                                 JSMSG_PAR_ARRAY_SCATTER_BOUNDS);
+            return ExecutionFailed;
+        }
+
+        if (source->isOneDimensional()) {
+            if (!source->getElementFromOnlyDimension(cx, i, &elem))
+                return ExecutionFailed;
+        } else {
+            iv.indices[0] = i;
+            if (!source->getParallelArrayElement(cx, iv, &elem))
+                return ExecutionFailed;
+        }
+
+        targetElem = buffer->getDenseArrayElement(targetIndex);
+
+        // We initialized the dense buffer with holes. If the target element
+        // in the source array is not a hole, that means we have set it
+        // already and we have a conflict.
+        if (!targetElem.isMagic(JS_ARRAY_HOLE)) {
+            if (conflictFun) {
+                InvokeArgsGuard args;
+                if (!cx->stack.pushInvokeArgs(cx, 2, &args))
+                    return ExecutionFailed;
+
+                args.setCallee(ObjectValue(*conflictFun));
+                args.setThis(UndefinedValue());
+                args[0] = elem;
+                args[1] = targetElem;
+
+                if (!Invoke(cx, args))
+                    return ExecutionFailed;
+
+                elem = args.rval();
+            } else {
+                JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL,
+                                     JSMSG_PAR_ARRAY_SCATTER_CONFLICT);
+                return ExecutionFailed;
+            }
+        }
+
+        buffer->setDenseArrayElementWithType(cx, targetIndex, elem);
+    }
+
+    // Fill holes.
+    for (uint32_t i = 0; i < length; i++) {
+        if (buffer->getDenseArrayElement(i).isMagic(JS_ARRAY_HOLE))
+            buffer->setDenseArrayElementWithType(cx, i, defaultValue);
+    }
+
+    return ExecutionSucceeded;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::SequentialMode::filter(JSContext *cx, HandleParallelArrayObject source,
+                                            HandleObject filters, HandleObject buffer)
+{
+    JS_ASSERT(buffer->isDenseArray());
+
+    IndexInfo iv(cx);
+    if (!source->isOneDimensional() && !iv.initialize(cx, source, 1))
+        return ExecutionFailed;
+
+    // Index vector and parallel array pointer for filters, in case filters is
+    // a ParallelArray object. If not, these are uninitialized.
+    IndexInfo fiv(cx);
+    RootedParallelArrayObject filtersPA(cx);
+
+    // The length of the filter array.
+    uint32_t filtersLength;
+
+    if (!MaybeGetParallelArrayObjectAndLength(cx, filters, &filtersPA, &fiv, &filtersLength))
+        return ExecutionFailed;
+
+    RootedValue elem(cx);
+    RootedValue felem(cx);
+    for (uint32_t i = 0, pos = 0; i < filtersLength; i++) {
+        if (!GetElementFromArrayLikeObject(cx, filters, filtersPA, fiv, i, &felem))
+            return ExecutionFailed;
+
+        // Skip if the filter element isn't truthy.
+        if (!ToBoolean(felem))
+            continue;
+
+        if (source->isOneDimensional()) {
+            if (!source->getElementFromOnlyDimension(cx, i, &elem))
+                return ExecutionFailed;
+        } else {
+            iv.indices[0] = i;
+            if (!source->getParallelArrayElement(cx, iv, &elem))
+                return ExecutionFailed;
+        }
+
+        // Set the element on the buffer. If we couldn't stay dense, fail.
+        JSObject::EnsureDenseResult result = JSObject::ED_SPARSE;
+        result = buffer->ensureDenseArrayElements(cx, pos, 1);
+        if (result != JSObject::ED_OK)
+            return ExecutionFailed;
+        if (i >= buffer->getArrayLength())
+            buffer->setDenseArrayLength(pos + 1);
+        buffer->setDenseArrayElementWithType(cx, pos, elem);
+
+        // We didn't filter this element out, so bump the position.
+        pos++;
+    }
+
+    return ExecutionSucceeded;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::ParallelMode::build(JSContext *cx, IndexInfo &iv,
+                                         HandleObject elementalFun, HandleObject buffer)
+{
+    return ExecutionFailed;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::ParallelMode::map(JSContext *cx, HandleParallelArrayObject source,
+                                       HandleObject elementalFun, HandleObject buffer)
+{
+    return ExecutionFailed;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::ParallelMode::reduce(JSContext *cx, HandleParallelArrayObject source,
+                                          HandleObject elementalFun, HandleObject buffer,
+                                          MutableHandleValue vp)
+{
+    return ExecutionFailed;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::ParallelMode::scatter(JSContext *cx, HandleParallelArrayObject source,
+                                           HandleObject targetsObj, const Value &defaultValue,
+                                           HandleObject conflictFun, HandleObject buffer)
+{
+    return ExecutionFailed;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::ParallelMode::filter(JSContext *cx, HandleParallelArrayObject source,
+                                          HandleObject filtersObj, HandleObject buffer)
+{
+    return ExecutionFailed;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::FallbackMode::build(JSContext *cx, IndexInfo &iv,
+                                         HandleObject elementalFun, HandleObject buffer)
+{
+    if (parallel.build(cx, iv, elementalFun, buffer) ||
+        sequential.build(cx, iv, elementalFun, buffer))
+    {
+        return ExecutionSucceeded;
+    }
+    return ExecutionFailed;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::FallbackMode::map(JSContext *cx, HandleParallelArrayObject source,
+                                       HandleObject elementalFun, HandleObject buffer)
+{
+    if (parallel.map(cx, source, elementalFun, buffer) ||
+        sequential.map(cx, source, elementalFun, buffer))
+    {
+        return ExecutionSucceeded;
+    }
+    return ExecutionFailed;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::FallbackMode::reduce(JSContext *cx, HandleParallelArrayObject source,
+                                          HandleObject elementalFun, HandleObject buffer,
+                                          MutableHandleValue vp)
+{
+    if (parallel.reduce(cx, source, elementalFun, buffer, vp) ||
+        sequential.reduce(cx, source, elementalFun, buffer, vp))
+    {
+        return ExecutionSucceeded;
+    }
+    return ExecutionFailed;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::FallbackMode::scatter(JSContext *cx, HandleParallelArrayObject source,
+                                           HandleObject targetsObj, const Value &defaultValue,
+                                           HandleObject conflictFun, HandleObject buffer)
+{
+    if (parallel.scatter(cx, source, targetsObj, defaultValue, conflictFun, buffer) ||
+        sequential.scatter(cx, source, targetsObj, defaultValue, conflictFun, buffer))
+    {
+        return ExecutionSucceeded;
+    }
+    return ExecutionFailed;
+}
+
+ParallelArrayObject::ExecutionStatus
+ParallelArrayObject::FallbackMode::filter(JSContext *cx, HandleParallelArrayObject source,
+                                          HandleObject filtersObj, HandleObject buffer)
+{
+    if (parallel.filter(cx, source, filtersObj, buffer) ||
+        sequential.filter(cx, source, filtersObj, buffer))
+    {
+        return ExecutionSucceeded;
+    }
+    return ExecutionFailed;
+}
+
+#ifdef DEBUG
+
+const char *
+ParallelArrayObject::ExecutionStatusToString(ExecutionStatus ss)
+{
+    switch (ss) {
+      case ExecutionFailed:
+        return "failure";
+      case ExecutionCompiled:
+        return "compilation";
+      case ExecutionSucceeded:
+        return "success";
+    }
+    return "(unknown status)";
+}
+
+bool
+ParallelArrayObject::DebugOptions::init(JSContext *cx, const Value &v)
+{
+    if (!v.isObject())
+        return false;
+
+    RootedObject obj(cx, &v.toObject());
+    RootedId id(cx);
+    RootedValue propv(cx);
+    JSString *propStr;
+    JSBool match = false;
+
+    id = AtomToId(Atomize(cx, "mode", strlen("mode")));
+    if (!obj->getGeneric(cx, id, &propv))
+        return false;
+
+    propStr = ToString(cx, propv);
+    if (!JS_StringEqualsAscii(cx, propStr, "par", &match))
+        return false;
+    if (match) {
+        mode = &parallel;
+    } else {
+        if (!JS_StringEqualsAscii(cx, propStr, "seq", &match))
+            return false;
+        if (match)
+            mode = &sequential;
+        else
+            return false;
+    }
+
+    id = AtomToId(Atomize(cx, "expect", strlen("expect")));
+    if (!obj->getGeneric(cx, id, &propv))
+        return false;
+
+    propStr = ToString(cx, propv);
+    if (!JS_StringEqualsAscii(cx, propStr, "fail", &match))
+        return false;
+    if (match) {
+        expect = ExecutionFailed;
+    } else {
+        if (!JS_StringEqualsAscii(cx, propStr, "bail", &match))
+            return false;
+        if (match) {
+            expect = ExecutionCompiled;
+        } else {
+            if (!JS_StringEqualsAscii(cx, propStr, "success", &match))
+                return false;
+            if (match)
+                expect = ExecutionSucceeded;
+            else
+                return false;
+        }
+    }
+
+    return true;
+}
+
+bool
+ParallelArrayObject::DebugOptions::check(JSContext *cx, ExecutionStatus actual)
+{
+    if (expect != actual) {
+        JS_ReportError(cx, "expected %s for %s execution, got %s",
+                       ExecutionStatusToString(expect),
+                       mode->toString(),
+                       ExecutionStatusToString(actual));
+        return false;
+    }
+
+    return true;
+}
+
+#endif // DEBUG
+
+//
+// ParallelArrayObject
+//
+
+JSFunctionSpec ParallelArrayObject::methods[] = {
+    JS_FN("map",                 NonGenericMethod<map>,            1, 0),
+    JS_FN("reduce",              NonGenericMethod<reduce>,         1, 0),
+    JS_FN("scan",                NonGenericMethod<scan>,           1, 0),
+    JS_FN("scatter",             NonGenericMethod<scatter>,        1, 0),
+    JS_FN("filter",              NonGenericMethod<filter>,         1, 0),
+    JS_FN("flatten",             NonGenericMethod<flatten>,        0, 0),
+    JS_FN("partition",           NonGenericMethod<partition>,      1, 0),
+    JS_FN("get",                 NonGenericMethod<get>,            1, 0),
+    JS_FN(js_toString_str,       NonGenericMethod<toString>,       0, 0),
+    JS_FN(js_toLocaleString_str, NonGenericMethod<toLocaleString>, 0, 0),
+    JS_FS_END
+};
+
+Class ParallelArrayObject::protoClass = {
+    "ParallelArray",
+    JSCLASS_HAS_CACHED_PROTO(JSProto_ParallelArray),
+    JS_PropertyStub,         // addProperty
+    JS_PropertyStub,         // delProperty
+    JS_PropertyStub,         // getProperty
+    JS_StrictPropertyStub,   // setProperty
+    JS_EnumerateStub,
+    JS_ResolveStub,
+    JS_ConvertStub
+};
+
+Class ParallelArrayObject::class_ = {
+    "ParallelArray",
+    Class::NON_NATIVE |
+    JSCLASS_HAS_RESERVED_SLOTS(RESERVED_SLOTS) |
+    JSCLASS_HAS_CACHED_PROTO(JSProto_ParallelArray),
+    JS_PropertyStub,         // addProperty
+    JS_PropertyStub,         // delProperty
+    JS_PropertyStub,         // getProperty
+    JS_StrictPropertyStub,   // setProperty
+    JS_EnumerateStub,
+    JS_ResolveStub,
+    JS_ConvertStub,
+    NULL,                    // finalize
+    NULL,                    // checkAccess
+    NULL,                    // call
+    NULL,                    // construct
+    NULL,                    // hasInstance
+    mark,                    // trace
+    JS_NULL_CLASS_EXT,
+    {
+        lookupGeneric,
+        lookupProperty,
+        lookupElement,
+        lookupSpecial,
+        defineGeneric,
+        defineProperty,
+        defineElement,
+        defineSpecial,
+        getGeneric,
+        getProperty,
+        getElement,
+        NULL,                // getElementIfPresent
+        getSpecial,
+        setGeneric,
+        setProperty,
+        setElement,
+        setSpecial,
+        getGenericAttributes,
+        getPropertyAttributes,
+        getElementAttributes,
+        getSpecialAttributes,
+        setGenericAttributes,
+        setPropertyAttributes,
+        setElementAttributes,
+        setSpecialAttributes,
+        deleteProperty,
+        deleteElement,
+        deleteSpecial,
+        enumerate,
+        NULL,                // typeof
+        NULL,                // thisObject
+        NULL,                // clear
+    }
+};
+
+JSObject *
+ParallelArrayObject::initClass(JSContext *cx, JSObject *obj)
+{
+    JS_ASSERT(obj->isNative());
+
+    Rooted<GlobalObject *> global(cx, &obj->asGlobal());
+
+    RootedObject proto(cx, global->createBlankPrototype(cx, &protoClass));
+    if (!proto)
+        return NULL;
+
+    JSProtoKey key = JSProto_ParallelArray;
+    JSAtom *atom = CLASS_NAME(cx, ParallelArray);
+    RootedFunction ctor(cx, global->createConstructor(cx, construct, atom, 0));
+    if (!ctor ||
+        !LinkConstructorAndPrototype(cx, ctor, proto) ||
+        !DefinePropertiesAndBrand(cx, proto, NULL, methods) ||
+        !DefineConstructorAndPrototype(cx, global, key, ctor, proto))
+    {
+        return NULL;
+    }
+
+    // Define the length and shape properties.
+    RootedId lengthId(cx, AtomToId(cx->runtime->atomState.lengthAtom));
+    RootedId shapeId(cx, AtomToId(cx->runtime->atomState.shapeAtom));
+    unsigned flags = JSPROP_PERMANENT | JSPROP_READONLY | JSPROP_SHARED | JSPROP_GETTER;
+
+    JSObject *scriptedLength = js_NewFunction(cx, NULL, NonGenericMethod<lengthGetter>,
+                                              0, 0, global, NULL);
+    JSObject *scriptedShape = js_NewFunction(cx, NULL, NonGenericMethod<dimensionsGetter>,
+                                             0, 0, global, NULL);
+
+    RootedValue value(cx, UndefinedValue());
+    if (!scriptedLength || !scriptedShape ||
+        !DefineNativeProperty(cx, proto, lengthId, value,
+                              JS_DATA_TO_FUNC_PTR(PropertyOp, scriptedLength), NULL,
+                              flags, 0, 0) ||
+        !DefineNativeProperty(cx, proto, shapeId, value,
+                              JS_DATA_TO_FUNC_PTR(PropertyOp, scriptedShape), NULL,
+                              flags, 0, 0))
+    {
+        return NULL;
+    }
+
+    return proto;
+}
+
+bool
+ParallelArrayObject::getElementFromOnlyDimension(JSContext *cx, uint32_t index, MutableHandleValue vp)
+{
+    JS_ASSERT(isOneDimensional());
+
+    uint32_t base = bufferOffset();
+    uint32_t end = base + outermostDimension();
+
+    if (base + index >= end)
+        vp.setUndefined();
+    else
+        vp.set(buffer()->getDenseArrayElement(base + index));
+
+    return true;
+}
+
+bool
+ParallelArrayObject::getParallelArrayElement(JSContext *cx, IndexInfo &iv, MutableHandleValue vp)
+{
+    JS_ASSERT(iv.isInitialized());
+
+    // How many indices we have determine what dimension we are indexing. For
+    // example, if we have 2 indices [n,m], we are indexing something on the
+    // 2nd dimension.
+    uint32_t d = iv.indices.length();
+    uint32_t ndims = iv.dimensions.length();
+    JS_ASSERT(d <= ndims);
+
+    uint32_t base = bufferOffset();
+    uint32_t end = base + iv.scalarLengthOfDimensions();
+
+    // If we are provided an index vector with every dimension specified, we
+    // are indexing a leaf. Leaves are always value, so just return them.
+    if (d == ndims) {
+        uint32_t index = base + iv.toScalar();
+        if (index >= end)
+            vp.setUndefined();
+        else
+            vp.set(buffer()->getDenseArrayElement(index));
+        return true;
+    }
+
+    // If we aren't indexing a leaf value, we should return a new
+    // ParallelArray of lesser dimensionality. Here we create a new 'view' on
+    // the underlying buffer, though whether a ParallelArray is a view or a
+    // copy is not observable by the user.
+    uint32_t rowLength = iv.partialProducts[d - 1];
+    uint32_t offset = base + iv.toScalar();
+    if (offset + rowLength > end) {
+        vp.setUndefined();
+        return true;
+    }
+
+    RootedObject buf(cx, buffer());
+    IndexVector newDims(cx);
+    return (newDims.append(iv.dimensions.begin() + d, iv.dimensions.end()) &&
+            create(cx, buf, offset, newDims, vp));
+}
+
+bool
+ParallelArrayObject::getParallelArrayElement(JSContext *cx, uint32_t index, MutableHandleValue vp)
+{
+    IndexInfo iv(cx);
+    // Manually initialize to avoid re-rooting 'this', as this code could be
+    // called from inside a loop.
+    if (!getDimensions(cx, iv.dimensions) || !iv.initialize(1))
+        return false;
+    iv.indices[0] = index;
+    return getParallelArrayElement(cx, iv, vp);
+}
+
+bool
+ParallelArrayObject::create(JSContext *cx, MutableHandleValue vp)
+{
+    IndexVector dims(cx);
+    if (!dims.append(0))
+        return false;
+    return create(cx, NullPtr(), 0, dims, vp);
+}
+
+bool
+ParallelArrayObject::create(JSContext *cx, HandleObject buffer, MutableHandleValue vp)
+{
+    IndexVector dims(cx);
+    if (!dims.append(buffer->getArrayLength()))
+        return false;
+    return create(cx, buffer, 0, dims, vp);
+}
+
+bool
+ParallelArrayObject::create(JSContext *cx, HandleObject buffer, uint32_t offset,
+                            const IndexVector &dims, MutableHandleValue vp)
+{
+    JS_ASSERT_IF(buffer, buffer->isDenseArray());
+
+    RootedObject result(cx, NewBuiltinClassInstance(cx, &class_));
+    if (!result)
+        return false;
+
+    // Propagate element types.
+    if (buffer && cx->typeInferenceEnabled()) {
+        AutoEnterTypeInference enter(cx);
+        TypeSet *bufferTypes = buffer->getType(cx)->getProperty(cx, JSID_VOID, false);
+        TypeSet *resultTypes = result->getType(cx)->getProperty(cx, JSID_VOID, true);
+        bufferTypes->addSubset(cx, resultTypes);
+    }
+
+    // Store the dimension vector into a dense array for better GC / layout.
+    RootedObject dimArray(cx, NewDenseArrayWithType(cx, dims.length()));
+    if (!dimArray)
+        return false;
+
+    for (uint32_t i = 0; i < dims.length(); i++)
+        dimArray->setDenseArrayElementWithType(cx, i, Int32Value(static_cast<int32_t>(dims[i])));
+
+    result->setSlot(SLOT_DIMENSIONS, ObjectValue(*dimArray));
+
+    // Store the buffer and offset.
+    if (buffer) {
+        result->setSlot(SLOT_BUFFER, ObjectValue(*buffer));
+        result->setSlot(SLOT_BUFFER_OFFSET, Int32Value(static_cast<int32_t>(offset)));
+    } else {
+        result->setSlot(SLOT_BUFFER, UndefinedValue());
+        result->setSlot(SLOT_BUFFER_OFFSET, Int32Value(0));
+    }
+
+    // This is usually args.rval() from build or construct.
+    vp.setObject(*result);
+
+    return true;
+}
+
+JSBool
+ParallelArrayObject::construct(JSContext *cx, unsigned argc, Value *vp)
+{
+    CallArgs args = CallArgsFromVp(argc, vp);
+
+    // Trivial case: create an empty ParallelArray object.
+    if (args.length() < 1)
+        return create(cx, args.rval());
+
+    // First case: initialize using an array value.
+    if (args.length() == 1) {
+        if (!args[0].isObject()) {
+            JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_BAD_ARG, "");
+            return false;
+        }
+
+        RootedObject source(cx, &(args[0].toObject()));
+
+        // When using an array value we can only make one dimensional arrays.
+        IndexVector dims(cx);
+        uint32_t length;
+        if (!dims.resize(1) || !js_GetLengthProperty(cx, source, &length))
+            return false;
+        dims[0] = length;
+
+        RootedObject buffer(cx);
+
+        // If the source is already a dense array, just copy it over
+        // wholesale. Else copy it pointwise.
+        if (source->isDenseArray()) {
+            buffer = NewDenseArrayWithType(cx, length, source);
+            if (!buffer)
+                return false;
+        } else {
+            buffer = NewDenseArrayWithType(cx, length);
+            if (!buffer)
+                return false;
+
+            RootedValue elem(cx);
+            for (uint32_t i = 0; i < length; i++) {
+                if (!source->getElement(cx, i, &elem))
+                    return false;
+                buffer->setDenseArrayElementWithType(cx, i, elem);
+            }
+        }
+
+        return create(cx, buffer, 0, dims, args.rval());
+    }
+
+    // Second case: initialize using a length/dimensions vector and kernel.
+    //
+    // If the length is an integer, we build a 1-dimensional parallel
+    // array using the kernel.
+    //
+    // If the length is an array-like object of sizes, the i-th value in the
+    // dimension array is the size of the i-th dimension.
+    IndexInfo iv(cx);
+    if (args[0].isObject()) {
+        RootedObject dimObj(cx, &(args[0].toObject()));
+        if (!ArrayLikeToIndexVector(cx, dimObj, iv.dimensions))
+            return false;
+    } else {
+        if (!iv.dimensions.resize(1) || !ToUint32(cx, args[0], &iv.dimensions[0]))
+            return false;
+    }
+    if (!iv.initialize(0))
+        return false;
+
+    // Extract second argument, the elemental function.
+    RootedObject elementalFun(cx, ValueToCallable(cx, &args[1]));
+    if (!elementalFun)
+        return false;
+
+    // How long the flattened array will be.
+    uint32_t length = iv.scalarLengthOfDimensions();
+
+    // Create backing store.
+    RootedObject buffer(cx, NewDenseArrayWithType(cx, length));
+    if (!buffer)
+        return false;
+
+#ifdef DEBUG
+    if (args.length() > 1) {
+        DebugOptions options;
+        if (options.init(cx, args[1])) {
+            if (!options.check(cx, options.mode->build(cx, iv, elementalFun, buffer)))
+                return false;
+            return create(cx, buffer, 0, iv.dimensions, args.rval());
+        }
+    }
+#endif
+
+    if (fallback.build(cx, iv, elementalFun, buffer) != ExecutionSucceeded)
+        return false;
+
+    return create(cx, buffer, 0, iv.dimensions, args.rval());
+}
+
+bool
+ParallelArrayObject::map(JSContext *cx, CallArgs args)
+{
+    if (args.length() < 1) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_MORE_ARGS_NEEDED,
+                             "ParallelArray.prototype.map", "0", "s");
+        return false;
+    }
+
+    RootedParallelArrayObject obj(cx, as(&args.thisv().toObject()));
+
+    uint32_t outer = obj->outermostDimension();
+    RootedObject buffer(cx, NewDenseArrayWithType(cx, outer));
+    if (!buffer)
+        return false;
+
+    RootedObject elementalFun(cx, ValueToCallable(cx, &args[0]));
+    if (!elementalFun)
+        return false;
+
+#ifdef DEBUG
+    if (args.length() > 1) {
+        DebugOptions options;
+        if (options.init(cx, args[1])) {
+            if (!options.check(cx, options.mode->map(cx, obj, elementalFun, buffer)))
+                return false;
+            return create(cx, buffer, args.rval());
+        }
+    }
+#endif
+
+    if (fallback.map(cx, obj, elementalFun, buffer) != ExecutionSucceeded)
+        return false;
+
+    return create(cx, buffer, args.rval());
+}
+
+bool
+ParallelArrayObject::reduce(JSContext *cx, CallArgs args)
+{
+    if (args.length() < 1) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_MORE_ARGS_NEEDED,
+                             "ParallelArray.prototype.reduce", "0", "s");
+        return false;
+    }
+
+    RootedParallelArrayObject obj(cx, as(&args.thisv().toObject()));
+    uint32_t outer = obj->outermostDimension();
+
+    // Throw if the array is empty.
+    if (outer == 0) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_REDUCE_EMPTY);
+        return false;
+    }
+
+    RootedObject elementalFun(cx, ValueToCallable(cx, &args[0]));
+    if (!elementalFun)
+        return false;
+
+#ifdef DEBUG
+    if (args.length() > 1) {
+        DebugOptions options;
+        if (options.init(cx, args[1])) {
+            return options.check(cx, options.mode->reduce(cx, obj, elementalFun, NullPtr(),
+                                                          args.rval()));
+        }
+    }
+#endif
+
+    // Call reduce with a null destination buffer to not store intermediates.
+    return fallback.reduce(cx, obj, elementalFun, NullPtr(), args.rval()) == ExecutionSucceeded;
+}
+
+bool
+ParallelArrayObject::scan(JSContext *cx, CallArgs args)
+{
+    if (args.length() < 1) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_MORE_ARGS_NEEDED,
+                             "ParallelArray.prototype.scan", "0", "s");
+        return false;
+    }
+
+    RootedParallelArrayObject obj(cx, as(&args.thisv().toObject()));
+
+    uint32_t outer = obj->outermostDimension();
+
+    // Throw if the array is empty.
+    if (outer == 0) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_REDUCE_EMPTY);
+        return false;
+    }
+
+    RootedObject buffer(cx, NewDenseArrayWithType(cx, outer));
+    if (!buffer)
+        return false;
+
+    RootedObject elementalFun(cx, ValueToCallable(cx, &args[0]));
+    if (!elementalFun)
+        return false;
+
+    // Call reduce with a dummy out value to be discarded and a buffer to
+    // store intermediates.
+    RootedValue dummy(cx);
+
+#ifdef DEBUG
+    if (args.length() > 1) {
+        DebugOptions options;
+        if (options.init(cx, args[1])) {
+            if (!options.check(cx, options.mode->reduce(cx, obj, elementalFun, buffer, &dummy)))
+                return false;
+            return create(cx, buffer, args.rval());
+        }
+    }
+#endif
+
+    if (fallback.reduce(cx, obj, elementalFun, buffer, &dummy) != ExecutionSucceeded)
+        return false;
+
+    return create(cx, buffer, args.rval());
+}
+
+bool
+ParallelArrayObject::scatter(JSContext *cx, CallArgs args)
+{
+    if (args.length() < 1) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_MORE_ARGS_NEEDED,
+                             "ParallelArray.prototype.scatter", "0", "s");
+        return false;
+    }
+
+    if (!args[0].isObject()) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_BAD_ARG,
+                             ".prototype.scatter");
+        return false;
+    }
+
+    RootedParallelArrayObject obj(cx, as(&args.thisv().toObject()));
+    uint32_t outer = obj->outermostDimension();
+
+    // Get the scatter vector.
+    RootedObject targets(cx, &args[0].toObject());
+    uint32_t targetsLength;
+    if (!js_GetLengthProperty(cx, targets, &targetsLength))
+        return false;
+
+    // Don't iterate more than the length of the source array.
+    if (targetsLength > outer)
+        targetsLength = outer;
+
+    // The default value is optional and defaults to undefined.
+    Value defaultValue;
+    if (args.length() >= 2)
+        defaultValue = args[1];
+    else
+        defaultValue.setUndefined();
+
+    // The conflict function is optional.
+    RootedObject conflictFun(cx);
+    if (args.length() >= 3 && !args[2].isUndefined()) {
+        conflictFun = ValueToCallable(cx, &args[2]);
+        if (!conflictFun)
+            return false;
+    }
+
+    // The length of the result array is optional and defaults to the length
+    // of the source array.
+    uint32_t resultLength;
+    if (args.length() >= 4) {
+        if (!ToUint32(cx, args[3], &resultLength))
+            return false;
+    } else {
+        resultLength = outer;
+    }
+
+    // Create a destination buffer. Fail if we can't maintain denseness.
+    RootedObject buffer(cx, NewDenseArrayWithType(cx, resultLength));
+    if (!buffer)
+        return false;
+
+#ifdef DEBUG
+    if (args.length() > 1) {
+        DebugOptions options;
+        if (options.init(cx, args[1])) {
+            if (!options.check(cx, options.mode->scatter(cx, obj, targets, defaultValue,
+                                                         conflictFun, buffer)))
+            {
+                return false;
+            }
+            return create(cx, buffer, args.rval());
+        }
+    }
+#endif
+
+    if (fallback.scatter(cx, obj, targets, defaultValue,
+                         conflictFun, buffer) != ExecutionSucceeded)
+    {
+        return false;
+    }
+
+    return create(cx, buffer, args.rval());
+}
+
+bool
+ParallelArrayObject::filter(JSContext *cx, CallArgs args)
+{
+    if (args.length() < 1) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_MORE_ARGS_NEEDED,
+                             "ParallelArray.prototype.filter", "0", "s");
+        return false;
+    }
+
+    if (!args[0].isObject()) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_BAD_ARG,
+                             ".prototype.filter");
+        return false;
+    }
+
+    RootedParallelArrayObject obj(cx, as(&args.thisv().toObject()));
+
+    // Get the filter vector.
+    RootedObject filters(cx, &args[0].toObject());
+
+    RootedObject buffer(cx, NewDenseArrayWithType(cx, 0));
+    if (!buffer)
+        return false;
+
+#ifdef DEBUG
+    if (args.length() > 1) {
+        DebugOptions options;
+        if (options.init(cx, args[1])) {
+            if (!options.check(cx, options.mode->filter(cx, obj, filters, buffer)))
+                return false;
+            return create(cx, buffer, args.rval());
+        }
+    }
+#endif
+
+    if (fallback.filter(cx, obj, filters, buffer) != ExecutionSucceeded)
+        return false;
+
+    return create(cx, buffer, args.rval());
+}
+
+bool
+ParallelArrayObject::flatten(JSContext *cx, CallArgs args)
+{
+    RootedParallelArrayObject obj(cx, as(&args.thisv().toObject()));
+
+    IndexVector dims(cx);
+    if (!obj->getDimensions(cx, dims))
+        return false;
+
+    // Throw if already flat.
+    if (dims.length() == 1) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_ALREADY_FLAT);
+        return false;
+    }
+
+    // Flatten the two outermost dimensions.
+    dims[1] *= dims[0];
+    dims.erase(dims.begin());
+
+    RootedObject buffer(cx, obj->buffer());
+    return create(cx, buffer, obj->bufferOffset(), dims, args.rval());
+}
+
+bool
+ParallelArrayObject::partition(JSContext *cx, CallArgs args)
+{
+    if (args.length() < 1) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_MORE_ARGS_NEEDED,
+                             "ParallelArray.prototype.partition", "0", "s");
+        return false;
+    }
+
+    uint32_t newDimension;
+    if (!ToUint32(cx, args[0], &newDimension))
+        return false;
+
+    RootedParallelArrayObject obj(cx, as(&args.thisv().toObject()));
+
+    // Throw if the outer dimension is not divisible by the new dimension.
+    uint32_t outer = obj->outermostDimension();
+    if (outer % newDimension) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_BAD_PARTITION);
+        return false;
+    }
+
+    IndexVector dims(cx);
+    if (!obj->getDimensions(cx, dims))
+        return false;
+
+    // Set the new outermost dimension to be the quotient of the old outermost
+    // dimension and the new dimension.
+    if (!dims.insert(dims.begin(), outer / newDimension))
+        return false;
+
+    // Set the old outermost dimension to be the new dimension.
+    dims[1] = newDimension;
+
+    RootedObject buffer(cx, obj->buffer());
+    return create(cx, buffer, obj->bufferOffset(), dims, args.rval());
+}
+
+bool
+ParallelArrayObject::get(JSContext *cx, CallArgs args)
+{
+    if (args.length() < 1) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_MORE_ARGS_NEEDED,
+                             "ParallelArray.prototype.get", "0", "s");
+        return false;
+    }
+
+    if (!args[0].isObject()) {
+        JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_BAD_ARG,
+                             ".prototype.get");
+        return false;
+    }
+
+    RootedParallelArrayObject obj(cx, as(&args.thisv().toObject()));
+    RootedObject indicesObj(cx, &(args[0].toObject()));
+
+    if (obj->isOneDimensional()) {
+        uint32_t length;
+        if (is(indicesObj))
+            length = as(indicesObj)->outermostDimension();
+        else if (!js_GetLengthProperty(cx, indicesObj, &length))
+            return false;
+
+        // If we're one dimensional, indexing more than one dimension is
+        // definitely out of bounds.
+        if (length > 1) {
+            args.rval().setUndefined();
+            return true;
+        }
+
+        RootedValue elem(cx);
+        uint32_t index;
+        if (is(indicesObj)) {
+            if (!as(indicesObj)->getParallelArrayElement(cx, 0, &elem))
+                return false;
+        } else {
+            if (!indicesObj->getElement(cx, 0, &elem))
+                return false;
+        }
+
+        if (!ToUint32(cx, elem, &index))
+            return false;
+
+        return obj->getElementFromOnlyDimension(cx, index, args.rval());
+    }
+
+    IndexInfo iv(cx);
+    if (!iv.initialize(cx, obj, 0))
+        return false;
+    if (!ArrayLikeToIndexVector(cx, indicesObj, iv.indices))
+        return false;
+
+    // Set undefined if definitely out of bounds.
+    if (iv.indices.length() > iv.dimensions.length()) {
+        args.rval().setUndefined();
+        return true;
+    }
+
+    return obj->getParallelArrayElement(cx, iv, args.rval());
+}
+
+bool
+ParallelArrayObject::dimensionsGetter(JSContext *cx, CallArgs args)
+{
+    args.rval().setObject(*(as(&args.thisv().toObject())->dimensionArray()));
+    return true;
+}
+
+bool
+ParallelArrayObject::lengthGetter(JSContext *cx, CallArgs args)
+{
+    args.rval().setNumber(as(&args.thisv().toObject())->outermostDimension());
+    return true;
+}
+
+bool
+ParallelArrayObject::toStringBufferImpl(JSContext *cx, IndexInfo &iv, bool useLocale,
+                                        HandleObject buffer, StringBuffer &sb)
+{
+    JS_ASSERT(iv.isInitialized());
+
+    // The dimension we're printing out.
+    uint32_t d = iv.indices.length() + 1;
+
+    // If we still have more dimensions to go.
+    if (d < iv.dimensions.length()) {
+        if (!sb.append('<'))
+            return false;
+
+        iv.indices.infallibleAppend(0);
+        uint32_t length = iv.dimensions[d - 1];
+        for (size_t i = 0; i < length; i++) {
+            iv.indices[d - 1] = i;
+            if (!toStringBufferImpl(cx, iv, useLocale, buffer, sb) ||
+                (i + 1 != length && !sb.append(',')))
+            {
+                return false;
+            }
+        }
+        iv.indices.shrinkBy(1);
+
+        if (!sb.append('>'))
+            return false;
+
+        return true;
+    }
+
+    // We're on the last dimension.
+    if (!sb.append('<'))
+        return false;
+
+    uint32_t offset;
+    uint32_t length;
+
+    // If the array is flat, we can just use the entire extent.
+    if (d == 1) {
+        offset = bufferOffset();
+        length = iv.dimensions[0];
+    } else {
+        offset = bufferOffset() + iv.toScalar();
+        length = iv.partialProducts[d - 2];
+    }
+
+    RootedValue tmp(cx);
+    RootedValue localeElem(cx);
+    RootedId id(cx);
+
+    const Value *start = buffer->getDenseArrayElements() + offset;
+    const Value *end = start + length;
+    const Value *elem;
+
+    for (elem = start; elem < end; elem++) {
+        if (!JS_CHECK_OPERATION_LIMIT(cx))
+            return false;
+
+        if (!elem->isMagic(JS_ARRAY_HOLE) && !elem->isNullOrUndefined()) {
+            if (useLocale) {
+                tmp = *elem;
+                JSObject *robj = ToObject(cx, tmp);
+                if (!robj)
+                    return false;
+
+                id = NameToId(cx->runtime->atomState.toLocaleStringAtom);
+                if (!robj->callMethod(cx, id, 0, NULL, &localeElem) ||
+                    !ValueToStringBuffer(cx, localeElem, sb))
+                {
+                    return false;
+                }
+            } else {
+                if (!ValueToStringBuffer(cx, *elem, sb))
+                    return false;
+            }
+        }
+
+        if (elem + 1 != end && !sb.append(','))
+            return false;
+    }
+
+    if (!sb.append('>'))
+        return false;
+
+    return true;
+}
+
+bool
+ParallelArrayObject::toStringBuffer(JSContext *cx, bool useLocale, StringBuffer &sb)
+{
+    RootedParallelArrayObject self(cx, this);
+    IndexInfo iv(cx);
+    if (!iv.initialize(cx, self, 0))
+        return false;
+    RootedObject buffer(cx, this->buffer());
+    return toStringBufferImpl(cx, iv, useLocale, buffer, sb);
+}
+
+bool
+ParallelArrayObject::toString(JSContext *cx, CallArgs args)
+{
+    StringBuffer sb(cx);
+    if (!as(&args.thisv().toObject())->toStringBuffer(cx, false, sb))
+        return false;
+
+    if (JSString *str = sb.finishString()) {
+        args.rval().setString(str);
+        return true;
+    }
+
+    return false;
+}
+
+bool
+ParallelArrayObject::toLocaleString(JSContext *cx, CallArgs args)
+{
+    StringBuffer sb(cx);
+    if (!as(&args.thisv().toObject())->toStringBuffer(cx, true, sb))
+        return false;
+
+    if (JSString *str = sb.finishString()) {
+        args.rval().setString(str);
+        return true;
+    }
+
+    return false;
+}
+
+void
+ParallelArrayObject::mark(JSTracer *trc, JSObject *obj)
+{
+    gc::MarkSlot(trc, &obj->getSlotRef(SLOT_DIMENSIONS), "parallelarray.shape");
+    gc::MarkSlot(trc, &obj->getSlotRef(SLOT_BUFFER), "parallelarray.buffer");
+}
+
+JSBool
+ParallelArrayObject::lookupGeneric(JSContext *cx, HandleObject obj, HandleId id,
+                                   MutableHandleObject objp, MutableHandleShape propp)
+{
+    RootedObject buffer(cx, as(obj)->buffer());
+
+    if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom) ||
+        as(obj)->inOutermostDimensionRange(cx, id)) {
+        MarkNonNativePropertyFound(obj, propp);
+        objp.set(obj);
+        return true;
+    }
+
+    if (JSObject *proto = obj->getProto()) {
+        return proto->lookupGeneric(cx, id, objp, propp);
+    }
+
+    objp.set(NULL);
+    propp.set(NULL);
+    return true;
+}
+
+JSBool
+ParallelArrayObject::lookupProperty(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                                    MutableHandleObject objp, MutableHandleShape propp)
+{
+    RootedId id(cx, NameToId(name));
+    return lookupGeneric(cx, obj, id, objp, propp);
+}
+
+JSBool
+ParallelArrayObject::lookupElement(JSContext *cx, HandleObject obj, uint32_t index,
+                                   MutableHandleObject objp, MutableHandleShape propp)
+{
+    if (as(obj)->inOutermostDimensionRange(index)) {
+        MarkNonNativePropertyFound(obj, propp);
+        objp.set(obj);
+        return true;
+    }
+
+    if (JSObject *proto = obj->getProto())
+        return proto->lookupElement(cx, index, objp, propp);
+
+    objp.set(NULL);
+    propp.set(NULL);
+    return true;
+}
+
+JSBool
+ParallelArrayObject::lookupSpecial(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                                   MutableHandleObject objp, MutableHandleShape propp)
+{
+    RootedId id(cx, SPECIALID_TO_JSID(sid));
+    return lookupGeneric(cx, obj, id, objp, propp);
+}
+
+JSBool
+ParallelArrayObject::defineGeneric(JSContext *cx, HandleObject obj, HandleId id, HandleValue Value,
+                                   JSPropertyOp getter, StrictPropertyOp setter, unsigned attrs)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::defineProperty(JSContext *cx, HandleObject obj,
+                                    HandlePropertyName name, HandleValue value,
+                                    JSPropertyOp getter, StrictPropertyOp setter, unsigned attrs)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::defineElement(JSContext *cx, HandleObject obj,
+                                   uint32_t index, HandleValue value,
+                                   PropertyOp getter, StrictPropertyOp setter, unsigned attrs)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::defineSpecial(JSContext *cx, HandleObject obj,
+                                   HandleSpecialId sid, HandleValue value,
+                                   PropertyOp getter, StrictPropertyOp setter, unsigned attrs)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::getGeneric(JSContext *cx, HandleObject obj, HandleObject receiver,
+                                HandleId id, MutableHandleValue vp)
+{
+    Value idval = IdToValue(id);
+
+    uint32_t index;
+    if (IsDefinitelyIndex(idval, &index))
+        return getElement(cx, obj, receiver, index, vp);
+
+    JSAtom *atom = ToAtom(cx, idval);
+    if (!atom)
+        return false;
+
+    if (atom->isIndex(&index))
+        return getElement(cx, obj, receiver, index, vp);
+
+    Rooted<PropertyName*> name(cx, atom->asPropertyName());
+    return getProperty(cx, obj, receiver, name, vp);
+}
+
+JSBool
+ParallelArrayObject::getProperty(JSContext *cx, HandleObject obj, HandleObject receiver,
+                                 HandlePropertyName name, MutableHandleValue vp)
+{
+    if (name == cx->runtime->atomState.lengthAtom) {
+        vp.setNumber(as(obj)->outermostDimension());
+        return true;
+    }
+
+    if (JSObject *proto = obj->getProto())
+        return proto->getProperty(cx, receiver, name, vp);
+
+    vp.setUndefined();
+    return true;
+}
+
+JSBool
+ParallelArrayObject::getElement(JSContext *cx, HandleObject obj, HandleObject receiver,
+                                uint32_t index, MutableHandleValue vp)
+{
+    RootedParallelArrayObject source(cx, as(obj));
+    if (source->inOutermostDimensionRange(index)) {
+        if (source->isOneDimensional())
+            return source->getElementFromOnlyDimension(cx, index, vp);
+        return source->getParallelArrayElement(cx, index, vp);
+    }
+
+    if (JSObject *proto = obj->getProto())
+        return proto->getElement(cx, receiver, index, vp);
+
+    vp.setUndefined();
+    return true;
+}
+
+JSBool
+ParallelArrayObject::getSpecial(JSContext *cx, HandleObject obj, HandleObject receiver,
+                                HandleSpecialId sid, MutableHandleValue vp)
+{
+    if (!obj->getProto()) {
+        vp.setUndefined();
+        return true;
+    }
+
+    RootedId id(cx, SPECIALID_TO_JSID(sid));
+    return baseops::GetProperty(cx, obj, receiver, id, vp);
+}
+
+JSBool
+ParallelArrayObject::setGeneric(JSContext *cx, HandleObject obj, HandleId id,
+                                MutableHandleValue vp, JSBool strict)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::setProperty(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                                 MutableHandleValue vp, JSBool strict)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::setElement(JSContext *cx, HandleObject obj, uint32_t index,
+                                MutableHandleValue vp, JSBool strict)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::setSpecial(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                                MutableHandleValue vp, JSBool strict)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::getGenericAttributes(JSContext *cx, HandleObject obj, HandleId id,
+                                          unsigned *attrsp)
+{
+    if (JSID_IS_ATOM(id, cx->runtime->atomState.lengthAtom))
+        *attrsp = JSPROP_PERMANENT | JSPROP_READONLY;
+    else
+        *attrsp = JSPROP_PERMANENT | JSPROP_READONLY | JSPROP_ENUMERATE;
+
+    return true;
+}
+
+JSBool
+ParallelArrayObject::getPropertyAttributes(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                                           unsigned *attrsp)
+{
+    if (name == cx->runtime->atomState.lengthAtom)
+        *attrsp = JSPROP_PERMANENT | JSPROP_READONLY;
+    return true;
+}
+
+JSBool
+ParallelArrayObject::getElementAttributes(JSContext *cx, HandleObject obj, uint32_t index,
+                                          unsigned *attrsp)
+{
+    *attrsp = JSPROP_PERMANENT | JSPROP_READONLY | JSPROP_ENUMERATE;
+    return true;
+}
+
+JSBool
+ParallelArrayObject::getSpecialAttributes(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                                          unsigned *attrsp)
+{
+    *attrsp = JSPROP_PERMANENT | JSPROP_READONLY | JSPROP_ENUMERATE;
+    return true;
+}
+
+JSBool
+ParallelArrayObject::setGenericAttributes(JSContext *cx, HandleObject obj, HandleId id,
+                                          unsigned *attrsp)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::setPropertyAttributes(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                                           unsigned *attrsp)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::setElementAttributes(JSContext *cx, HandleObject obj, uint32_t index,
+                                          unsigned *attrsp)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::setSpecialAttributes(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                                          unsigned *attrsp)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::deleteGeneric(JSContext *cx, HandleObject obj, HandleId id,
+                                   MutableHandleValue rval, JSBool strict)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::deleteProperty(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                                    MutableHandleValue rval, JSBool strict)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::deleteElement(JSContext *cx, HandleObject obj, uint32_t index,
+                                   MutableHandleValue rval, JSBool strict)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::deleteSpecial(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                                   MutableHandleValue rval, JSBool strict)
+{
+    JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_PAR_ARRAY_IMMUTABLE);
+    return false;
+}
+
+JSBool
+ParallelArrayObject::enumerate(JSContext *cx, HandleObject obj, JSIterateOp enum_op,
+                               Value *statep, jsid *idp)
+{
+    JS_ASSERT(is(obj));
+    RootedParallelArrayObject source(cx, as(obj));
+
+    uint32_t index;
+    switch (enum_op) {
+      case JSENUMERATE_INIT_ALL:
+      case JSENUMERATE_INIT:
+        statep->setInt32(0);
+        if (idp)
+            *idp = ::INT_TO_JSID(source->outermostDimension());
+        break;
+
+      case JSENUMERATE_NEXT:
+        index = static_cast<uint32_t>(statep->toInt32());
+        if (index < source->outermostDimension()) {
+            *idp = ::INT_TO_JSID(index);
+            statep->setInt32(index + 1);
+        } else {
+            JS_ASSERT(index == source->outermostDimension());
+            statep->setNull();
+        }
+        break;
+
+      case JSENUMERATE_DESTROY:
+        statep->setNull();
+        break;
+    }
+
+    return true;
+}
+
+JSObject *
+js_InitParallelArrayClass(JSContext *cx, JSObject *obj)
+{
+    return ParallelArrayObject::initClass(cx, obj);
+}
new file mode 100644
--- /dev/null
+++ b/js/src/builtin/ParallelArray.h
@@ -0,0 +1,399 @@
+/* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sw=4 et tw=99 ft=cpp:
+ *
+ * This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef ParallelArray_h__
+#define ParallelArray_h__
+
+#include "jsapi.h"
+#include "jscntxt.h"
+#include "jsobj.h"
+
+namespace js {
+
+class ParallelArrayObject;
+typedef Rooted<ParallelArrayObject *> RootedParallelArrayObject;
+typedef Handle<ParallelArrayObject *> HandleParallelArrayObject;
+
+//
+// ParallelArray Overview
+//
+// Parallel arrays are immutable, possibly multi-dimensional arrays which
+// enable parallel computation based on a few base operations. The execution
+// model is one of fallback: try to execute operations in parallel, falling
+// back to sequential implementation if (for whatever reason) the operation
+// could not be executed in paralle. The API allows leeway to implementers to
+// decide both representation and what is considered parallelizable.
+//
+// Currently ParallelArray objects are backed by dense arrays for ease of
+// GC. For the higher-dimensional case, data is stored in a packed, row-major
+// order representation in the backing dense array. See notes below about
+// IndexInfo in how to convert between scalar offsets into the backing array
+// and a vector of indices.
+//
+// Except for the comprehension form, all operations (e.g. map, filter,
+// reduce) operate on the outermost dimension only. That is, those operations
+// only operate on the "rows" of the array. "Element" is used in context of
+// ParallelArray objects to mean any indexable value of a ParallelArray
+// object. For a one dimensional array, elements are always scalar values. For
+// a higher dimensional array, elements could either be scalar values
+// (i.e. leaves) or ParallelArray objects of lesser dimensions
+// (i.e. subarrays).
+//
+
+class ParallelArrayObject : public JSObject {
+  public:
+    typedef Vector<uint32_t, 4> IndexVector;
+
+    //
+    // Helper structure to help index higher-dimensional arrays to convert
+    // between a vector of indices and scalar offsets for use in the flat
+    // backing dense array.
+    //
+    // IndexInfo instances _must_ be initialized using one of the initialize
+    // methods before use.
+    //
+    // Typical usage is stack allocating an IndexInfo, initializing it with a
+    // particular source ParallelArray object's dimensionality, and mutating
+    // the indices member vector. For instance, to iterate through everything
+    // in the first 2 dimensions of an array of > 2 dimensions:
+    //
+    //   IndexInfo iv(cx);
+    //   if (!iv.initialize(cx, source, 2))
+    //       return false;
+    //   for (uint32_t i = 0; i < iv.dimensions[0]; i++) {
+    //       for (uint32_t j = 0; j < iv.dimensions[1]; j++) {
+    //           iv.indices[0] = i;
+    //           iv.indices[1] = j;
+    //           if (source->getParallelArrayElement(cx, iv, &elem))
+    //               ...
+    //       }
+    //   }
+    //
+    // Note from the above that it is not required to fill out the indices
+    // vector up to the full dimensionality. For an N-dimensional array,
+    // having an indices vector of length D < N indexes a subarray.
+    //
+
+    struct IndexInfo {
+        // Vector of indices. Should be large enough to hold up to
+        // dimensions.length indices.
+        IndexVector indices;
+
+        // Vector of dimensions of the ParallelArray object that the indices
+        // are meant to index into.
+        IndexVector dimensions;
+
+        // Cached partial products of the dimensions defined by the following
+        // recurrence:
+        //
+        //   partialProducts[n] =
+        //     1                                      if n == |dimensions|
+        //     dimensions[n+1] * partialProducts[n+1] otherwise
+        //
+        // These are used for computing scalar offsets.
+        IndexVector partialProducts;
+
+        IndexInfo(JSContext *cx)
+            : indices(cx), dimensions(cx), partialProducts(cx)
+        {}
+
+        // Prepares indices and computes partial products. The space argument
+        // is the index space. The indices vector is resized to be of length
+        // space.
+        //
+        // The dimensions vector must be filled already, and space must be <=
+        // dimensions.length().
+        inline bool initialize(uint32_t space);
+
+        // Load dimensions from a source, then initialize as above.
+        inline bool initialize(JSContext *cx, HandleParallelArrayObject source,
+                               uint32_t space);
+
+        // Get the scalar length according to the dimensions vector, i.e. the
+        // product of the dimensions vector.
+        inline uint32_t scalarLengthOfDimensions();
+
+        // Compute the scalar index from the current index vector.
+        inline uint32_t toScalar();
+
+        // Set the index vector according to a scalar index.
+        inline bool fromScalar(uint32_t index);
+
+        bool isInitialized();
+    };
+
+    static JSObject *initClass(JSContext *cx, JSObject *obj);
+    static Class class_;
+
+    static inline bool is(const Value &v);
+    static inline bool is(JSObject *obj);
+    static inline ParallelArrayObject *as(JSObject *obj);
+
+    inline JSObject *dimensionArray();
+    inline JSObject *buffer();
+    inline uint32_t bufferOffset();
+    inline uint32_t outermostDimension();
+    inline bool isOneDimensional();
+    inline bool inOutermostDimensionRange(uint32_t index);
+    inline bool inOutermostDimensionRange(JSContext *cx, HandleId id);
+    inline bool getDimensions(JSContext *cx, IndexVector &dims);
+
+    // Specialized for one dimensional arrays. Use this if possible.
+    bool getElementFromOnlyDimension(JSContext *cx, uint32_t index, MutableHandleValue vp);
+
+    // The general case; works for arrays of any dimensionality.
+    bool getParallelArrayElement(JSContext *cx, IndexInfo &iv, MutableHandleValue vp);
+
+    // Convenience function for getting an element from the outermost
+    // dimension in the general case. This creates a temporary IndexInfo of
+    // length 1 with the 1st index set to the index parameter.
+    bool getParallelArrayElement(JSContext *cx, uint32_t index, MutableHandleValue vp);
+
+    bool toStringBuffer(JSContext *cx, bool useLocale, StringBuffer &sb);
+
+  private:
+    enum {
+        // The ParallelArray API refers to dimensions as "shape", but to avoid
+        // confusion with the internal engine notion of a shape we call it
+        // "dimensions" here.
+        SLOT_DIMENSIONS = 0,
+
+        // Underlying dense array.
+        SLOT_BUFFER,
+
+        // First index of the underlying buffer to be considered in bounds.
+        SLOT_BUFFER_OFFSET,
+
+        RESERVED_SLOTS
+    };
+
+    enum ExecutionStatus {
+        ExecutionFailed = 0,
+        ExecutionCompiled,
+        ExecutionSucceeded
+    };
+
+    // Execution modes are kept as static instances of structs that implement
+    // a signature that comprises of build, map, fold, scatter, and filter,
+    // whose argument lists are defined in the macros below.
+    //
+    // Even though the base class |ExecutionMode| is purely abstract, we only
+    // use dynamic dispatch when using the debug options. Almost always we
+    // directly call the member function on one of the statics.
+
+#define JS_PA_build_ARGS               \
+    JSContext *cx,                     \
+    IndexInfo &iv,                     \
+    HandleObject elementalFun,         \
+    HandleObject buffer
+
+#define JS_PA_map_ARGS                 \
+    JSContext *cx,                     \
+    HandleParallelArrayObject source,  \
+    HandleObject elementalFun,         \
+    HandleObject buffer
+
+#define JS_PA_reduce_ARGS              \
+    JSContext *cx,                     \
+    HandleParallelArrayObject source,  \
+    HandleObject elementalFun,         \
+    HandleObject buffer,               \
+    MutableHandleValue vp
+
+#define JS_PA_scatter_ARGS             \
+    JSContext *cx,                     \
+    HandleParallelArrayObject source,  \
+    HandleObject targets,              \
+    const Value &defaultValue,         \
+    HandleObject conflictFun,          \
+    HandleObject buffer
+
+#define JS_PA_filter_ARGS              \
+    JSContext *cx,                     \
+    HandleParallelArrayObject source,  \
+    HandleObject filters,              \
+    HandleObject buffer
+
+#define JS_PA_DECLARE_OP(NAME) \
+    ExecutionStatus NAME(JS_PA_ ## NAME ## _ARGS)
+
+#define JS_PA_DECLARE_ALL_OPS          \
+    JS_PA_DECLARE_OP(build);           \
+    JS_PA_DECLARE_OP(map);             \
+    JS_PA_DECLARE_OP(reduce);          \
+    JS_PA_DECLARE_OP(scatter);         \
+    JS_PA_DECLARE_OP(filter);
+
+    class ExecutionMode {
+      public:
+        // The comprehension form. Builds a higher-dimensional array using a
+        // kernel function.
+        virtual JS_PA_DECLARE_OP(build) = 0;
+
+        // Maps a kernel function over the outermost dimension of the array.
+        virtual JS_PA_DECLARE_OP(map) = 0;
+
+        // Reduce to a value using a kernel function. Scan is like reduce, but
+        // keeps the intermediate results in an array.
+        virtual JS_PA_DECLARE_OP(reduce) = 0;
+
+        // Scatter elements according to an index map.
+        virtual JS_PA_DECLARE_OP(scatter) = 0;
+
+        // Filter elements according to a truthy array.
+        virtual JS_PA_DECLARE_OP(filter) = 0;
+
+        virtual const char *toString() = 0;
+    };
+
+    // Fallback means try parallel first, and if unable to execute in
+    // parallel, execute sequentially.
+    class FallbackMode : public ExecutionMode {
+      public:
+        JS_PA_DECLARE_ALL_OPS
+        const char *toString() { return "fallback"; }
+    };
+
+    class ParallelMode : public ExecutionMode {
+      public:
+        JS_PA_DECLARE_ALL_OPS
+        const char *toString() { return "parallel"; }
+    };
+
+    class SequentialMode : public ExecutionMode {
+      public:
+        JS_PA_DECLARE_ALL_OPS
+        const char *toString() { return "sequential"; }
+    };
+
+    static SequentialMode sequential;
+    static ParallelMode parallel;
+    static FallbackMode fallback;
+
+#undef JS_PA_build_ARGS
+#undef JS_PA_map_ARGS
+#undef JS_PA_reduce_ARGS
+#undef JS_PA_scatter_ARGS
+#undef JS_PA_filter_ARGS
+#undef JS_PA_DECLARE_OP
+#undef JS_PA_DECLARE_ALL_OPS
+
+#ifdef DEBUG
+    // Debug options can be passed in as an extra argument to the
+    // operations. The grammar is:
+    //
+    //   options ::= { mode: "par" | "seq",
+    //                 expect: "fail" | "bail" | "success" }
+    struct DebugOptions {
+        ExecutionMode *mode;
+        ExecutionStatus expect;
+        bool init(JSContext *cx, const Value &v);
+        bool check(JSContext *cx, ExecutionStatus actual);
+    };
+
+    static const char *ExecutionStatusToString(ExecutionStatus ss);
+#endif
+
+    static JSFunctionSpec methods[];
+    static Class protoClass;
+
+    static inline bool DenseArrayToIndexVector(JSContext *cx, HandleObject obj,
+                                               IndexVector &indices);
+
+    bool toStringBufferImpl(JSContext *cx, IndexInfo &iv, bool useLocale,
+                            HandleObject buffer, StringBuffer &sb);
+
+    static bool create(JSContext *cx, MutableHandleValue vp);
+    static bool create(JSContext *cx, HandleObject buffer, MutableHandleValue vp);
+    static bool create(JSContext *cx, HandleObject buffer, uint32_t offset,
+                       const IndexVector &dims, MutableHandleValue vp);
+    static JSBool construct(JSContext *cx, unsigned argc, Value *vp);
+
+    static bool map(JSContext *cx, CallArgs args);
+    static bool reduce(JSContext *cx, CallArgs args);
+    static bool scan(JSContext *cx, CallArgs args);
+    static bool scatter(JSContext *cx, CallArgs args);
+    static bool filter(JSContext *cx, CallArgs args);
+    static bool flatten(JSContext *cx, CallArgs args);
+    static bool partition(JSContext *cx, CallArgs args);
+    static bool get(JSContext *cx, CallArgs args);
+    static bool dimensionsGetter(JSContext *cx, CallArgs args);
+    static bool lengthGetter(JSContext *cx, CallArgs args);
+    static bool toString(JSContext *cx, CallArgs args);
+    static bool toLocaleString(JSContext *cx, CallArgs args);
+    static bool toSource(JSContext *cx, CallArgs args);
+
+    static void mark(JSTracer *trc, JSObject *obj);
+    static JSBool lookupGeneric(JSContext *cx, HandleObject obj, HandleId id,
+                                MutableHandleObject objp, MutableHandleShape propp);
+    static JSBool lookupProperty(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                                 MutableHandleObject objp, MutableHandleShape propp);
+    static JSBool lookupElement(JSContext *cx, HandleObject obj, uint32_t index,
+                                MutableHandleObject objp, MutableHandleShape propp);
+    static JSBool lookupSpecial(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                                MutableHandleObject objp, MutableHandleShape propp);
+    static JSBool defineGeneric(JSContext *cx, HandleObject obj, HandleId id, HandleValue value,
+                                JSPropertyOp getter, StrictPropertyOp setter, unsigned attrs);
+    static JSBool defineProperty(JSContext *cx, HandleObject obj,
+                                 HandlePropertyName name, HandleValue value,
+                                 JSPropertyOp getter, StrictPropertyOp setter, unsigned attrs);
+    static JSBool defineElement(JSContext *cx, HandleObject obj,
+                                uint32_t index, HandleValue value,
+                                PropertyOp getter, StrictPropertyOp setter, unsigned attrs);
+    static JSBool defineSpecial(JSContext *cx, HandleObject obj,
+                                HandleSpecialId sid, HandleValue value,
+                                PropertyOp getter, StrictPropertyOp setter, unsigned attrs);
+    static JSBool getGeneric(JSContext *cx, HandleObject obj, HandleObject receiver,
+                             HandleId id, MutableHandleValue vp);
+    static JSBool getProperty(JSContext *cx, HandleObject obj, HandleObject receiver,
+                              HandlePropertyName name, MutableHandleValue vp);
+    static JSBool getElement(JSContext *cx, HandleObject obj, HandleObject receiver,
+                             uint32_t index, MutableHandleValue vp);
+    static JSBool getSpecial(JSContext *cx, HandleObject obj, HandleObject receiver,
+                             HandleSpecialId sid, MutableHandleValue vp);
+    static JSBool setGeneric(JSContext *cx, HandleObject obj, HandleId id,
+                             MutableHandleValue vp, JSBool strict);
+    static JSBool setProperty(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                              MutableHandleValue vp, JSBool strict);
+    static JSBool setElement(JSContext *cx, HandleObject obj, uint32_t index,
+                             MutableHandleValue vp, JSBool strict);
+    static JSBool setSpecial(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                             MutableHandleValue vp, JSBool strict);
+    static JSBool getGenericAttributes(JSContext *cx, HandleObject obj, HandleId id,
+                                       unsigned *attrsp);
+    static JSBool getPropertyAttributes(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                                        unsigned *attrsp);
+    static JSBool getElementAttributes(JSContext *cx, HandleObject obj, uint32_t index,
+                                       unsigned *attrsp);
+    static JSBool getSpecialAttributes(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                                       unsigned *attrsp);
+    static JSBool setGenericAttributes(JSContext *cx, HandleObject obj, HandleId id,
+                                       unsigned *attrsp);
+    static JSBool setPropertyAttributes(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                                        unsigned *attrsp);
+    static JSBool setElementAttributes(JSContext *cx, HandleObject obj, uint32_t index,
+                                       unsigned *attrsp);
+    static JSBool setSpecialAttributes(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                                       unsigned *attrsp);
+    static JSBool deleteGeneric(JSContext *cx, HandleObject obj, HandleId id,
+                                MutableHandleValue rval, JSBool strict);
+    static JSBool deleteProperty(JSContext *cx, HandleObject obj, HandlePropertyName name,
+                                 MutableHandleValue rval, JSBool strict);
+    static JSBool deleteElement(JSContext *cx, HandleObject obj, uint32_t index,
+                                MutableHandleValue rval, JSBool strict);
+    static JSBool deleteSpecial(JSContext *cx, HandleObject obj, HandleSpecialId sid,
+                                MutableHandleValue rval, JSBool strict);
+    static JSBool enumerate(JSContext *cx, HandleObject obj, JSIterateOp enum_op,
+                            Value *statep, jsid *idp);
+};
+
+} // namespace js
+
+extern JSObject *
+js_InitParallelArrayClass(JSContext *cx, JSObject *obj);
+
+#endif // ParallelArray_h__
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/comprehension-1.js
@@ -0,0 +1,9 @@
+
+function buildComprehension() {
+  // 1D comprehension 
+  var p = new ParallelArray(10, function (idx) { return idx; });
+  var a = [0,1,2,3,4,5,6,7,8,9];
+  assertEq(p.toString(), "<" + a.join(",") + ">");
+}
+
+buildComprehension();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/comprehension-2.js
@@ -0,0 +1,9 @@
+
+function buildMultidim() {
+  // 2D comprehension
+  var p = new ParallelArray([2,2], function (i,j) { return i + j; });
+  assertEq(p.shape.toString(), [2,2].toString());
+  assertEq(p.toString(), "<<0,1>,<1,2>>");
+}
+
+buildMultidim();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/comprehension-fn-args.js
@@ -0,0 +1,15 @@
+
+function buildComprehension() {
+  // Test kernel function arguments
+  var shape = [];
+  for (var i = 0; i < 8; i++) {
+    shape.push(i+1);
+    var p = new ParallelArray(shape, function () {
+      assertEq(arguments.length, shape.length);
+      for (var j = 0; j < shape.length; j++)
+        assertEq(arguments[j] >= 0 && arguments[j] < shape[j], true);
+    });
+  }
+}
+
+buildComprehension();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/comprehension-scale.js
@@ -0,0 +1,31 @@
+
+function buildComprehension() {
+  var H = 96;
+  var W = 96;
+  var d = 4;
+  // 3D 96x96x4 texture-like PA
+  var p = new ParallelArray([H,W,d], function (i,j,k) { return i + j + k; });
+  var a = "<";
+  for (var i = 0; i < H; i++) {
+    a += "<";
+    for (var j = 0; j < W; j++) {
+      a += "<";
+      for (var k = 0; k < d; k++) {
+        a += i+j+k;
+        if (k !== d - 1)
+          a += ",";
+      }
+      a += ">";
+      if (j !== W - 1)
+        a += ","
+    }
+    a += ">";
+    if (i !== H - 1)
+      a += ","
+  }
+  a += ">"
+
+  assertEq(p.toString(), a);
+}
+
+buildComprehension();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/comprehension-throws.js
@@ -0,0 +1,7 @@
+// |jit-test| error: TypeError;
+function buildComprehension() {
+  // Throws if elemental fun not callable
+  var p = new ParallelArray([2,2], undefined);
+}
+
+buildComprehension();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/constructor-1.js
@@ -0,0 +1,16 @@
+function bracket(s) {
+  return "<" + s + ">";
+}
+
+function buildSimple() {
+  // Simple constructor
+  var a = [1,2,3,4,5];
+  var p = new ParallelArray(a);
+  var e = a.join(",");
+  assertEq(p.toString(), bracket(e));
+  a[0] = 9;
+  // No sharing
+  assertEq(p.toString(), bracket(e));
+}
+
+buildSimple();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/constructor-2.js
@@ -0,0 +1,13 @@
+
+function buildWithHoles() {
+  // Test holes
+  var a = new Array(5);
+  for (var cnt = 0; cnt < a.length; cnt+=2) {
+      a[cnt] = cnt;
+  }
+  var b = [0,1,2,3,4];
+  var p = new ParallelArray(a);
+  assertEq(Object.keys(p).join(","), Object.keys(b).join(","));
+}
+
+buildWithHoles();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/constructor-3.js
@@ -0,0 +1,13 @@
+function bracket(s) {
+  return "<" + s + ">";
+}
+
+function buildArrayLike() {
+  // Construct copying from array-like
+  var a = { 0: 1, 1: 2, 2: 3, 3: 4, length: 4 };
+  var p = new ParallelArray(a);
+  var e = Array.prototype.join.call(a, ",");
+  assertEq(p.toString(), bracket(e));
+}
+
+buildArrayLike();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/constructor-4.js
@@ -0,0 +1,12 @@
+
+function buildPA() {
+  // Construct copying from PA
+  var p1 = new ParallelArray([1,2,3,4]);
+  var p2 = new ParallelArray(p1);
+  assertEq(p1.toString(), p2.toString());
+  var p1d = new ParallelArray([2,2], function(i,j) { return i + j; });
+  var p2d = new ParallelArray(p1d);
+  assertEq(p1d.toString(), p2d.toString());
+}
+
+buildPA();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/element-1.js
@@ -0,0 +1,13 @@
+function testElement() {
+  // Test getting element from 1D
+  var a = [1,{},"a",false]
+  var p = new ParallelArray(a);
+  for (var i = 0; i < a.length; i++) {
+    assertEq(p[i], p[i]);
+    assertEq(p[i], a[i]);
+  }
+  // Test out of bounds
+  assertEq(p[42], undefined);
+}
+
+testElement();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/element-2.js
@@ -0,0 +1,11 @@
+function testElement() {
+  // Test getting element from higher dimension
+  var p = new ParallelArray([2,2,2], function () { return 0; });
+  assertEq(p[0].toString(), "<<0,0>,<0,0>>");
+  // Should create new wrapper
+  assertEq(p[0] !== p[0], true);
+  // Test out of bounds
+  assertEq(p[42], undefined);
+}
+
+testElement();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/element-3.js
@@ -0,0 +1,10 @@
+function testElement() {
+  var p = new ParallelArray([9]);
+  var desc = Object.getOwnPropertyDescriptor(p, "0");
+  assertEq(desc.enumerable, true);
+  assertEq(desc.configurable, false);
+  assertEq(desc.writable, false);
+  assertEq(desc.value, 9);
+}
+
+testElement();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/element-4.js
@@ -0,0 +1,8 @@
+function testElement() {
+  // Test crazy prototype walking
+  ParallelArray.prototype[42] = "foo";
+  var p = new ParallelArray([1,2,3,4]);
+  assertEq(p[42], "foo");
+}
+
+testElement();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/enumerate-1.js
@@ -0,0 +1,7 @@
+function testEnumerate() {
+  var p = new ParallelArray([1,2,3,4,5]);
+  for (var i in p)
+    assertEq(i >= 0 && i < p.length, true);
+}
+
+testEnumerate();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/filter-1.js
@@ -0,0 +1,13 @@
+
+function testFilterAll() {
+  // Test filtering everything (leaving everything in)
+  var p = new ParallelArray([0,1,2,3,4]);
+  var all = p.map(function (i) { return true; });
+  var r = p.filter(all);
+  assertEq(r.toString(), "<0,1,2,3,4>");
+  var p = new ParallelArray([5,2], function(i,j) { return i+j; });
+  var r = p.filter(all);
+  assertEq(r.toString(), "<<0,1>,<1,2>,<2,3>,<3,4>,<4,5>>");
+}
+
+testFilterAll();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/filter-2.js
@@ -0,0 +1,12 @@
+function testFilterNone() {
+  // Test filtering (removing everything)
+  var p = new ParallelArray([0,1,2,3,4]);
+  var none = p.map(function () { return false; });
+  var r = p.filter(none);
+  assertEq(r.toString(), "<>");
+  var p = new ParallelArray([5,2], function(i,j) { return i+j; });
+  var r = p.filter(none);
+  assertEq(r.toString(), "<>");
+}
+
+testFilterNone();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/filter-3.js
@@ -0,0 +1,16 @@
+function bracket(s) {
+  return "<" + s + ">";
+}
+
+function testFilterSome() {
+  var p = new ParallelArray([0,1,2,3,4]);
+  var evenBelowThree = p.map(function (i) { return ((i%2) === 0) && (i < 3); });
+  var r = p.filter(evenBelowThree);
+  assertEq(r.toString(), bracket([0,2].join(",")));
+  var p = new ParallelArray([5,2], function (i,j) { return i; });
+  var evenBelowThree = p.map(function (i) { return ((i[0]%2) === 0) && (i[0] < 3); });
+  var r = p.filter(evenBelowThree);
+  assertEq(r.toString(), bracket(["<0,0>","<2,2>"].join(",")));
+}
+
+testFilterSome();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/filter-4.js
@@ -0,0 +1,18 @@
+function bracket(s) {
+  return "<" + s + ">";
+}
+
+function testFilterMisc() {
+  var p = new ParallelArray([0,1,2]);
+  // Test array
+  var r = p.filter([true, false, true]);
+  assertEq(r.toString(), bracket([0,2].join(",")));
+  // Test array-like
+  var r = p.filter({ 0: true, 1: false, 2: true, length: 3 });
+  assertEq(r.toString(), bracket([0,2].join(",")));
+  // Test truthy
+  var r = p.filter([1, "", {}]);
+  assertEq(r.toString(), bracket([0,2].join(",")));
+}
+
+testFilterMisc();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/flatten-1.js
@@ -0,0 +1,11 @@
+function testFlatten() {
+  var shape = [5];
+  for (var i = 0; i < 7; i++) {
+    shape.push(i+1);
+    var p = new ParallelArray(shape, function(i,j) { return i+j; });
+    var flatShape = ([shape[0] * shape[1]]).concat(shape.slice(2));
+    assertEq(p.flatten().shape.toString(), flatShape.toString());
+  }
+}
+
+testFlatten();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/flatten-2.js
@@ -0,0 +1,7 @@
+function testFlatten() {
+  var p = new ParallelArray([2,2], function(i,j) { return i+j; });
+  var p2 = new ParallelArray([0,1,1,2]);
+  assertEq(p.flatten().toString(), p2.toString());
+}
+
+testFlatten();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/flatten-throws.js
@@ -0,0 +1,9 @@
+// |jit-test| error: Error;
+
+function testFlattenFlat() {
+  // Throw on flattening flat array
+  var p = new ParallelArray([1]);
+  var f = p.flatten();
+}
+
+testFlattenFlat();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/get-1.js
@@ -0,0 +1,8 @@
+function testGet() {
+  var a = [1,2,3,4,5];
+  var p = new ParallelArray(a);
+  for (var i = 0; i < a.length; i++)
+    assertEq(p.get([i]), a[i]);
+}
+
+testGet();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/get-2.js
@@ -0,0 +1,10 @@
+function testGet() {
+  var p = new ParallelArray([2,2,2], function(i,j,k) { return i+j+k; });
+  assertEq(p.get([1,1,1]), 1+1+1);
+  var p2 = new ParallelArray([2], function(i) { return 1+1+i; });
+  assertEq(p.get([1,1]).toString(), p2.toString());
+  var p3 = new ParallelArray([2,2], function(i,j) { return 1+i+j; });
+  assertEq(p.get([1]).toString(), p3.toString());
+}
+
+testGet();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/get-3.js
@@ -0,0 +1,8 @@
+function testGetNoCraziness() {
+  // .get shouldn't do prototype walks
+  ParallelArray.prototype[42] = "foo";
+  var p = new ParallelArray([1,2,3,4]);
+  assertEq(p.get([42]), undefined);
+}
+
+testGetNoCraziness();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/get-4.js
@@ -0,0 +1,6 @@
+function testGetBounds() {
+  var p = new ParallelArray([1,2,3,4]);
+  assertEq(p.get([42]), undefined);
+}
+
+testGetBounds();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/get-5.js
@@ -0,0 +1,9 @@
+function testGet() {
+  // Test .get on array-like
+  var p = new ParallelArray([1,2,3,4]);
+  assertEq(p.get({ 0: 1, length: 1 }), 2);
+  var p2 = new ParallelArray([2,2], function(i,j) { return i+j; });
+  assertEq(p2.get({ 0: 1, 1: 0, length: 2 }), 1);
+}
+
+testGet();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/get-throws.js
@@ -0,0 +1,9 @@
+// |jit-test| error: TypeError;
+
+function testGetThrows() {
+  // Throw if argument not object
+  var p = new ParallelArray([1,2,3,4]);
+  p.get(42);
+}
+
+testGetThrows();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/length-1.js
@@ -0,0 +1,11 @@
+function testLength() {
+  var a = [1,2,3];
+  var p = new ParallelArray(a);
+  assertEq(p.length, a.length);
+  // Test holes
+  var a = [1,,3];
+  var p = new ParallelArray(a);
+  assertEq(p.length, a.length);
+}
+
+testLength();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/length-2.js
@@ -0,0 +1,12 @@
+function testLength() {
+  // Test higher dimension shape up to 8D
+  var shape = [];
+  for (var i = 0; i < 8; i++) {
+    shape.push(i+1);
+    var p = new ParallelArray(shape, function () { return 0; });
+    // Length should be outermost dimension
+    assertEq(p.length, shape[0]);
+  }
+}
+
+testLength();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/length-3.js
@@ -0,0 +1,11 @@
+function testLength() {
+  // Test length attributes
+  var p = new ParallelArray([1,2,3,4]);
+  var desc = Object.getOwnPropertyDescriptor(p, "length");
+  assertEq(desc.enumerable, false);
+  assertEq(desc.configurable, false);
+  assertEq(desc.writable, false);
+  assertEq(desc.value, 4);
+}
+
+testLength();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/map-1.js
@@ -0,0 +1,11 @@
+function bracket(s) {
+  return "<" + s + ">";
+}
+
+function testMap() {
+    var p = new ParallelArray([0,1,2,3,4]);
+    var m = p.map(function (v) { return v+1; });
+    assertEq(m.toString(), bracket([1,2,3,4,5].join(",")));
+}
+
+testMap();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/map-2.js
@@ -0,0 +1,9 @@
+function testMap() {
+  // Test overflow
+  var p = new ParallelArray([1 << 30]);
+  var m = p.map(function(x) { return x * 4; });
+  assertEq(m[0], (1 << 30) * 4);
+}
+
+testMap();
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/map-3.js
@@ -0,0 +1,9 @@
+function testMap() {
+  // Test mapping higher dimensional
+  var p = new ParallelArray([2,2], function (i,j) { return i+j; });
+  var m = p.map(function(x) { return x.toString(); });
+  assertEq(m.toString(), "<<0,1>,<1,2>>");
+}
+
+testMap();
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/map-fn-args.js
@@ -0,0 +1,19 @@
+function testMap() {
+  // Test map elemental fun args
+  var p = new ParallelArray([1,2,3,4]);
+  var m = p.map(function(e) {
+    assertEq(e >= 1 && e <= 4, true); 
+  });
+  var m = p.map(function(e,i) {
+    assertEq(e >= 1 && e <= 4, true); 
+    assertEq(i >= 0 && i < 4, true);
+  });
+  var m = p.map(function(e,i,c) {
+    assertEq(e >= 1 && e <= 4, true); 
+    assertEq(i >= 0 && i < 4, true);
+    assertEq(c, p);
+  });
+}
+
+testMap();
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/map-throws.js
@@ -0,0 +1,9 @@
+// |jit-test| error: TypeError;
+function testMap() {
+  // Test map throws
+  var p = new ParallelArray([1,2,3,4])
+  var m = p.map(42);
+}
+
+testMap();
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/partition-1.js
@@ -0,0 +1,13 @@
+function testPartition() {
+  var p = new ParallelArray([1,2,3,4,5,6,7,8]);
+  var pp = p.partition(2);
+  var ppp = pp.partition(2);
+  var ppShape = [p.shape[0] / 2, 2].concat(p.shape.slice(1));
+  var pppShape = [pp.shape[0] / 2, 2].concat(pp.shape.slice(1));
+  assertEq(pp.shape.toString(), ppShape.toString())
+  assertEq(pp.toString(), "<<1,2>,<3,4>,<5,6>,<7,8>>");
+  assertEq(ppp.shape.toString(), pppShape.toString())
+  assertEq(ppp.toString(), "<<<1,2>,<3,4>>,<<5,6>,<7,8>>>");
+}
+
+testPartition();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/partition-throws.js
@@ -0,0 +1,8 @@
+// |jit-test| error: Error;
+
+function testPartitionDivisible() {
+  var p = new ParallelArray([1,2,3,4]);
+  var pp = p.partition(3);
+}
+
+testPartitionDivisible();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/reduce-1.js
@@ -0,0 +1,8 @@
+
+function testReduce() {
+  var p = new ParallelArray([1,2,3,4,5]);
+  var r = p.reduce(function (v, p) { return v*p; });
+  assertEq(r, 120);
+}
+
+testReduce();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/reduce-2.js
@@ -0,0 +1,8 @@
+
+function testReduceOne() {
+  var p = new ParallelArray([1]);
+  var r = p.reduce(function (v, p) { return v*p; });
+  assertEq(r, 1);
+}
+
+testReduceOne();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/reduce-3.js
@@ -0,0 +1,14 @@
+
+function testReduce() {
+  // Test reduce on higher dimensional
+  // XXX Can we test this better?
+  var shape = [2];
+  for (var i = 0; i < 7; i++) {
+    shape.push(i+1);
+    var p = new ParallelArray(shape, function () { return i+1; });
+    var r = p.reduce(function (a, b) { return a; });
+    assertEq(r.shape.length, i + 1);
+  }
+}
+
+testReduce();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/reduce-fn-args.js
@@ -0,0 +1,13 @@
+
+function testReduce() {
+  // Test reduce elemental fun args
+  var p = new ParallelArray([1,2,3,4]);
+  var r = p.reduce(function (a, b) {
+    assertEq(a >= 1 && a <= 4, true);
+    assertEq(b >= 1 && b <= 4, true);
+    return a;
+  });
+  assertEq(r >= 1 && r <= 4, true);
+}
+
+testReduce();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/reduce-throws.js
@@ -0,0 +1,16 @@
+load(libdir + "asserts.js");
+
+function testReduceThrows() {
+  // Throw on empty
+  assertThrowsInstanceOf(function () {
+    var p = new ParallelArray([]);
+    p.reduce(function (v, p) { return v*p; });
+  }, Error);
+  // Throw on not function
+  assertThrowsInstanceOf(function () {
+    var p = new ParallelArray([1]);
+    p.reduce(42);
+  }, TypeError);
+}
+
+testReduceThrows();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scan-1.js
@@ -0,0 +1,13 @@
+
+function testScan() {
+  function f(v, p) { return v*p; }
+  var a = [1,2,3,4,5];
+  var p = new ParallelArray(a);
+  var s = p.scan(f);
+  for (var i = 0; i < p.length; i++) {
+    var p2 = new ParallelArray(a.slice(0, i+1));
+    assertEq(s[i], p2.reduce(f));
+  }
+}
+
+testScan();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scan-2.js
@@ -0,0 +1,9 @@
+
+function testScanOne() {
+  function f(v, p) { return v*p; }
+  var p = new ParallelArray([1]);
+  var s = p.scan(f);
+  assertEq(s[0], p.reduce(f));
+}
+
+testScanOne();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scan-3.js
@@ -0,0 +1,18 @@
+
+function testScan() {
+  // Test reduce on higher dimensional
+  // XXX Can we test this better?
+  function f(a, b) { return a; }
+  var shape = [2];
+  for (var i = 0; i < 7; i++) {
+    shape.push(i+1);
+    var p = new ParallelArray(shape, function () { return i+1; });
+    var r = p.reduce(f);
+    var s = p.scan(f)
+    for (var j = 0; j < s.length; j++)
+      assertEq(s[0].shape.length, i + 1);
+    assertEq(r.shape.length, i + 1);
+  }
+}
+
+testScan();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scan-fn-args.js
@@ -0,0 +1,13 @@
+
+function testScan() {
+  // Test reduce elemental fun args
+  var p = new ParallelArray([1,2,3,4]);
+  var r = p.reduce(function (a, b) {
+    assertEq(a >= 1 && a <= 4, true);
+    assertEq(b >= 1 && b <= 4, true);
+    return a;
+  });
+  assertEq(r >= 1 && r <= 4, true);
+}
+
+testScan();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scan-throws.js
@@ -0,0 +1,16 @@
+load(libdir + "asserts.js");
+
+function testScanThrows() {
+  // Throw on empty
+  assertThrowsInstanceOf(function () {
+    var p = new ParallelArray([]);
+    p.scan(function (v, p) { return v*p; });
+  }, Error);
+  // Throw on not function
+  assertThrowsInstanceOf(function () {
+    var p = new ParallelArray([1]);
+    p.scan(42);
+  }, TypeError);
+}
+
+testScanThrows();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-1.js
@@ -0,0 +1,8 @@
+
+function testScatter() {
+  var p = new ParallelArray([1,2,3,4,5]);
+  var r = p.scatter([0,1,0,3,4], 9, function (a,b) { return a+b; }, 10);
+  assertEq(r.length, 10);
+}
+
+testScatter();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-2.js
@@ -0,0 +1,9 @@
+
+function testScatterIdentity() {
+  var p = new ParallelArray([1,2,3,4,5]);
+  var r = p.scatter([0,1,2,3,4]);
+  assertEq(p.toString(), r.toString());
+}
+
+testScatterIdentity();
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-3.js
@@ -0,0 +1,10 @@
+
+function testScatter() {
+  var p = new ParallelArray([1,2,3,4,5]);
+  var r = p.scatter([1,0,3,2,4]);
+  var p2 = new ParallelArray([2,1,4,3,5]);
+  assertEq(r.toString(), p2.toString());
+}
+
+testScatter();
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-4.js
@@ -0,0 +1,12 @@
+function bracket(s) {
+  return "<" + s + ">";
+}
+
+function testScatterDefault() {
+  var p = new ParallelArray([1,2,3,4,5]);
+  var r = p.scatter([0,2,4], 9);
+  assertEq(r.toString(), bracket([1,9,2,9,3].join(",")));
+}
+
+testScatterDefault();
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-5.js
@@ -0,0 +1,11 @@
+function bracket(s) {
+  return "<" + s + ">";
+}
+
+function testScatterConflict() {
+    var p = new ParallelArray([1,2,3,4,5]);
+    var r = p.scatter([0,1,0,3,4], 9, function (a,b) { return a+b; });
+    assertEq(r.toString(), bracket([4,2,9,4,5].join(",")));
+}
+
+testScatterConflict();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-6.js
@@ -0,0 +1,13 @@
+
+function testScatter() {
+  // Test scatter on higher dimension
+  var shape = [5];
+  for (var i = 0; i < 7; i++) {
+    shape.push(i+1);
+    var p = new ParallelArray(shape, function(k) { return k; });
+    var r = p.scatter([0,1,0,3,4], 9, function (a,b) { return a+b; }, 10);
+    assertEq(r.length, 10);
+  }
+}
+
+testScatter();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-7.js
@@ -0,0 +1,13 @@
+
+function testScatterIdentity() {
+  var shape = [5];
+  for (var i = 0; i < 7; i++) {
+    shape.push(i+1);
+    var p = new ParallelArray(shape, function(k) { return k; });
+    var r = p.scatter([0,1,2,3,4]);
+    assertEq(p.toString(), r.toString());
+  }
+}
+
+testScatterIdentity();
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-8.js
@@ -0,0 +1,14 @@
+
+function testScatter() {
+  var shape = [5];
+  for (var i = 0; i < 7; i++) {
+    shape.push(i+1);
+    var p = new ParallelArray(shape, function(k) { return k; });
+    var r = p.scatter([1,0,3,2,4]);
+    var p2 = new ParallelArray([p[1], p[0], p[3], p[2], p[4]]);
+    assertEq(p2.toString(), r.toString());
+  }
+}
+
+testScatter();
+
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-9.js
@@ -0,0 +1,7 @@
+function testScatter() {
+  // Ignore the rest of the scatter vector if longer than source
+  var p = new ParallelArray([1,2,3,4,5]);
+  var r = p.scatter([1,0,3,2,4,1,2,3]);
+  var p2 = new ParallelArray([2,1,4,3,5]);
+  assertEq(r.toString(), p2.toString());
+}
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/scatter-throws.js
@@ -0,0 +1,16 @@
+load(libdir + "asserts.js");
+
+function testScatterThrows() {
+  // Throw on conflict with no resolution function
+  assertThrowsInstanceOf(function () {
+    var p = new ParallelArray([1,2,3,4,5]);
+    var r = p.scatter([0,1,0,3,4]);
+  }, Error);
+  // Throw on out of bounds
+  assertThrowsInstanceOf(function () {
+    var p = new ParallelArray([1,2,3,4,5]);
+    var r = p.scatter([0,1,0,3,11]);
+  }, Error);
+}
+
+testScatterThrows();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/shape-1.js
@@ -0,0 +1,8 @@
+function testShape() {
+  var a = [1,2,3];
+  var p = new ParallelArray(a);
+  assertEq(p.shape.length, 1);
+  assertEq(p.shape[0], a.length);
+}
+
+testShape();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/shape-2.js
@@ -0,0 +1,14 @@
+function testShape() {
+  // Test higher dimension shape up to 8D
+  var shape = [];
+  for (var i = 0; i < 8; i++) {
+    shape.push(i+1);
+    var p = new ParallelArray(shape, function () { return 0; });
+    // Test shape identity and shape
+    assertEq(p.shape, p.shape);
+    assertEq(p.shape !== shape, true);
+    assertEq(p.shape.toString(), shape.toString());
+  }
+}
+
+testShape();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/surfaces-1.js
@@ -0,0 +1,37 @@
+// ParallelArray surfaces
+
+var desc = Object.getOwnPropertyDescriptor(this, "ParallelArray");
+assertEq(desc.enumerable, false);
+assertEq(desc.configurable, true);
+assertEq(desc.writable, true);
+
+assertEq(typeof ParallelArray, 'function');
+assertEq(Object.keys(ParallelArray).length, 0);
+assertEq(ParallelArray.length, 0);
+assertEq(ParallelArray.name, "ParallelArray");
+
+assertEq(Object.getPrototypeOf(ParallelArray.prototype), Object.prototype);
+assertEq(Object.prototype.toString.call(ParallelArray.prototype), "[object ParallelArray]");
+assertEq(Object.prototype.toString.call(new ParallelArray), "[object ParallelArray]");
+assertEq(Object.prototype.toString.call(ParallelArray()), "[object ParallelArray]");
+assertEq(Object.keys(ParallelArray.prototype).join(), "");
+assertEq(ParallelArray.prototype.constructor, ParallelArray);
+
+function checkMethod(name, arity) { 
+    var desc = Object.getOwnPropertyDescriptor(ParallelArray.prototype, name);
+    assertEq(desc.enumerable, false);
+    assertEq(desc.configurable, true);
+    assertEq(desc.writable, true);
+    assertEq(typeof desc.value, 'function');
+    assertEq(desc.value.name, name);
+    assertEq(desc.value.length, arity);
+}
+
+checkMethod("map", 1);
+checkMethod("reduce", 1);
+checkMethod("scan", 1);
+checkMethod("scatter", 1);
+checkMethod("filter", 1);
+checkMethod("flatten", 0);
+checkMethod("partition", 1);
+checkMethod("get", 1);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/parallelarray/surfaces-2.js
@@ -0,0 +1,27 @@
+// ParallelArray methods throw when passed a this-value that isn't a ParallelArray.
+
+load(libdir + "asserts.js");
+
+function testcase(obj, fn) {
+    assertEq(typeof fn, "function");
+    var args = Array.slice(arguments, 2);
+    assertThrowsInstanceOf(function () { fn.apply(obj, args); }, TypeError);
+}
+
+function test(obj) {
+    function f() {}
+    testcase(obj, ParallelArray.prototype.map, f);
+    testcase(obj, ParallelArray.prototype.reduce, f);
+    testcase(obj, ParallelArray.prototype.scan, f);
+    testcase(obj, ParallelArray.prototype.scatter, [0]);
+    testcase(obj, ParallelArray.prototype.filter, [0]);
+    testcase(obj, ParallelArray.prototype.flatten);
+    testcase(obj, ParallelArray.prototype.partition, 2);
+    testcase(obj, ParallelArray.prototype.get, [1]);
+}
+
+test(ParallelArray.prototype);
+test(Object.create(new ParallelArray));
+test({});
+test(null);
+test(undefined);
--- a/js/src/js.msg
+++ b/js/src/js.msg
@@ -349,8 +349,15 @@ MSG_DEF(JSMSG_PARAMETER_AFTER_REST,   29
 MSG_DEF(JSMSG_NO_REST_NAME,           296, 0, JSEXN_SYNTAXERR, "no parameter name after ...")
 MSG_DEF(JSMSG_ARGUMENTS_AND_REST,     297, 0, JSEXN_SYNTAXERR, "'arguments' object may not be used in conjunction with a rest parameter")
 MSG_DEF(JSMSG_FUNCTION_ARGUMENTS_AND_REST, 298, 0, JSEXN_ERR, "the 'arguments' property of a function with a rest parameter may not be used")
 MSG_DEF(JSMSG_REST_WITH_DEFAULT,      299, 0, JSEXN_SYNTAXERR, "rest parameter may not have a default")
 MSG_DEF(JSMSG_NONDEFAULT_FORMAL_AFTER_DEFAULT, 300, 0, JSEXN_SYNTAXERR, "parameter(s) with default followed by parameter without default")
 MSG_DEF(JSMSG_YIELD_IN_DEFAULT,       301, 0, JSEXN_SYNTAXERR, "yield in default expression")
 MSG_DEF(JSMSG_INTRINSIC_NOT_DEFINED,  302, 1, JSEXN_REFERENCEERR, "no intrinsic function {0}")
 MSG_DEF(JSMSG_ALREADY_HAS_SOURCEMAP,  303, 1, JSEXN_ERR,      "{0} is being assigned a source map, yet already has one")
+MSG_DEF(JSMSG_PAR_ARRAY_IMMUTABLE,    304, 0, JSEXN_TYPEERR, "ParallelArray objects are immutable")
+MSG_DEF(JSMSG_PAR_ARRAY_BAD_ARG,      305, 1, JSEXN_TYPEERR, "invalid ParallelArray{0} argument")
+MSG_DEF(JSMSG_PAR_ARRAY_BAD_PARTITION, 306, 0, JSEXN_ERR, "argument must be divisible by outermost dimension")
+MSG_DEF(JSMSG_PAR_ARRAY_REDUCE_EMPTY, 307, 0, JSEXN_ERR, "cannot reduce empty ParallelArray object")
+MSG_DEF(JSMSG_PAR_ARRAY_ALREADY_FLAT, 308, 0, JSEXN_ERR, "cannot flatten 1-dimensional ParallelArray object")
+MSG_DEF(JSMSG_PAR_ARRAY_SCATTER_CONFLICT, 309, 0, JSEXN_ERR, "no conflict resolution function provided")
+MSG_DEF(JSMSG_PAR_ARRAY_SCATTER_BOUNDS, 310, 0, JSEXN_ERR, "index in scatter vector out of bounds")
--- a/js/src/jsapi.cpp
+++ b/js/src/jsapi.cpp
@@ -50,16 +50,17 @@
 #include "jsweakmap.h"
 #include "jswrapper.h"
 #include "jstypedarray.h"
 #include "jsxml.h"
 
 #include "builtin/Eval.h"
 #include "builtin/MapObject.h"
 #include "builtin/RegExp.h"
+#include "builtin/ParallelArray.h"
 #include "ds/LifoAlloc.h"
 #include "frontend/BytecodeCompiler.h"
 #include "frontend/TreeContext.h"
 #include "gc/Marking.h"
 #include "gc/Memory.h"
 #include "js/MemoryMetrics.h"
 #include "vm/NumericConversions.h"
 #include "vm/StringBuffer.h"
@@ -1862,16 +1863,17 @@ static JSStdName standard_class_atoms[] 
 #if JS_HAS_GENERATORS
     {js_InitIteratorClasses,            EAGER_ATOM_AND_CLASP(StopIteration)},
 #endif
     {js_InitJSONClass,                  EAGER_ATOM_AND_CLASP(JSON)},
     {js_InitTypedArrayClasses,          EAGER_CLASS_ATOM(ArrayBuffer), &js::ArrayBufferObject::protoClass},
     {js_InitWeakMapClass,               EAGER_CLASS_ATOM(WeakMap), &js::WeakMapClass},
     {js_InitMapClass,                   EAGER_CLASS_ATOM(Map), &js::MapObject::class_},
     {js_InitSetClass,                   EAGER_CLASS_ATOM(Set), &js::SetObject::class_},
+    {js_InitParallelArrayClass,         EAGER_CLASS_ATOM(ParallelArray), &js::ParallelArrayObject::class_},
     {NULL,                              0, NULL}
 };
 
 /*
  * Table of top-level function and constant names and their init functions.
  * If you add a "standard" global function or property, remember to update
  * this table.
  */
--- a/js/src/jsatom.tbl
+++ b/js/src/jsatom.tbl
@@ -117,16 +117,17 @@ DEFINE_ATOM(fix, "fix")
 DEFINE_ATOM(has, "has")
 DEFINE_ATOM(hasOwn, "hasOwn")
 DEFINE_ATOM(keys, "keys")
 DEFINE_ATOM(iterate, "iterate")
 DEFINE_PROTOTYPE_ATOM(WeakMap)
 DEFINE_ATOM(buffer, "buffer")
 DEFINE_ATOM(byteLength, "byteLength")
 DEFINE_ATOM(byteOffset, "byteOffset")
+DEFINE_ATOM(shape, "shape")
 DEFINE_KEYWORD_ATOM(return)
 DEFINE_KEYWORD_ATOM(throw)
 DEFINE_ATOM(url, "url")
 DEFINE_ATOM(innermost, "innermost")
 
 DEFINE_ATOM(XMLList, "XMLList")
 DEFINE_ATOM(decodeURI, "decodeURI")
 DEFINE_ATOM(decodeURIComponent, "decodeURIComponent")
--- a/js/src/jsproto.tbl
+++ b/js/src/jsproto.tbl
@@ -59,12 +59,13 @@ JS_PROTO(Float32Array,          31,     
 JS_PROTO(Float64Array,          32,     js_InitTypedArrayClasses)
 JS_PROTO(Uint8ClampedArray,     33,     js_InitTypedArrayClasses)
 JS_PROTO(Proxy,                 34,     js_InitProxyClass)
 JS_PROTO(AnyName,               35,     js_InitNullClass)
 JS_PROTO(WeakMap,               36,     js_InitWeakMapClass)
 JS_PROTO(Map,                   37,     js_InitMapClass)
 JS_PROTO(Set,                   38,     js_InitSetClass)
 JS_PROTO(DataView,              39,     js_InitTypedArrayClasses)
+JS_PROTO(ParallelArray,         40,     js_InitParallelArrayClass)
 
 #undef XML_INIT
 #undef NAMESPACE_INIT
 #undef QNAME_INIT