Re: Better RecursiveTask Example
Alex Otenko via Concurrency-interest <[email protected]> Thu, 25 Nov 2021 15:43:17 +0000
| Newsgroups | gmane.comp.java.jsr.166-concurrency |
|---|---|
| Message-ID | <CANkgWKjRL0Zr=CkrG-EVsZGCbpkkRA9_thgivs3-F2e8nHxk5g@mail.gmail.com> |
--===============4086076455452693942== Content-Type: multipart/alternative; boundary="00000000000007a07f05d19ed6a2" --00000000000007a07f05d19ed6a2 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable The usual: all forked, none volunteered to pick up the task they all depend on. This seems to fix it: https://bit.ly/3laU9Iu (But this is moot now, your suggestion is just as good) Alex On Thu, 25 Nov 2021, 10:35 Dr Heinz M. Kabutz, <[email protected]> wrote: > Hi Alex, > > there is some strange resource deadlock in your Fibonacci solution that > occurs when there are more than 2 cores. Try run your Main with > -XX:+ActiveProcessorCount=3D8 to see what I mean: > > > https://tio.run/##pVVNbxMxEL3nVww9oHWjWmnEAZpugFatBBKkajlUIA624yZOdu3I9ga= qKn@dMN7vfBSCsJTNzng8b/z8PDtjS3YyG8/Xa5UujPUwQwdNmZ/SCzX5oL2cSDvotCczrxIqjB= aZtVJ7em3s/KNR@saY5LDIL8zN/xx5K/HNqaUsQjuLjCdKgEiYc/CJKQ1PHYDS6zzz@Lc0agwpz= kV33io9@fYdGMnjAO4enZcpNZmnC5zziY6OEFcljCfyxhohnTPWQQxH0IXbTHuVSjqRvnyNCN0T= HhEyeDa9MGlqclJumGVJIhPl0hKgTVlAudwXW2d/MDbCpKDi3gDU@avw7HbJc8ha/oBrxU2kCFK= aLjIfyueY7K8r3vS2lwCswrKS4sToCTzkubEeXbGrHiDSEMfQI2Clz6yGXlF6voDhrts2R/u0ZY= vGrreKrlJ8dKomU@n8SMsL5SMEHQ6HGA/qRc4Hmri8KqXKKTEBO@bINT8Wg2qKw3EMvDZFMJtZF= kzWMrubwRtm2ISsrcBA4OAlKAIvcLvQKghHKKcB2s2Ww205NhFWneZZcsy3j6e4HuEkQf70Uo8d= bFyk8zA1rA4tnGCRvrnp1fZbHr7jEaWSyut3vaMHHH6qHEVNVBCrYsm70VJaq8aySGCNl8LLcVF= zrbwmTaGsc@iTpw3y4lY9dPT5apvIQo1vQZy1A79e3Y62GRbUZdxbJnzEqitSjJLlsJOtU8DRbm= UlrTbgVjdJQxApoSjoeUQGe5c1lQ1BZ6GY9jRlY7bwEbJxgrnpDN2hC6F7HNWmIDTNEq8WyWPj5= ORwXN4/CJb/JwzrH7i7XRj2DzDiMBixB0YQ0rrqqIs@VXpp5nnrR8p5v4wkrQaB7aJf17k/KBwr= Hm7pbwQWlJ03jNOiYWz2i73NYKuBBO0GUEZ25dl5TsOrTvHrrNbrX2bhldFufXJ/f/ZeeOwS9bf= t0uCHL379Gw > > > 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 11:40, Alex Otenko wrote: > > Hmmm, yes. I lost focus there. > > I think there are two different problems: seeing that it is Fibonacci, an= d > 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 parallelMultipl= y() >> 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.javaspeciali= sts.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/= concurrent/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 us= e >>> 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 i= t >>> 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 differen= t >>> 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.javaspecial= ists.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 >>> >> --00000000000007a07f05d19ed6a2 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"auto">The usual: all forked, none volunteered to pick up the ta= sk they all depend on.<div dir=3D"auto"><br></div><div dir=3D"auto">This se= ems to fix it:</div><div dir=3D"auto"><br></div><div dir=3D"auto"><a href= =3D"https://bit.ly/3laU9Iu">https://bit.ly/3laU9Iu</a></div><div dir=3D"aut= o"><br></div><div dir=3D"auto">(But this is moot now, your suggestion is ju= st as good)<br><div dir=3D"auto"><br></div><div dir=3D"auto">Alex</div></di= v></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr= ">On Thu, 25 Nov 2021, 10:35 Dr Heinz M. Kabutz, <<a href=3D"mailto:hein= [email protected]">[email protected]</a>> wrote:<br></div><blo= ckquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #c= cc solid;padding-left:1ex"> =20 =20 =20 <div> <p>Hi Alex,</p> <p>there is some strange resource deadlock in your Fibonacci solution that occurs when there are more than 2 cores. Try run your Main with -XX:+ActiveProcessorCount=3D8 to see what I mean:</p> <p><a href=3D"https://tio.run/#%23pVVNbxMxEL3nVww9oHWjWmnEAZpugFatBBKka= jlUIA624yZOdu3I9gaqKn@dMN7vfBSCsJTNzng8b/z8PDtjS3YyG8/Xa5UujPUwQwdNmZ/SCzX5= oL2cSDvotCczrxIqjBaZtVJ7em3s/KNR@saY5LDIL8zN/xx5K/HNqaUsQjuLjCdKgEiYc/CJKQ1= PHYDS6zzz@Lc0agwpzkV33io9@fYdGMnjAO4enZcpNZmnC5zziY6OEFcljCfyxhohnTPWQQxH0I= XbTHuVSjqRvnyNCN0THhEyeDa9MGlqclJumGVJIhPl0hKgTVlAudwXW2d/MDbCpKDi3gDU@avw7= HbJc8ha/oBrxU2kCFKaLjIfyueY7K8r3vS2lwCswrKS4sToCTzkubEeXbGrHiDSEMfQI2Clz6yG= XlF6voDhrts2R/u0ZYvGrreKrlJ8dKomU@n8SMsL5SMEHQ6HGA/qRc4Hmri8KqXKKTEBO@bINT8= Wg2qKw3EMvDZFMJtZFkzWMrubwRtm2ISsrcBA4OAlKAIvcLvQKghHKKcB2s2Ww205NhFWneZZcs= y3j6e4HuEkQf70Uo8dbFyk8zA1rA4tnGCRvrnp1fZbHr7jEaWSyut3vaMHHH6qHEVNVBCrYsm70= VJaq8aySGCNl8LLcVFzrbwmTaGsc@iTpw3y4lY9dPT5apvIQo1vQZy1A79e3Y62GRbUZdxbJnzE= qitSjJLlsJOtU8DRbmUlrTbgVjdJQxApoSjoeUQGe5c1lQ1BZ6GY9jRlY7bwEbJxgrnpDN2hC6F= 7HNWmIDTNEq8WyWPj5ORwXN4/CJb/JwzrH7i7XRj2DzDiMBixB0YQ0rrqqIs@VXpp5nnrR8p5v4= wkrQaB7aJf17k/KBwrHm7pbwQWlJ03jNOiYWz2i73NYKuBBO0GUEZ25dl5TsOrTvHrrNbrX2bhl= dFufXJ/f/ZeeOwS9bft0uCHL379Gw" target=3D"_blank" rel=3D"noreferrer">https:/= /tio.run/##pVVNbxMxEL3nVww9oHWjWmnEAZpugFatBBKkajlUIA624yZOdu3I9gaqKn@dMN7v= fBSCsJTNzng8b/z8PDtjS3YyG8/Xa5UujPUwQwdNmZ/SCzX5oL2cSDvotCczrxIqjBaZtVJ7em3= s/KNR@saY5LDIL8zN/xx5K/HNqaUsQjuLjCdKgEiYc/CJKQ1PHYDS6zzz@Lc0agwpzkV33io9@f= YdGMnjAO4enZcpNZmnC5zziY6OEFcljCfyxhohnTPWQQxH0IXbTHuVSjqRvnyNCN0THhEyeDa9M= GlqclJumGVJIhPl0hKgTVlAudwXW2d/MDbCpKDi3gDU@avw7HbJc8ha/oBrxU2kCFKaLjIfyueY= 7K8r3vS2lwCswrKS4sToCTzkubEeXbGrHiDSEMfQI2Clz6yGXlF6voDhrts2R/u0ZYvGrreKrlJ= 8dKomU@n8SMsL5SMEHQ6HGA/qRc4Hmri8KqXKKTEBO@bINT8Wg2qKw3EMvDZFMJtZFkzWMrubwR= tm2ISsrcBA4OAlKAIvcLvQKghHKKcB2s2Ww205NhFWneZZcsy3j6e4HuEkQf70Uo8dbFyk8zA1r= A4tnGCRvrnp1fZbHr7jEaWSyut3vaMHHH6qHEVNVBCrYsm70VJaq8aySGCNl8LLcVFzrbwmTaGs= c@iTpw3y4lY9dPT5apvIQo1vQZy1A79e3Y62GRbUZdxbJnzEqitSjJLlsJOtU8DRbmUlrTbgVjd= JQxApoSjoeUQGe5c1lQ1BZ6GY9jRlY7bwEbJxgrnpDN2hC6F7HNWmIDTNEq8WyWPj5ORwXN4/CJ= b/JwzrH7i7XRj2DzDiMBixB0YQ0rrqqIs@VXpp5nnrR8p5v4wkrQaB7aJf17k/KBwrHm7pbwQWl= J03jNOiYWz2i73NYKuBBO0GUEZ25dl5TsOrTvHrrNbrX2bhldFufXJ/f/ZeeOwS9bft0uCHL379= Gw</a></p> <p><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 11:40, Alex Otenko wrote:<br> </div> <blockquote type=3D"cite"> =20 <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 importance to give to the former.</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 Thu, 25 Nov 2021, 05:38 Dr Heinz M. Kabutz, <<a href=3D"mailto:[email protected]" = target=3D"_blank" rel=3D"noreferrer">[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"> <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/64= 09" rel=3D"noreferrer noreferrer" target=3D"_blank">https://github.com/open= jdk/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" rel=3D"noreferrer noreferrer" target= =3D"_blank">www.javaspecialists.eu</a> Java Champion - <a href=3D"http://www.javachampions.org" rel=3D"noreferrer = noreferrer" target=3D"_blank">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"> <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" rel=3D= "noreferrer noreferrer" target=3D"_blank">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:[email protected]"= rel=3D"noreferrer noreferrer" target=3D"_blank">[email protected]= wego.edu</a>> wrote:<br> </div> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8e= x;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/java.base/java/util/concurrent/RecursiveTask.html" rel=3D"noreferrer n= oreferrer noreferrer noreferrer" target=3D"_blank">https://docs.oracle.com/= en/java/javase/11/docs/api/java.base/java/util/concurrent/RecursiveTask.htm= l</a><br> <br> For a classic example, here is a task computing Fibonacci numbers:<br> <br> <br> =C2=A0=C2=A0class Fibonacci extends RecursiveTask<Inte= ger> {<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 Fibon= acci(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 Fibon= acci(n - 2);<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return f2.compute() + f1.j= oin();<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'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 referr= ed 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> =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.fro= m =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 noreferrer" target=3D"_blank">thi= s.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 (from + to) >>> 1;<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Factoria= lTask leftTask =3D new FactorialTask(from, mid);<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Factoria= lTask 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 BigInteg= er right =3D rightTask.invoke();<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BigInteg= er left =3D leftTask.join();<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return l= eft.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 factori= alStream(int n) {<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 return I= ntStream.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 s= witch (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 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();<b= r> <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' Newsle= tter" - <a href=3D"http://www.javaspecialists.eu" rel=3D"noreferrer noreferrer noreferrer noreferrer" target=3D"_blank">www= .javaspecialists.eu</a><br> Java Champion - <a href=3D"http://www.javachampions.org" = rel=3D"noreferrer 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 noreferrer noreferrer" target=3D"_blank">Concurrency-interes= [email protected]</a><br> <a href=3D"http://cs.oswego.edu/mailman/listinfo/concurre= ncy-interest" rel=3D"noreferrer noreferrer noreferrer noreferrer" target=3D= "_blank">http://cs.oswego.edu/mailman/listinfo/concurrency-interest</a><br> </blockquote> </div> </blockquote> </div> </blockquote> </div> </blockquote> </div> </blockquote></div> --00000000000007a07f05d19ed6a2-- --===============4086076455452693942== 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 --===============4086076455452693942==--