Re: Better RecursiveTask Example
Alex Otenko via Concurrency-interest <[email protected]> Thu, 25 Nov 2021 15:26:41 +0000
| Newsgroups | gmane.comp.java.jsr.166-concurrency |
|---|---|
| Message-ID | <CANkgWKjCSwrHjSqjdJFT+HorXkZd2xME3fqyinCiei-iC1YaEA@mail.gmail.com> |
--===============1152685310397936414== Content-Type: multipart/alternative; boundary="000000000000a48d2e05d19e9a18" --000000000000a48d2e05d19e9a18 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Eg HotSpot as before: Factorial, straightforward: 6.281s Factorial, try equalize work: 6.051s GraalVM EE 20.2.0 (JDK 11 based): 5.278s and 4.668s respectively for the same task. Alex On Thu, 25 Nov 2021, 15:18 Alex Otenko, <[email protected]> wrote: > Hi Heinz, > > I don't mind even if my version is left as an exercise for the reader - > after all, I have no feel of what the target audience can grasp. > > As for your finding - that's interesting. I don't get 12x worse with > (2x1024x1024)!, I always get mine a little faster (and for some inputs > quite a bit faster). > > (HotSpot, 15.0.1+9-18 on Mac) > > Alex > > > On Thu, 25 Nov 2021, 11:00 Dr Heinz M. Kabutz, <[email protected]> > wrote: > >> With my current simple algorithm, the magnitude of the two halves are >> similar. Whilst your algorithm is better in terms of keeping the two hal= ves >> 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 conce= rn >> 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. >> >> My algorithm for (2 * 1024 * 1024)! ends up like this: >> >> left size 2,733,860 bits, right size 2,746,476 bits >> left size 4,340,409 bits, right size 4,864,687 bits >> left size 5,062,576 bits, right size 5,191,086 bits >> left size 5,286,644 bits, right size 5,362,796 bits >> left size 5,426,123 bits, right size 5,480,336 bits >> left size 9,205,096 bits, right size 10,253,661 bits >> left size 10,649,440 bits, right size 10,906,459 bits >> left size 19,458,756 bits, right size 21,555,898 bits >> 2097152 bits 41014654 >> fjTime =3D 4798ms >> >> Your algorithm for the same input has an almost equal number of bits for >> the two numbers: >> >> left size 320,424 bits, right size 320,433 bits >> left size 640,852 bits, right size 640,861 bits >> left size 640,847 bits, right size 640,857 bits >> left size 1,281,703 bits, right size 1,281,713 bits >> left size 2,563,415 bits, right size 2,563,424 bits >> left size 5,126,828 bits, right size 5,126,839 bits >> left size 10,253,656 bits, right size 10,253,667 bits >> left size 20,507,332 bits, right size 20,507,322 bits >> 2097152 bits 41014654 >> fjTime =3D 69867ms >> >> However, mine also happens to be about 12x faster, but I suspect that ha= s >> more to do with the computational time complexity than with Fork/Join. W= ith >> BigInteger, we want to get to large numbers as quickly as possible, so t= hat >> we can start using Karatsuba and Toom Cook 3. >> >> 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 12:17, Alex Otenko wrote: >> >> Do we want to also nudge the reader towards considering how to split >> tasks into equally sized, if possible? >> >> https://bit.ly/3HOH9Ca - factorial is, of course, better done by >> ensuring both branches multiply numbers of similar magnitude. >> >> Alex >> >> On Thu, 25 Nov 2021, 09:40 Alex Otenko, <[email protected]> >> wrote: >> >>> 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 gi= ve >>> to the former. >>> >>> >>> Alex >>> >>> On Thu, 25 Nov 2021, 05:38 Dr Heinz M. Kabutz, <[email protected]= u> >>> 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 larg= e >>>> numbers that need to be multiplied together, and this is (currently) >>>> happening in parallel. I've got a PR in the works to add parallelMulti= ply() >>>> 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.javaspecia= lists.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 parall= el >>>> 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/uti= l/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 i= s >>>>> 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 th= e >>>>> 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 i= t >>>>> 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 multipl= y >>>>> 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 nee= d >>>>> to be done in the CVS? Or can I do it in the OpenJDK GitHub repositor= y >>>>> 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.javaspeci= alists.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 >>>>> >>>> --000000000000a48d2e05d19e9a18 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"auto">Eg HotSpot as before:<div dir=3D"auto"><br></div><div dir= =3D"auto">Factorial, straightforward: 6.281s</div><div dir=3D"auto">Factori= al, try equalize work: 6.051s</div><div dir=3D"auto"><br></div><div dir=3D"= auto">GraalVM EE 20.2.0 (JDK 11 based):</div><div dir=3D"auto">5.278s and 4= .668s respectively for the same task.</div><div dir=3D"auto"><br></div><div= dir=3D"auto">Alex</div></div><br><div class=3D"gmail_quote"><div dir=3D"lt= r" class=3D"gmail_attr">On Thu, 25 Nov 2021, 15:18 Alex Otenko, <<a href= =3D"mailto:[email protected]">[email protected]</a>> 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"><div>Hi Hei= nz,<div dir=3D"auto"><br></div><div dir=3D"auto">I don't mind even if m= y version is left as an exercise for the reader - after all, I have no feel= of what the target audience can grasp.</div><div dir=3D"auto"><br></div><d= iv dir=3D"auto">As for your finding - that's interesting. I don't g= et 12x worse with (2x1024x1024)!, I always get mine a little faster (and fo= r some inputs quite a bit faster).</div><div dir=3D"auto"><br></div><div di= r=3D"auto">(HotSpot, 15.0.1+9-18 on Mac)</div><div dir=3D"auto"><br></div><= div dir=3D"auto">Alex</div><br><br><div class=3D"gmail_quote"><div dir=3D"l= tr" class=3D"gmail_attr">On Thu, 25 Nov 2021, 11:00 Dr Heinz M. Kabutz, <= ;<a href=3D"mailto:[email protected]" target=3D"_blank" rel=3D"noref= errer">[email protected]</a>> wrote:<br></div><blockquote class= =3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padd= ing-left:1ex"> =20 =20 =20 <div> <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 =3D 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 =3D 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 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 12:17, Alex Otenko wrote:<br> </div> <blockquote type=3D"cite"> =20 <div dir=3D"auto">Do we want to also nudge the reader towards considering how to split tasks into equally sized, if possible?=C2= =A0 <div dir=3D"auto"><br> </div> <div dir=3D"auto"><a href=3D"https://bit.ly/3HOH9Ca" rel=3D"norefer= rer noreferrer" target=3D"_blank">https://bit.ly/3HOH9Ca</a> - factorial is, of course, better done by ensuring both branches multiply numbers of similar magnitude.<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, 09:40 Alex Otenko, <<a href=3D"mailto:[email protected]" re= l=3D"noreferrer noreferrer" target=3D"_blank">[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 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:3= 8 Dr Heinz M. Kabutz, <<a href=3D"mailto:heinz@javaspecialis= ts.eu" rel=3D"noreferrer noreferrer noreferrer" target=3D"_blank">heinz@jav= aspecialists.eu</a>> wrote:<br> </div> <blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo= rder-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://gith= ub.com/openjdk/jdk/pull/6409" rel=3D"noreferrer noreferrer noreferrer noref= errer" target=3D"_blank">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" rel=3D"noreferrer noreferrer noreferre= r noreferrer" target=3D"_blank">www.javaspecialists.eu</a> Java Champion - <a href=3D"http://www.javachampions.org" rel=3D"noreferrer = noreferrer 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" re= l=3D"noreferrer noreferrer 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:concurren= [email protected]" rel=3D"noreferrer noreferrer noreferrer noreferr= er" target=3D"_blank">[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/java.base/java/util/concurrent/RecursiveTask.html" rel=3D"noreferr= er noreferrer noreferrer noreferrer noreferrer noreferrer" target=3D"_blank"= >https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/con= current/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 F= ibonacci(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 F= ibonacci(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'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 re= ferred 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 fr= om, 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 h= ref=3D"http://this.to" rel=3D"noreferrer noreferrer noreferrer noreferrer noreferrer norefer= rer" 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 (from + to) >>> 1;<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Fact= orialTask leftTask =3D new FactorialTask(from, mid);<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 Fact= orialTask rightTask =3D new FactorialTask(mid + 1, to);<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 left= Task.fork();<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BigI= nteger right =3D rightTask.invoke();<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 BigI= nteger left =3D leftTask.join();<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 retu= rn 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 fac= torialStream(int n) {<br> =C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0=C2=A0 retu= rn 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 retu= rn 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 Squa= res 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.inv= oke();<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.joi= n();<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 };<b= r> =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' Ne= wsletter" - <a href=3D"http://www.javaspecialists.eu" rel=3D"noreferre= r noreferrer noreferrer noreferrer noreferrer noreferrer" target=3D"_blank"= >www.javaspecialists.eu</a><br> Java Champion - <a href=3D"http://www.javachampions.o= rg" rel=3D"noreferrer noreferrer 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 noreferrer noreferrer" target=3D"_= blank">[email protected]</a><br> <a href=3D"http://cs.oswego.edu/mailman/listinfo/conc= urrency-interest" rel=3D"noreferrer noreferrer 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> </blockquote></div></div></div> </blockquote></div> --000000000000a48d2e05d19e9a18-- --===============1152685310397936414== 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 --===============1152685310397936414==--