Open briancavalier opened 9 years ago
When the conditions are right, the difference can be almost comical: This gist shows a candidate implemetations (quite simple!), plus the an example to reduce a 10k element array, with an add()
function that delays for 1 millisecond. Parallel takes 74 milliseconds, while linear takes 13 seconds O.o
UPDATE: simplified the reducePar impl in the gist.
It wouldn't be too hard to add a parallel associative reduce. It would have an advantage over left-to-right and right-to-left reducing in the case where the combine function itself is async.
So, for example, left-to-right reduce looks like the following:
Imagine that
add
is an asynchronous operation, perhaps sending the inputs off to some remote "add service". In the left-to-right case, each add must wait for the previous add to complete in order to have access to both parameters so that it can send them to the "add service".A parallel, associative reduce would look more like (remember,
add
is async):In this case, intermediate results
r0
andr1
can be computed in parallel, and then once both are available, can be combined to compute the finalresult
. IOW, it reduces as a tree:rather than linear:
Advantages
Assuming
add
takes 100ms, then in the very simple example above, left-to-right reduce would take 300ms, whereas parallel would take 200ms. The time to compute left-to-right is O(n), and parallel associative is O(log n).The advantage can be significant as n grows even a little. For instance, if the example above had 32 elements instead of 3, linear would take 3.2 seconds vs 500 milliseconds for parallel.
Possible downsides
The combine function must be associative. For example, you can't substitute subtraction into the example above. You could, however, substitute multiplication and string concatenation, for example.
AFAIK, when the combine function is synchronous there is no advantage over linear reduce. A good implementation should perform no worse, but it would still impose the associativity restriction.
Questions
when.reduce
only to await promises in the input array?