Re: Better RecursiveTask Example
Alex Otenko via Concurrency-interest <[email protected]> Thu, 25 Nov 2021 09:40:36 +0000
| Newsgroups | gmane.comp.java.jsr.166-concurrency |
|---|---|
| Message-ID | <CANkgWKjFKRYqxoLy+yKXL3eeh_8afqvntxZxMM0un9TTP67hFg@mail.gmail.com> |
--===============4606399732945425877== Content-Type: multipart/alternative; boundary="000000000000f0c16405d199c4c4" --000000000000f0c16405d199c4c4 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Hmmm, yes. I lost focus there. 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. Alex On Thu, 25 Nov 2021, 05:38 Dr Heinz M. Kabutz, <[email protected]> wrote: > Hi Alex, > > 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. > > 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: https://github.com/openjdk/jdk/pull/6409 > > 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 > > On 2021/11/25 01:30, Alex Otenko 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 >> > --000000000000f0c16405d199c4c4 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"auto">Hmmm, yes. I lost focus there.<div dir=3D"auto"><br></div= ><div dir=3D"auto">I think there are two different problems: seeing that it= is Fibonacci, and seeing how recursion works. I am not sure how much impor= tance to give to the former.</div><div dir=3D"auto"><br></div><div dir=3D"a= uto"><br></div><div dir=3D"auto">Alex</div></div><br><div class=3D"gmail_qu= ote"><div dir=3D"ltr" class=3D"gmail_attr">On Thu, 25 Nov 2021, 05:38 Dr He= inz M. Kabutz, <<a href=3D"mailto:[email protected]">heinz@javasp= ecialists.eu</a>> wrote:<br></div><blockquote class=3D"gmail_quote" styl= e=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"> =20 =20 =20 <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=3D"https://github.com/openjdk/jdk/pull/6409" target=3D"_blank= " rel=3D"noreferrer">https://github.com/openjdk/jdk/pull/6409</a><br> </p> <pre cols=3D"72">Regards Heinz --=20 Dr Heinz M. Kabutz (PhD CompSci) Author of "The Java=E2=84=A2 Specialists' Newsletter" - <a hr= ef=3D"http://www.javaspecialists.eu" target=3D"_blank" rel=3D"noreferrer">w= ww.javaspecialists.eu</a> Java Champion - <a href=3D"http://www.javachampions.org" target=3D"_blank" = rel=3D"noreferrer">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=3D"cite"> =20 <div dir=3D"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=3D"auto"><br> </div> <div dir=3D"auto"><a href=3D"https://bit.ly/3oVFeTD" target=3D"_bla= nk" 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"gmail_attr">On Wed, 24 Nov 2021, 19:19 Dr Heinz M. Kabutz via Concurrency-interest, <<a href=3D"mailto:c= [email protected]" target=3D"_blank" rel=3D"noreferrer">con= [email protected]</a>> wrote:<br> </div> <blockquote class=3D"gmail_quote" style=3D"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=3D"https://docs.oracle.com/en/java/javase/11/docs/api/jav= a.base/java/util/concurrent/RecursiveTask.html" rel=3D"noreferrer noreferre= r noreferrer" target=3D"_blank">https://docs.oracle.com/en/java/javase/11/d= ocs/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> =C2=A0=C2=A0class Fibonacci extends RecursiveTask<Integer> = {<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 <=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();<b= r> =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'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 afte= r about <br> fibonacci(90), we would need BigInteger. And there the add is linear, <br> meaning that the "fast linear" algorithm referred to he= re 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> =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 fr= om;<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 return 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 (fro= m + to) >>> 1;<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 FactorialTask le= ftTask =3D new FactorialTask(from, mid);<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 FactorialTask ri= ghtTask =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 rightTask.invoke();<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BigInteger left = =3D leftTask.join();<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return left.mult= iply(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= .rangeClosed(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'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> =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 case 0 -> 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 case 1 -> 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 default -> {<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's Sum of Squares Algorith= m<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 <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=E2=84=A2 Specialists' Newsletter&quo= t; - <a href=3D"http://www.javaspecialists.eu" rel=3D"noreferrer noreferrer noreferrer" target=3D"_blank">www.javaspecialists.eu= </a><br> Java Champion - <a href=3D"http://www.javachampions.org" rel=3D"n= oreferrer 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"nore= ferrer noreferrer" target=3D"_blank">[email protected]</a>= <br> <a href=3D"http://cs.oswego.edu/mailman/listinfo/concurrency-inte= rest" rel=3D"noreferrer noreferrer noreferrer" target=3D"_blank">http://cs.= oswego.edu/mailman/listinfo/concurrency-interest</a><br> </blockquote> </div> </blockquote> </div> </blockquote></div> --000000000000f0c16405d199c4c4-- --===============4606399732945425877== 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 --===============4606399732945425877==--