Mixing
How does newly introduced Arrays.parallelPrefix(…) in JAVA-8 work
Clash Royale CLAN TAG#URR8PPP
up vote
8
down vote
favorite
I came across Arrays.parallelPrefix introduced in JAVA-8.
This overloaded method performs operation on each element of the input array in a cumulative fashion. For e.g. from docs:
Cumulates, in parallel, each element of the given array in place,
using the supplied function. For example if the array initially holds
[2, 1, 0, 3] and the operation performs addition, then upon return the
array holds [2, 3, 3, 6]. Parallel prefix computation is usually more
efficient than sequential loops for large arrays.
So, how does JAVA achieve this task in parallel when the operation on a term is dependent on the operation result on the previous term, and so on?
I tried going through the code myself and they do use ForkJoinTasks, but it's not so straightforward how they would merge result to get the final array.
java arrays java-8
edited 1 hour ago
Eran
268k35415501
asked 2 hours ago
Aditya Gupta
136210
add a comment |Â
up vote
8
down vote
favorite
I came across Arrays.parallelPrefix introduced in JAVA-8.
This overloaded method performs operation on each element of the input array in a cumulative fashion. For e.g. from docs:
Cumulates, in parallel, each element of the given array in place,
using the supplied function. For example if the array initially holds
[2, 1, 0, 3] and the operation performs addition, then upon return the
array holds [2, 3, 3, 6]. Parallel prefix computation is usually more
efficient than sequential loops for large arrays.
So, how does JAVA achieve this task in parallel when the operation on a term is dependent on the operation result on the previous term, and so on?
I tried going through the code myself and they do use ForkJoinTasks, but it's not so straightforward how they would merge result to get the final array.
java arrays java-8
edited 1 hour ago
Eran
268k35415501
asked 2 hours ago
Aditya Gupta
136210
2
Nice question. +1 .. Parallel prefix computation is usually more efficient than sequential loops for large arrays ... every day there is a lot more for me here to learn and I love it.
– nullpointer
2 hours ago
add a comment |Â
up vote
8
down vote
favorite
up vote
8
down vote
favorite
I came across Arrays.parallelPrefix introduced in JAVA-8.
This overloaded method performs operation on each element of the input array in a cumulative fashion. For e.g. from docs:
Cumulates, in parallel, each element of the given array in place,
using the supplied function. For example if the array initially holds
[2, 1, 0, 3] and the operation performs addition, then upon return the
array holds [2, 3, 3, 6]. Parallel prefix computation is usually more
efficient than sequential loops for large arrays.
So, how does JAVA achieve this task in parallel when the operation on a term is dependent on the operation result on the previous term, and so on?
I tried going through the code myself and they do use ForkJoinTasks, but it's not so straightforward how they would merge result to get the final array.
java arrays java-8
edited 1 hour ago
Eran
268k35415501
asked 2 hours ago
Aditya Gupta
136210
I came across Arrays.parallelPrefix introduced in JAVA-8.
This overloaded method performs operation on each element of the input array in a cumulative fashion. For e.g. from docs:
Cumulates, in parallel, each element of the given array in place,
using the supplied function. For example if the array initially holds
[2, 1, 0, 3] and the operation performs addition, then upon return the
array holds [2, 3, 3, 6]. Parallel prefix computation is usually more
efficient than sequential loops for large arrays.
So, how does JAVA achieve this task in parallel when the operation on a term is dependent on the operation result on the previous term, and so on?
I tried going through the code myself and they do use ForkJoinTasks, but it's not so straightforward how they would merge result to get the final array.
java arrays java-8
java arrays java-8
edited 1 hour ago
Eran
268k35415501
asked 2 hours ago
Aditya Gupta
136210
edited 1 hour ago
Eran
268k35415501
asked 2 hours ago
Aditya Gupta
136210
edited 1 hour ago
Eran
268k35415501
edited 1 hour ago
Eran
268k35415501
edited 1 hour ago
Eran
268k35415501
268k35415501
asked 2 hours ago
Aditya Gupta
136210
asked 2 hours ago
Aditya Gupta
136210
asked 2 hours ago
Aditya Gupta
136210
136210
2
Nice question. +1 .. Parallel prefix computation is usually more efficient than sequential loops for large arrays ... every day there is a lot more for me here to learn and I love it.
– nullpointer
2 hours ago
add a comment |Â
2
Nice question. +1 .. Parallel prefix computation is usually more efficient than sequential loops for large arrays ... every day there is a lot more for me here to learn and I love it.
– nullpointer
2 hours ago
2
2
Nice question. +1 .. Parallel prefix computation is usually more efficient than sequential loops for large arrays ... every day there is a lot more for me here to learn and I love it.
– nullpointer
2 hours ago
Nice question. +1 .. Parallel prefix computation is usually more efficient than sequential loops for large arrays ... every day there is a lot more for me here to learn and I love it.
– nullpointer
2 hours ago
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
8
down vote
The main point is that the operator is a
side-effect-free, associative function
This means that
(a op b) op c == a op (b op c)
Therefore, if you split the array into two halves and apply the parallelPrefix method recursively on each half, you can later merge the partial results by applying the operation on each element of the second half of the array with the last element of the first half.
Consider the [2, 1, 0, 3] with addition example. If you split the array into two halves and perform the operation on each half, you get:
[2, 3] and [0, 3]
Then, in order to merge them, you add 3 (the last element of the first half) to each element of the second half, and get:
[2, 3, 3, 6]
answered 2 hours ago
Eran
268k35415501
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
8
down vote
The main point is that the operator is a
side-effect-free, associative function
This means that
(a op b) op c == a op (b op c)
Therefore, if you split the array into two halves and apply the parallelPrefix method recursively on each half, you can later merge the partial results by applying the operation on each element of the second half of the array with the last element of the first half.
Consider the [2, 1, 0, 3] with addition example. If you split the array into two halves and perform the operation on each half, you get:
[2, 3] and [0, 3]
Then, in order to merge them, you add 3 (the last element of the first half) to each element of the second half, and get:
[2, 3, 3, 6]
answered 2 hours ago
Eran
268k35415501
add a comment |Â
up vote
8
down vote
The main point is that the operator is a
side-effect-free, associative function
This means that
(a op b) op c == a op (b op c)
Therefore, if you split the array into two halves and apply the parallelPrefix method recursively on each half, you can later merge the partial results by applying the operation on each element of the second half of the array with the last element of the first half.
Consider the [2, 1, 0, 3] with addition example. If you split the array into two halves and perform the operation on each half, you get:
[2, 3] and [0, 3]
Then, in order to merge them, you add 3 (the last element of the first half) to each element of the second half, and get:
[2, 3, 3, 6]
answered 2 hours ago
Eran
268k35415501
add a comment |Â
up vote
8
down vote
up vote
8
down vote
The main point is that the operator is a
side-effect-free, associative function
This means that
(a op b) op c == a op (b op c)
Therefore, if you split the array into two halves and apply the parallelPrefix method recursively on each half, you can later merge the partial results by applying the operation on each element of the second half of the array with the last element of the first half.
Consider the [2, 1, 0, 3] with addition example. If you split the array into two halves and perform the operation on each half, you get:
[2, 3] and [0, 3]
Then, in order to merge them, you add 3 (the last element of the first half) to each element of the second half, and get:
[2, 3, 3, 6]
answered 2 hours ago
Eran
268k35415501
The main point is that the operator is a
side-effect-free, associative function
This means that
(a op b) op c == a op (b op c)
Therefore, if you split the array into two halves and apply the parallelPrefix method recursively on each half, you can later merge the partial results by applying the operation on each element of the second half of the array with the last element of the first half.
Consider the [2, 1, 0, 3] with addition example. If you split the array into two halves and perform the operation on each half, you get:
[2, 3] and [0, 3]
Then, in order to merge them, you add 3 (the last element of the first half) to each element of the second half, and get:
[2, 3, 3, 6]
answered 2 hours ago
Eran
268k35415501
edited 2 hours ago
answered 2 hours ago
Eran
268k35415501
answered 2 hours ago
Eran
268k35415501
answered 2 hours ago
Eran
268k35415501
268k35415501
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f52961981%2fhow-does-newly-introduced-arrays-parallelprefix-in-java-8-work%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
2
Nice question. +1 .. Parallel prefix computation is usually more efficient than sequential loops for large arrays ... every day there is a lot more for me here to learn and I love it.
– nullpointer
2 hours ago