Re: Better RecursiveTask Example

--===============3701218844231636213==
Content-Type: multipart/alternative; boundary="000000000000d4287405d1913d33"

--000000000000d4287405d1913d33
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

I presume logarithmic cost Fibonacci is not considered, because there's
little point doing it recursively? (Although can still show off parallel
computations)

https://bit.ly/3oVFeTD


Alex

On Wed, 24 Nov 2021, 19:19 Dr Heinz M. Kabutz via Concurrency-interest, <
[email protected]> wrote:

> Every time I see the example in RecursiveTask I have to cringe:
>
>
> https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/co=
ncurrent/RecursiveTask.html
>
> For a classic example, here is a task computing Fibonacci numbers:
>
>
>   class Fibonacci extends RecursiveTask<Integer> {
>     final int n;
>     Fibonacci(int n) { this.n =3D n; }
>     protected Integer compute() {
>       if (n <=3D 1)
>         return n;
>       Fibonacci f1 =3D new Fibonacci(n - 1);
>       f1.fork();
>       Fibonacci f2 =3D new Fibonacci(n - 2);
>       return f2.compute() + f1.join();
>     }
>   }
> However, besides being a dumb way to compute Fibonacci functions (there
> is a simple fast linear algorithm that you'd use in practice), this is
> likely to perform poorly because the smallest subtasks are too small to
> be worthwhile splitting up. Instead, as is the case for nearly all
> fork/join applications, you'd pick some minimum granularity size (for
> example 10 here) for which you always sequentially solve rather than
> subdividing.
>
>
>
> Indeed, it is a dumb way to compute Fibonacci, but the "fast linear"
> algorithm isn't fast either. Since we overflow even Long after about
> fibonacci(90), we would need BigInteger. And there the add is linear,
> meaning that the "fast linear" algorithm referred to here is probably
> going to end up as "slow quadratic".
>
> To me, this example sends the completely wrong message. Let's take the
> worst possible algorithm and parallelize it. Great. That means if we use
> 1000 processors, we can solve the problem of n+10 in the same time as n
> with a single processor.
>
> I do realize this is meant to illustrate a point, but it doesn't do it
> very well IME. I would like to propose to change this to a slightly
> better example, for example a Factorial calculation:
>
> public class FactorialTask extends RecursiveTask<BigInteger> {
>      private final int from, to;
>
>      public FactorialTask(int n) {
>          this(0, n);
>      }
>
>      private FactorialTask(int from, int to) {
>          this.from =3D from;
>          this.to =3D to;
>      }
>
>      protected BigInteger compute() {
>          if (from =3D=3D to) {
>              if (from =3D=3D 0) return BigInteger.ONE;
>              return BigInteger.valueOf(from);
>          }
>          int mid =3D (from + to) >>> 1;
>          FactorialTask leftTask =3D new FactorialTask(from, mid);
>          FactorialTask rightTask =3D new FactorialTask(mid + 1, to);
>          leftTask.fork();
>          BigInteger right =3D rightTask.invoke();
>          BigInteger left =3D leftTask.join();
>          return left.multiply(right);
>      }
> }
>
> This is actually a *lot* faster than the stream version:
>
>      public static BigInteger factorialStream(int n) {
>          return IntStream.rangeClosed(1, n)
>                  .mapToObj(BigInteger::valueOf)
>                  .reduce(BigInteger.ONE, BigInteger::multiply);
>      }
>
> (this has to do more with the algorithms used by BigInteger's multiply
> method than the parallelization, but that also has an effect.
>
>
> Alternatively, if we have to have Fibonacci, could we at least change it
> to Dijkstra's Sum of Squares? I believe there are slightly better
> algorithms, but this one works very nicely with parallelisation:
>
> public class FibonacciTask extends RecursiveTask<BigInteger> {
>      private final int n;
>
>      public FibonacciTask(int n) {
>          this.n =3D n;
>      }
>
>      @Override
>      protected BigInteger compute() {
>          return switch (n) {
>              case 0 -> BigInteger.ZERO;
>              case 1 -> BigInteger.ONE;
>              default -> {
>                  // Dijkstra's Sum of Squares Algorithm
>                  int half =3D (n + 1) / 2;
>                  FibonacciTask f0_task =3D new FibonacciTask(half - 1);
>                  f0_task.fork();
>                  FibonacciTask f1_task =3D new FibonacciTask(half);
>                  BigInteger f1 =3D f1_task.invoke();
>                  BigInteger f0 =3D f0_task.join();
>
>                  if (n % 2 =3D=3D 1) {
>                      yield f0.multiply(f0).add(f1.multiply(f1));
>                  } else {
>                      yield f0.shiftLeft(1).add(f1).multiply(f1);
>                  }
>              }
>          };
>      }
> }
>
> Please let me know if you agree with this change (or propose a different
> example). I would be happy to make the change. I presume it would need
> to be done in the CVS? Or can I do it in the OpenJDK GitHub repository
> and then we can sync that over to CVS? (My preference would be GitHub)
>
>
>
>
> Regards
>
> Heinz
> --
> Dr Heinz M. Kabutz (PhD CompSci)
> Author of "The Java=E2=84=A2 Specialists' Newsletter" - www.javaspecialis=
ts.eu
> Java Champion - www.javachampions.org
> JavaOne Rock Star Speaker
> Tel: +30 69 75 595 262
> Skype: kabutz
>
> _______________________________________________
> Concurrency-interest mailing list
> [email protected]
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>

--000000000000d4287405d1913d33
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"auto">I presume logarithmic cost Fibonacci is not considered, b=
ecause there&#39;s little point doing it recursively? (Although can still s=
how off parallel computations)<div dir=3D"auto"><br></div><div dir=3D"auto"=
><a href=3D"https://bit.ly/3oVFeTD">https://bit.ly/3oVFeTD</a></div><div di=
r=3D"auto"><br></div><div dir=3D"auto"><br></div><div dir=3D"auto">Alex</di=
v></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr=
">On Wed, 24 Nov 2021, 19:19 Dr Heinz M. Kabutz via Concurrency-interest, &=
lt;<a href=3D"mailto:[email protected]">concurrency-intere=
[email protected]</a>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" =
style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Eve=
ry time I see the example in RecursiveTask I have to cringe:<br>
<br>
<a href=3D"https://docs.oracle.com/en/java/javase/11/docs/api/java.base/jav=
a/util/concurrent/RecursiveTask.html" rel=3D"noreferrer noreferrer" target=
=3D"_blank">https://docs.oracle.com/en/java/javase/11/docs/api/java.base/ja=
va/util/concurrent/RecursiveTask.html</a><br>
<br>
For a classic example, here is a task computing Fibonacci numbers:<br>
<br>
<br>
=C2=A0=C2=A0class Fibonacci extends RecursiveTask&lt;Integer&gt; {<br>
=C2=A0=C2=A0=C2=A0 final int n;<br>
=C2=A0=C2=A0=C2=A0 Fibonacci(int n) { this.n =3D n; }<br>
=C2=A0=C2=A0=C2=A0 protected Integer compute() {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 if (n &lt;=3D 1)<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return n;<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Fibonacci f1 =3D new Fibonacci(n - 1);<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 f1.fork();<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Fibonacci f2 =3D new Fibonacci(n - 2);<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return f2.compute() + f1.join();<br>
=C2=A0=C2=A0=C2=A0 }<br>
=C2=A0=C2=A0}<br>
However, besides being a dumb way to compute Fibonacci functions (there <br=
>
is a simple fast linear algorithm that you&#39;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&#39;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 &quot;fast linear&qu=
ot; <br>
algorithm isn&#39;t fast either. Since we overflow even Long after about <b=
r>
fibonacci(90), we would need BigInteger. And there the add is linear, <br>
meaning that the &quot;fast linear&quot; algorithm referred to here is prob=
ably <br>
going to end up as &quot;slow quadratic&quot;.<br>
<br>
To me, this example sends the completely wrong message. Let&#39;s take the =
<br>
worst possible algorithm and parallelize it. Great. That means if we use <b=
r>
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&#39;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&lt;BigInteger&gt; {<br>
=C2=A0=C2=A0=C2=A0=C2=A0 private final int from, to;<br>
<br>
=C2=A0=C2=A0=C2=A0=C2=A0 public FactorialTask(int n) {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 this(0, n);<br>
=C2=A0=C2=A0=C2=A0=C2=A0 }<br>
<br>
=C2=A0=C2=A0=C2=A0=C2=A0 private FactorialTask(int from, int to) {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 this.from =3D from;<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 <a href=3D"http://this.to"=
 rel=3D"noreferrer noreferrer" target=3D"_blank">this.to</a> =3D to;<br>
=C2=A0=C2=A0=C2=A0=C2=A0 }<br>
<br>
=C2=A0=C2=A0=C2=A0=C2=A0 protected BigInteger compute() {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 if (from =3D=3D to) {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 if=
 (from =3D=3D 0) return BigInteger.ONE;<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 re=
turn BigInteger.valueOf(from);<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 }<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 int mid =3D (from + to) &g=
t;&gt;&gt; 1;<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 FactorialTask leftTask =3D=
 new FactorialTask(from, mid);<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 FactorialTask rightTask =
=3D new FactorialTask(mid + 1, to);<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 leftTask.fork();<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BigInteger right =3D right=
Task.invoke();<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BigInteger left =3D leftTa=
sk.join();<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return left.multiply(right=
);<br>
=C2=A0=C2=A0=C2=A0=C2=A0 }<br>
}<br>
<br>
This is actually a *lot* faster than the stream version:<br>
<br>
=C2=A0=C2=A0=C2=A0=C2=A0 public static BigInteger factorialStream(int n) {<=
br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return IntStream.rangeClos=
ed(1, n)<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 .mapToObj(BigInteger::valueOf)<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 .reduce(BigInteger.ONE, BigInteger::multiply);<br>
=C2=A0=C2=A0=C2=A0=C2=A0 }<br>
<br>
(this has to do more with the algorithms used by BigInteger&#39;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 <b=
r>
to Dijkstra&#39;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&lt;BigInteger&gt; {<br>
=C2=A0=C2=A0=C2=A0=C2=A0 private final int n;<br>
<br>
=C2=A0=C2=A0=C2=A0=C2=A0 public FibonacciTask(int n) {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 this.n =3D n;<br>
=C2=A0=C2=A0=C2=A0=C2=A0 }<br>
<br>
=C2=A0=C2=A0=C2=A0=C2=A0 @Override<br>
=C2=A0=C2=A0=C2=A0=C2=A0 protected BigInteger compute() {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return switch (n) {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ca=
se 0 -&gt; BigInteger.ZERO;<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 ca=
se 1 -&gt; BigInteger.ONE;<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 de=
fault -&gt; {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 // Dijkstra&#39;s Sum of Squares Algorithm<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 int half =3D (n + 1) / 2;<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 FibonacciTask f0_task =3D new FibonacciTask(half - 1)=
;<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 f0_task.fork();<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 FibonacciTask f1_task =3D new FibonacciTask(half);<br=
>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 BigInteger f1 =3D f1_task.invoke();<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 BigInteger f0 =3D f0_task.join();<br>
<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 if (n % 2 =3D=3D 1) {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 yield f0.multiply(f0).add(f1.=
multiply(f1));<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 } else {<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 yield f0.shiftLeft(1).add(f1)=
.multiply(f1);<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=
=A0=C2=A0=C2=A0=C2=A0 }<br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 }<=
br>
=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 };<br>
=C2=A0=C2=A0=C2=A0=C2=A0 }<br>
}<br>
<br>
Please let me know if you agree with this change (or propose a different <b=
r>
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 &quot;The Java=E2=84=A2 Specialists&#39; Newsletter&quot; - <a hr=
ef=3D"http://www.javaspecialists.eu" rel=3D"noreferrer noreferrer" target=
=3D"_blank">www.javaspecialists.eu</a><br>
Java Champion - <a href=3D"http://www.javachampions.org" rel=3D"noreferrer =
noreferrer" target=3D"_blank">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=3D"mailto:[email protected]" target=3D"_blank" rel=
=3D"noreferrer">[email protected]</a><br>
<a href=3D"http://cs.oswego.edu/mailman/listinfo/concurrency-interest" rel=
=3D"noreferrer noreferrer" target=3D"_blank">http://cs.oswego.edu/mailman/l=
istinfo/concurrency-interest</a><br>
</blockquote></div>

--000000000000d4287405d1913d33--

--===============3701218844231636213==
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

--===============3701218844231636213==--