862904 - Add out pointer to the parallel array API

Status: RESOLVED WONTFIX

(Core :: JavaScript Engine, defect)

Description

[Niko Matsakis [:nmatsakis]]

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, ...);
     })

Comment 1

[Niko Matsakis [:nmatsakis]]

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.

Comment 2

[Niko Matsakis [:nmatsakis]]

(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.)

Comment 3

[Niko Matsakis [:nmatsakis]]

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.

Comment 4

[Niko Matsakis [:nmatsakis]]

Some examples:

     new Matrix([100], Array(100, Array(100, Uint8)), function(i, out) {
        out.set(v0);

        // 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.

Comment 5

[Niko Matsakis [:nmatsakis]]

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:

    foo.map(..., 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:

    foo.map(..., function(..., out) {
        new ParallelArray(1024, function(i) {
            out.set(...); /* illegal! */
        });
    });

Comment 6

[Niko Matsakis [:nmatsakis]]

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.