Closed Bug 862904 Opened 10 years ago Closed 8 years ago

Add out pointer to the parallel array API


(Core :: JavaScript Engine, defect)

22 Branch
Not set





(Reporter: nmatsakis, Assigned: shu)



(Whiteboard: PJS)

When constructing a multi-dimensional matrix, it is sometimes necessary to compute submatrices (for example, a row) sequentially. The current API requires that the row which was computed sequentially be returned and then copied into its final home. This results in unnecessary performance overhead, which will only become more visible once Bug 862897 lands. 

We briefly entertained the idea of eliminating this overhead via heroic compiler optimizations, and those may still be something that is worthwhile, just as a convenience. However, for the moment, the plan is to add an optional write-only out pointer to the callback. This object will offer a `set()` method that can be used to generate the result.

In other words, before you might have written:

     new Matrix([100], Array(100, Uint8), function(i) {
        var result = [];
        for (var j = 0; j < 100; j++) result[j] = ...;
        return result;

and that would still be legal, but a more efficient alternative would be:

     new Matrix([100], Array(100, Uint8), function(i, out) {
        for (var j = 0; j < 100; j++) out.set(j, ...);
The intention, by the way, is to offer these parameters uniformly on all parallel methods, including those offered on arrays etc, though they are less crucial in those cases.
Blocks: PJS
Depends on: 862897
Whiteboard: PJS
Assignee: general → shu
(Actually, it may be that we do not offer out pointers on the parallel methods of normal JS arrays, since they are pretty pointless there.  I just thought it'd be a good idea for reasons of uniformity.)
Further details:

    out.set(i0, ..., iN, v)

where i0...iN are the indices within the output grain.  If the output grain is not an array, you would not actually take any indices.
Some examples:

     new Matrix([100], Array(100, Array(100, Uint8)), function(i, out) {

        // OR

        for (var j = 0; j < 100; j++) out.set(j, v1);
        // OR

        for (var j = 0; j < 100; j++) 
            for (var k = 0; k < 100; k++)
                out.set(j, k, v2);

Here v0 must have type 100*100*uint8, v1 must have type 100*uint8, and v2 must have type uint8.
Some open questions:

- Should the out-pointer be read-write?  
  - This would be advantageous for many reasons:
    - supporting sequential reprocessing
    - out-pointer can share the binary data APIs
  - There are some implications:
    - Initialization is necessary, though it probably is anyhow.
    - Have to be careful around data races. Our current write guards are a bit
      dumb, but it's not a problem since we don't support nested parallelism yet.

The danger cases for races are two.  First, we should offer a divide-like method that slices up the out pointer and produces parallel work that targets a subrange. During such a method, reading from out (and not the subview) is illegal:, function(..., out) {
        out.divide(function (subview) { ... /* read from out is illegal */ });

The other danger is that we enter a parallel scheme through some other means, and then we must be sure to make it illegal to write to out:, function(..., out) {
        new ParallelArray(1024, function(i) {
            out.set(...); /* illegal! */
Should we support "braces" notation?  e.g., out[j] = k? Obviously it's nicer.  It can be inefficient for `out[j][k] = v`.  Adopting the binary data APIs addresses this since they also offer two alternatives.
Closed: 8 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.