avoiding excessive memory operations

[Norm Rubin]

I've noticed that a common pattern of usage is a map to compute an intermediate transform on each input, followed by a reduce to combine the transformed values. An example would be
P1 = p.map ((x,i)->[x,i])
Scalar = p1.reduce ( ...)

It appears to me that a jit that tries to avoid actually generating the intermediate is going to have to work quite hard.

While one could suggest that the developer could have written
p.map().reduce(...)
There is some chance that the same transformation is actually useful in other places, so it would be nice to be able to name the intermediate result.


I'd like to suggest an alternative idea that I think is simpler to process

Suppose we have a method on a parallel array called a view
v1 = p.view(x,i)->[x,i])

A view gets a function, as an argument. The ideas is the function is saved and is applied later when the view is used
So
Given a view v1 of a ParallelArray
v1.reduce ( function(x,y) ....) works like this
a simple jit just evaluates the view building a new parallel array and then calls reduce,
while a more optimizing jit changes the reduce function to
function(x_,y_) { x = view.fn(x); y = view.fn(y_) ...)
and where an aggressively optimizing jit could avoid recalculating the view.fn on elements more than once.
It could for instance strip mine. That is it could generate code that applies the view.fn to the first n elements of the ParallelArray, applies the reduce function to those elements and then goes on to do the next batch

Any opinions?







-----------------------------------------------------------------------------------
This email message is for the sole use of the intended recipient(s) and may contain
confidential information. Any unauthorized review, use, disclosure or distribution
is prohibited. If you are not the intended recipient, please contact the sender by
reply email and destroy all copies of the original message.
-----------------------------------------------------------------------------------

[Herhut, Stephan A]

We discussed different forms of lazy (or by-need) evaluation of ParallelArray methods, including the idea to fold different operations to avoid materializing intermediate results. The simplest form

A.map(f).reduce(g)

seems quite doable but as soon as one allows any code between the invocations of map and reduce, the closure of the deferred map needs to be monitored for changes or captured. Of course, if f is closed, i.e. does not reference any non-local state, one can do without this requirement but are those an interesting set of functions?

