Re: Better RecursiveTask Example

--===============5668002650460905087==
Content-Type: multipart/alternative; boundary="0000000000007bf81905d191e7e8"

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

https://bit.ly/3HVgEey - but maybe this is less silly, as we can actually
make subcomputations wait for the previous task to complete.

Alex

On Wed, 24 Nov 2021, 23:30 Alex Otenko, <[email protected]> wrote:

> 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/c=
oncurrent/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.javaspeciali=
sts.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
>>
>

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

<div dir=3D"auto"><a href=3D"https://bit.ly/3HVgEey">https://bit.ly/3HVgEey=
</a> - but maybe this is less silly, as we can actually make subcomputation=
s wait for the previous task to complete.<div dir=3D"auto"><br></div><div d=
ir=3D"auto">Alex</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr"=
 class=3D"gmail_attr">On Wed, 24 Nov 2021, 23:30 Alex Otenko, &lt;<a href=
=3D"mailto:[email protected]">[email protected]</a>&gt; w=
rote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex=
;border-left:1px #ccc solid;padding-left:1ex"><div dir=3D"auto">I presume l=
ogarithmic cost Fibonacci is not considered, because there&#39;s little poi=
nt doing it recursively? (Although can still show off parallel computations=
)<div dir=3D"auto"><br></div><div dir=3D"auto"><a href=3D"https://bit.ly/3o=
VFeTD" target=3D"_blank" rel=3D"noreferrer">https://bit.ly/3oVFeTD</a></div=
><div dir=3D"auto"><br></div><div dir=3D"auto"><br></div><div dir=3D"auto">=
Alex</div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gm=
ail_attr">On Wed, 24 Nov 2021, 19:19 Dr Heinz M. Kabutz via Concurrency-int=
erest, &lt;<a href=3D"mailto:[email protected]" target=3D"=
_blank" rel=3D"noreferrer">[email protected]</a>&gt; wrote=
:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bor=
der-left:1px #ccc solid;padding-left:1ex">Every time I see the example in R=
ecursiveTask 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 noreferr=
er" target=3D"_blank">https://docs.oracle.com/en/java/javase/11/docs/api/ja=
va.base/java/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 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 noreferre=
r" target=3D"_blank">www.javaspecialists.eu</a><br>
Java Champion - <a href=3D"http://www.javachampions.org" rel=3D"noreferrer =
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]" rel=3D"noreferrer nor=
eferrer" target=3D"_blank">[email protected]</a><br>
<a href=3D"http://cs.oswego.edu/mailman/listinfo/concurrency-interest" rel=
=3D"noreferrer noreferrer noreferrer" target=3D"_blank">http://cs.oswego.ed=
u/mailman/listinfo/concurrency-interest</a><br>
</blockquote></div>
</blockquote></div>

--0000000000007bf81905d191e7e8--

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

--===============5668002650460905087==--