River Trail vs. Smalltalk

In the context of Open Parallel’s project Parallel Cobol  Gaston Hillar -Open Parallel contributor commented:

“Have you seen what Intel did with River Trail? Something similar applied to Cobol + asynchronous methods for I/O can have an enormous potential”

That triggered Richard O’Keefe‘s interest and he came back with this:

River Trail appears to be just “add parallel arrays to Javascript”. (Ken Iverson must be rolling in his grave.  People keep reinventing *parts* of APL.)

In fact River Trail looks to me to be rather clumsy to use compared with the parallel collections in my Smalltalk.
More precisely, more things are _possible_ in River Trail, but fewer things are _easy_.  They don’t seem to have learned the APL “index-free programming is easier” lesson.

River Trail takes the ‘safety-is-the-programmer’s-responsibility, MUG!’ approach.  Consider

var s = 0;
var a = some_parallel_array.map(function (x) { return s += x; });

This appears to be allowed.  Hello undefined result!  (Assuming atomic updates.)  Hello data race!  (Assuming non-atomic updates.)
I noticed this issue because my Smalltalk parallel collections have precisely the same design flaw.

This shows a general problem with parallelism-by-library. If the compiler doesn’t know what’s going on, it cannot help you.

River Trail                    My Smalltalk library

pa.map(f)                     a par collect: f
pa.combine(f)             a par keysCollect: f
pa.reduce(f)                 a par inject: initial into: f
pa.scan(f)                    a par inject: initial prefixesCollect: f
pa.filter(f)                    a par keysSelect: f
pa.flatten()                  not applicable
pa.partition(size)      not applicable
pa.get(indices)           a at: index
pa.scatter(i,d,c,l)      missing
missing                       a par {all,any,one}Satisfies: f

There are two principal differences.

(1) My library deals only with 1D sequences.
If it’s ever extended to 2D/3D arrays, it will _not_ work with vectors of indices, which must put a lot of pressure on the garbage collector.  How can you do anything fast if you
have to allocate a new array for each element of the collection you are working with?

pa.filter() is very strange.  It is really unclear to me what is supposed to happen if you filter a multidimensional array.

(2) Following Smalltalk tradition, I have

keysAndValuesCollect:       pass index and element
keysCollect                             pass index only
collect:                                     pass element only
keysAndValuesSelect:         pass index and element
keysSelect:                              pass index only
select:                                       pass element only
River Trail’s filter only passes an index, not an element.

There are some obvious gaps in River Trail.
There’s scatter, but not gather, for example.

There’s an interesting comment in one of the pages:
Pretty much any ParallelArray that does not hold a typed array or that cannot be turned into a typed array is unlikely to be optimized.  So far we have not seen meaningful use cases where this is a significant restriction.

Looking at the constructors of ParallelArray, we see a rather confusing, and I’d say error-prone, zoo.  Since it is important to have a typed array inside a ParallelArray, you’d think the
constructors would make it very easy to accomplish this.
At a guess,
ParallelArray(anArray)                             should preserve the type of anArray
ParallelArray(canvas)                               should use a typed array
ParallelArray(constructor, anArray)     Argument 0 is a function and there is one more argument:  Construct a new parallel array as above but use the first argument as constructor for the internal data container.  This form can be used to force the ParallelArray to hold its data as a typed array.

Typed arrays are fairly new in JavaScript.  There is precedent for having typed arrays in a dynamic language: Pop-2, Common Lisp, there’s a Scheme SRFI, Smalltalk-80, …  The Javascript ones are, needless to say, weirder.  A Javascript array is a typed slice of an untyped byte buffer.  The types are
{Int8,Uint8,Uint8Clamped,Int16,Uint16,Int32,Uint32}Array
Float{32,64}Array
So if you want say a 16 bit int array,

var ia = ParallelArray(Int16Array, << 3, 1, 4, 1, 5, 9 >>);

Now comes the interesting bit.

var qa = ia.map(function (x) { return x+1; });

Apparently this call can be optimised, because there is a typed array underneath.  But what about qa?  Since the function could return _anything_, it’s hard to see how it could have a typed array inside.  Even if you do it in two steps: first collect the results, then see what you got and pack appropriately,

var za = ia.map(function (x) { return 0; });

you have a choice of 7 ‘integer’ arrays this could be.  So it looks very much as though the “optimisability” of River Trail ParallelArrays evaporates rather quickly.

Of course they could fix the interface:

pa.map(<constructor>, <function> …)

would let you specify the kind of result you want (oddly enough, the Common Lisp MAP function has just such an interface).

Right now, it looks as though you’d have to write

ParallelArray(Int16Array, ia.map(function (x) { return 0; }))

But the documentation really does not make that clear.

——————

Advertisements