Another issue are side effects. Right now, we allow side effects in the elemental functions but do not execute them in parallel in such case. This is motivated by the high cost of tracking side effects during sequential execution (see the series of posts on Niko's blog for a discussion http://smallcultfollowing.com/babysteps/blog/categories/pjs/ ). Reducing that cost is probably more of an engineering problem than a conceptual issue but engineering cost is an important metric, too. Now, if we would defer computations or even combine them, side effects of elemental functions might appear later or even multiple times, depending on the runtime or browser.

I believe view suffers from these problems, too.

Stephan

>_______________________________________________
>dev-tech-js-engine-rivertrail mailing list dev-tech-js-engine-
>river...@lists.mozilla.org
>https://lists.mozilla.org/listinfo/dev-tech-js-engine-rivertrail

[Hudson, Rick]

There is also an issue with throwing exceptions between the view and the reduce so just monitoring for writes isn't enough.

- Rick

_______________________________________________
dev-tech-js-engine-rivertrail mailing list dev-tech-js-en...@lists.mozilla.org
https://lists.mozilla.org/listinfo/dev-tech-js-engine-rivertrail

[Niko Matsakis]

We've discussed this idea (of lazilly evaluating maps and so forth)
from time to time. I like the idea of making it explicit, to be sure,
since otherwise there are great difficulties in dealing with
exceptions and so forth. Clojure offers a similar abstraction
(reducers [1]) and seems to derive great utility from it. We might do
well to emulate their approach.

However, I wonder if a `mapreduce` method isn't a more straightforward
way to address this use case---the question I guess is whether it is
common to chain together transformations in arbitrary and complex
patterns, or whether a small number would suffice.


Niko

[1] http://clojure.com/blog/2012/05/08/reducers-a-library-and-model-for-collection-processing.html

[Vinod Grover]

Some of this notion of views sounds similar to delayed arrays in Repa
[1]. In this model you don't necessarily compute an intermediate array but
return a function to compute the elements of intermediate values. Not sure
how that fits into JS, but I thought I'd mention it here.




[1]
http://hackage.haskell.org/packages/archive/repa/3.2.3.2/doc/html/Data-Array-Repa-Repr-Delayed.html

[Norm Rubin]

I think a combined map-reduce is one possible option but these same lazy ops also fit with the other operations.
Map-and-scan? Map-and-scatter? Even map-and map?

One case for map-map might be computing dot-products of lots of 3d vectors
Where to improve performance we store the vectors as a struct of arrays
A is stored as three parallelArrays, the first holds x components, the second y components and the last holds the z components
B is stored in the same way

Laying out the data this way helps performance (gpu gets good memory coalescing, cpu gets to use sse) provided we never actually build the intermediates.

The dot product of each A with the corresponding B
Could be done by setting up views that access the 3 vectors for A/B ( zip the 3 vectors together into a single 3-tuple)
And then mapping the views of tuples into parallel dot-products


A related question concerns lazy reductions,
Given
S1 = pa.reduce(f1)
S2 = pa.reduce(f2)
Two separate reductions on the same parallel array, like find the max, and find the min
Can we make build a jit that wants to magically fuse the two functions so it only needs to read pa once?

From: Vinod Grover [mailto:vinod....@gmail.com]
Sent: Wednesday, May 08, 2013 9:59 PM
To: Niko Matsakis
Cc: Norm Rubin; dev-tech-js-en...@lists.mozilla.org
Subject: Re: avoiding excessive memory operations

Some of this notion of views sounds similar to delayed arrays in Repa [1]. In this model you don't necessarily compute an intermediate array but return a function to compute the elements of intermediate values. Not sure how that fits into JS, but I thought I'd mention it here.




[1] http://hackage.haskell.org/packages/archive/repa/3.2.3.2/doc/html/Data-Array-Repa-Repr-Delayed.html

> dev-tech-js-en...@lists.mozilla.org<mailto:dev-tech-js-en...@lists.mozilla.org>

> https://lists.mozilla.org/listinfo/dev-tech-js-engine-rivertrail
_______________________________________________
dev-tech-js-engine-rivertrail mailing list

dev-tech-js-en...@lists.mozilla.org<mailto:dev-tech-js-en...@lists.mozilla.org>
https://lists.mozilla.org/listinfo/dev-tech-js-engine-rivertrail

[Niko Matsakis]

On Wed, May 08, 2013 at 11:50:16PM +0000, Herhut, Stephan A wrote:
> Reducing that cost is probably more of an engineering problem than a
> conceptual issue but engineering cost is an important metric,
> too. Now, if we would defer computations or even combine them, side
> effects of elemental functions might appear later or even multiple
> times, depending on the runtime or browser.

To me this is the biggest issue. It is largely an engineering issue,
yes, though there is also the question of finding a way to define
precisely what is 'side-effecting' and what is not.

> I believe view suffers from these problems, too.

I had presumed that `view` would be explicit about the possible
interleaving of execution order. In other words, it would say that
individual map iterations will occur lazilly as the view is accessed,
and not together as an atomic unit. That's certainly one of the
dangers of the idea: more undefined behavior.


Niko

[Hudson, Rick]

Futures and non-strict functionality are really JavaScript proper issues and not an issue relevant only to Parallel JavaScript. In any case we should be very careful to avoid non-determinism even if it costs us performance.

The important issue of what side effect free means needs to be uniform across the different forms of parallelism that are being envisioned including data parallelism (our focus), wavefront parallelism, Niko's thread parallelism, and distributed promises, aka distributed futures. All will benefit from a uniform definition of side effect free functionality.

- Rick

-----Original Message-----
From: dev-tech-js-engine-rivertrail-bounces+rick.hudson=inte...@lists.mozilla.org [mailto:dev-tech-js-engine-rivertrail-bounces+rick.hudson=inte...@lists.mozilla.org] On Behalf Of Niko Matsakis
Sent: Thursday, May 09, 2013 6:09 AM
To: Herhut, Stephan A
Cc: Norm Rubin; dev-tech-js-en...@lists.mozilla.org
Subject: Re: avoiding excessive memory operations

_______________________________________________
dev-tech-js-engine-rivertrail mailing list dev-tech-js-en...@lists.mozilla.org

https://lists.mozilla.org/listinfo/dev-tech-js-engine-rivertrail