Re: Better RecursiveTask Example
"Dr Heinz M. Kabutz via Concurrency-interest" <[email protected]> Thu, 25 Nov 2021 07:38:22 +0200
| Newsgroups | gmane.comp.java.jsr.166-concurrency |
|---|---|
| Organization | JavaSpecialists.eu |
| Message-ID | <[email protected]> |
--===============4486210737613708176==
Content-Type: text/html; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 8bit
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
</head>
<body>
<p>Hi Alex,</p>
<p>my second example was a recursive logarithmic complexity
Fibonacci. However, I do think that the logarithmic Fibonacci
demos are too complicated for most readers to follow. But
Factorial most people know.</p>
<p>The parallel performance of the Factorial is limited by the final
large numbers that need to be multiplied together, and this is
(currently) happening in parallel. I've got a PR in the works to
add parallelMultiply() to BigInteger:
<a class="moz-txt-link-freetext" href="https://github.com/openjdk/jdk/pull/6409">https://github.com/openjdk/jdk/pull/6409</a><br>
</p>
<pre class="moz-signature" cols="72">Regards
Heinz
--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java™ Specialists' Newsletter" - <a class="moz-txt-link-abbreviated" href="http://www.javaspecialists.eu">www.javaspecialists.eu</a>
Java Champion - <a class="moz-txt-link-abbreviated" href="http://www.javachampions.org">www.javachampions.org</a>
JavaOne Rock Star Speaker
Tel: +30 69 75 595 262
Skype: kabutz
</pre>
<div class="moz-cite-prefix">On 2021/11/25 01:30, Alex Otenko wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CANkgWKjPCmJV5oeUhX9ZOSGqdD9M9Ai3WGfLm==e=Nn-E-J29g@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="auto">I presume logarithmic cost Fibonacci is not
considered, because there's little point doing it recursively?
(Although can still show off parallel computations)
<div dir="auto"><br>
</div>
<div dir="auto"><a href="https://bit.ly/3oVFeTD"
moz-do-not-send="true">https://bit.ly/3oVFeTD</a></div>
<div dir="auto"><br>
</div>
<div dir="auto"><br>
</div>
<div dir="auto">Alex</div>
</div>
<br>
<div class="gmail_quote">
<div dir="ltr" class="gmail_attr">On Wed, 24 Nov 2021, 19:19 Dr
Heinz M. Kabutz via Concurrency-interest, <<a
href="mailto:[email protected]"
moz-do-not-send="true">[email protected]</a>>
wrote:<br>
</div>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">Every time I
see the example in RecursiveTask I have to cringe:<br>
<br>
<a
href="https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/RecursiveTask.html"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true">https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/RecursiveTask.html</a><br>
<br>
For a classic example, here is a task computing Fibonacci
numbers:<br>
<br>
<br>
class Fibonacci extends RecursiveTask<Integer> {<br>
final int n;<br>
Fibonacci(int n) { this.n = n; }<br>
protected Integer compute() {<br>
if (n <= 1)<br>
return n;<br>
Fibonacci f1 = new Fibonacci(n - 1);<br>
f1.fork();<br>
Fibonacci f2 = new Fibonacci(n - 2);<br>
return f2.compute() + f1.join();<br>
}<br>
}<br>
However, besides being a dumb way to compute Fibonacci
functions (there <br>
is a simple fast linear algorithm that you'd use in practice),
this is <br>
likely to perform poorly because the smallest subtasks are too
small to <br>
be worthwhile splitting up. Instead, as is the case for nearly
all <br>
fork/join applications, you'd pick some minimum granularity
size (for <br>
example 10 here) for which you always sequentially solve
rather than <br>
subdividing.<br>
<br>
<br>
<br>
Indeed, it is a dumb way to compute Fibonacci, but the "fast
linear" <br>
algorithm isn't fast either. Since we overflow even Long after
about <br>
fibonacci(90), we would need BigInteger. And there the add is
linear, <br>
meaning that the "fast linear" algorithm referred to here is
probably <br>
going to end up as "slow quadratic".<br>
<br>
To me, this example sends the completely wrong message. Let's
take the <br>
worst possible algorithm and parallelize it. Great. That means
if we use <br>
1000 processors, we can solve the problem of n+10 in the same
time as n <br>
with a single processor.<br>
<br>
I do realize this is meant to illustrate a point, but it
doesn't do it <br>
very well IME. I would like to propose to change this to a
slightly <br>
better example, for example a Factorial calculation:<br>
<br>
public class FactorialTask extends
RecursiveTask<BigInteger> {<br>
private final int from, to;<br>
<br>
public FactorialTask(int n) {<br>
this(0, n);<br>
}<br>
<br>
private FactorialTask(int from, int to) {<br>
this.from = from;<br>
<a href="http://this.to" rel="noreferrer noreferrer"
target="_blank" moz-do-not-send="true">this.to</a> = to;<br>
}<br>
<br>
protected BigInteger compute() {<br>
if (from == to) {<br>
if (from == 0) return BigInteger.ONE;<br>
return BigInteger.valueOf(from);<br>
}<br>
int mid = (from + to) >>> 1;<br>
FactorialTask leftTask = new FactorialTask(from,
mid);<br>
FactorialTask rightTask = new FactorialTask(mid + 1,
to);<br>
leftTask.fork();<br>
BigInteger right = rightTask.invoke();<br>
BigInteger left = leftTask.join();<br>
return left.multiply(right);<br>
}<br>
}<br>
<br>
This is actually a *lot* faster than the stream version:<br>
<br>
public static BigInteger factorialStream(int n) {<br>
return IntStream.rangeClosed(1, n)<br>
.mapToObj(BigInteger::valueOf)<br>
.reduce(BigInteger.ONE,
BigInteger::multiply);<br>
}<br>
<br>
(this has to do more with the algorithms used by BigInteger's
multiply <br>
method than the parallelization, but that also has an effect.<br>
<br>
<br>
Alternatively, if we have to have Fibonacci, could we at least
change it <br>
to Dijkstra's Sum of Squares? I believe there are slightly
better <br>
algorithms, but this one works very nicely with
parallelisation:<br>
<br>
public class FibonacciTask extends
RecursiveTask<BigInteger> {<br>
private final int n;<br>
<br>
public FibonacciTask(int n) {<br>
this.n = n;<br>
}<br>
<br>
@Override<br>
protected BigInteger compute() {<br>
return switch (n) {<br>
case 0 -> BigInteger.ZERO;<br>
case 1 -> BigInteger.ONE;<br>
default -> {<br>
// Dijkstra's Sum of Squares Algorithm<br>
int half = (n + 1) / 2;<br>
FibonacciTask f0_task = new
FibonacciTask(half - 1);<br>
f0_task.fork();<br>
FibonacciTask f1_task = new
FibonacciTask(half);<br>
BigInteger f1 = f1_task.invoke();<br>
BigInteger f0 = f0_task.join();<br>
<br>
if (n % 2 == 1) {<br>
yield
f0.multiply(f0).add(f1.multiply(f1));<br>
} else {<br>
yield
f0.shiftLeft(1).add(f1).multiply(f1);<br>
}<br>
}<br>
};<br>
}<br>
}<br>
<br>
Please let me know if you agree with this change (or propose a
different <br>
example). I would be happy to make the change. I presume it
would need <br>
to be done in the CVS? Or can I do it in the OpenJDK GitHub
repository <br>
and then we can sync that over to CVS? (My preference would be
GitHub)<br>
<br>
<br>
<br>
<br>
Regards<br>
<br>
Heinz<br>
-- <br>
Dr Heinz M. Kabutz (PhD CompSci)<br>
Author of "The Java™ Specialists' Newsletter" - <a
href="http://www.javaspecialists.eu" rel="noreferrer
noreferrer" target="_blank" moz-do-not-send="true">www.javaspecialists.eu</a><br>
Java Champion - <a href="http://www.javachampions.org"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true">www.javachampions.org</a><br>
JavaOne Rock Star Speaker<br>
Tel: +30 69 75 595 262<br>
Skype: kabutz<br>
<br>
_______________________________________________<br>
Concurrency-interest mailing list<br>
<a href="mailto:[email protected]"
target="_blank" rel="noreferrer" moz-do-not-send="true">[email protected]</a><br>
<a
href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><br>
</blockquote>
</div>
</blockquote>
</body>
</html>
--===============4486210737613708176==
Content-Type: text/plain; charset="us-ascii"
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Disposition: inline
_______________________________________________
Concurrency-interest mailing list
[email protected]
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
--===============4486210737613708176==--