Re: Better RecursiveTask Example
"Dr Heinz M. Kabutz via Concurrency-interest" <[email protected]> Thu, 25 Nov 2021 13:00:37 +0200
| Newsgroups | gmane.comp.java.jsr.166-concurrency |
|---|---|
| Organization | JavaSpecialists.eu |
| Message-ID | <[email protected]> |
--===============2806443294668406539==
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>With my current simple algorithm, the magnitude of the two halves
are similar. Whilst your algorithm is better in terms of keeping
the two halves of closer size, it also complicates the demo
program too much in my opinion. Your point should perhaps be added
as a comment? A bigger concern to me would be the many tasks that
we would fork. It would be better to have a depth threshold after
which we stop forking. This is already mentioned in the comment.</p>
<p>My algorithm for (2 * 1024 * 1024)! ends up like this:</p>
<p>left size 2,733,860 bits, right size 2,746,476 bits<br>
left size 4,340,409 bits, right size 4,864,687 bits<br>
left size 5,062,576 bits, right size 5,191,086 bits<br>
left size 5,286,644 bits, right size 5,362,796 bits<br>
left size 5,426,123 bits, right size 5,480,336 bits<br>
left size 9,205,096 bits, right size 10,253,661 bits<br>
left size 10,649,440 bits, right size 10,906,459 bits<br>
left size 19,458,756 bits, right size 21,555,898 bits<br>
2097152 bits 41014654<br>
fjTime = 4798ms<br>
</p>
<p>Your algorithm for the same input has an almost equal number of
bits for the two numbers:</p>
<p>left size 320,424 bits, right size 320,433 bits<br>
left size 640,852 bits, right size 640,861 bits<br>
left size 640,847 bits, right size 640,857 bits<br>
left size 1,281,703 bits, right size 1,281,713 bits<br>
left size 2,563,415 bits, right size 2,563,424 bits<br>
left size 5,126,828 bits, right size 5,126,839 bits<br>
left size 10,253,656 bits, right size 10,253,667 bits<br>
left size 20,507,332 bits, right size 20,507,322 bits<br>
2097152 bits 41014654<br>
fjTime = 69867ms<br>
</p>
<p>However, mine also happens to be about 12x faster, but I suspect
that has more to do with the computational time complexity than
with Fork/Join. With BigInteger, we want to get to large numbers
as quickly as possible, so that we can start using Karatsuba and
Toom Cook 3.<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 12:17, Alex Otenko wrote:<br>
</div>
<blockquote type="cite"
cite="mid:CANkgWKjP4Y-61LtPu5zwX0iHPrDE+UX=1KVvX-dZFDcEk8N_OA@mail.gmail.com">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
<div dir="auto">Do we want to also nudge the reader towards
considering how to split tasks into equally sized, if possible?
<div dir="auto"><br>
</div>
<div dir="auto"><a href="https://bit.ly/3HOH9Ca"
moz-do-not-send="true">https://bit.ly/3HOH9Ca</a> -
factorial is, of course, better done by ensuring both branches
multiply numbers of similar magnitude.<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 Thu, 25 Nov 2021, 09:40
Alex Otenko, <<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">
<div dir="auto">Hmmm, yes. I lost focus there.
<div dir="auto"><br>
</div>
<div dir="auto">I think there are two different problems:
seeing that it is Fibonacci, and seeing how recursion
works. I am not sure how much importance to give to the
former.</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 Thu, 25 Nov 2021, 05:38
Dr Heinz M. Kabutz, <<a
href="mailto:[email protected]" target="_blank"
rel="noreferrer" 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">
<div>
<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
href="https://github.com/openjdk/jdk/pull/6409"
rel="noreferrer noreferrer" target="_blank"
moz-do-not-send="true">https://github.com/openjdk/jdk/pull/6409</a><br>
</p>
<pre cols="72">Regards
Heinz
--
Dr Heinz M. Kabutz (PhD CompSci)
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>
Java Champion - <a href="http://www.javachampions.org" rel="noreferrer noreferrer" target="_blank" moz-do-not-send="true">www.javachampions.org</a>
JavaOne Rock Star Speaker
Tel: +30 69 75 595 262
Skype: kabutz
</pre>
<div>On 2021/11/25 01:30, Alex Otenko wrote:<br>
</div>
<blockquote type="cite">
<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"
rel="noreferrer noreferrer" target="_blank"
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]"
rel="noreferrer noreferrer" target="_blank"
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 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 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 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 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]"
rel="noreferrer noreferrer noreferrer"
target="_blank" moz-do-not-send="true">[email protected]</a><br>
<a
href="http://cs.oswego.edu/mailman/listinfo/concurrency-interest"
rel="noreferrer noreferrer noreferrer
noreferrer" target="_blank"
moz-do-not-send="true">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><br>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</body>
</html>
--===============2806443294668406539==
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
--===============2806443294668406539==--