Re: Better RecursiveTask Example
Alex Otenko via Concurrency-interest <[email protected]> Fri, 26 Nov 2021 08:54:51 +0000
| Newsgroups | gmane.comp.java.jsr.166-concurrency |
|---|---|
| Message-ID | <CANkgWKjUt2N9dePgGKqEJxxxCCT4AF578qX1f-91TQWqrJ1+dg@mail.gmail.com> |
--===============3209604593362972223== Content-Type: multipart/alternative; boundary="0000000000002e012c05d1ad3f67" --0000000000002e012c05d1ad3f67 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable I am curious what's going on with your 12x observation. I may be wrong about why I observe the speedup, but my original thinking was to do that. Looking at the naive split of work, I was thinking: the left multiplies lots of small numbers, and the right multiplies lots of big numbers; that means the left is going to be done sooner, and some CPU will be idling. Of course, given that there will be a lot of tiny work created, it won't really be idling so much, so let's call it a hunch that it will have tendency to idle. So I thought let's split the work into even and odd numbers. Then left and right will be going through the numbers of similar magnitude, and bound to do similar amount of work. Then to keep splitting work, choose all divisible by 4 out of even, and those that aren't; then of those divisible by 4, half are divisible by 8, and half aren't, etc. Of course, no divisibility test is needed - just keep adding a step, so the procedure of splitting work is extensible to the odd numbers, too. If you notice, we actually end up multiplying a very small number and a very large one at first - say, 1 and 1 million. This is kind of against my premise that we multiply mostly equally sized numbers. But the idea is that the other branch is doing roughly the same - multiplying 2 and 1000001. This certainly is going to get us into Karatsuba range very quickly, too. So I really wonder why you are getting 12x worse numbers. If this isn't due to some additional debugging that wasn't commented out, I wonder if there is some strange fact about how the work gets split - eg do we get to juggle work that gets blocked more? 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 halv= es > 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 concer= n > 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 has > more to do with the computational time complexity than with Fork/Join. Wi= th > BigInteger, we want to get to large numbers as quickly as possible, so th= at > 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.javaspecialis= ts.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 task= s > 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 giv= e >> 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 parallelMultip= ly() >>> 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.javaspecial= ists.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 paralle= l >>> 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 (ther= e >>>> 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 t= o >>>> 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.javaspecia= lists.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 >>>> >>> --0000000000002e012c05d1ad3f67 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable <div dir=3D"auto">I am curious what's going on with your 12x observatio= n.=C2=A0<div dir=3D"auto"><br></div><div dir=3D"auto">I may be wrong about = why I observe the speedup, but my original thinking was to do that.</div><d= iv dir=3D"auto"><br></div><div dir=3D"auto">Looking at the naive split of w= ork, I was thinking: the left multiplies lots of small numbers, and the rig= ht multiplies lots of big numbers; that means the left is going to be done = sooner, and some CPU will be idling. Of course, given that there will be a = lot of tiny work created, it won't really be idling so much, so let'= ;s call it a hunch that it will have tendency to idle.</div><div dir=3D"aut= o"><br></div><div dir=3D"auto">So I thought let's split the work into e= ven and odd numbers. Then left and right will be going through the numbers = of similar magnitude, and bound to do similar amount of work. Then to keep = splitting work, choose all divisible by 4 out of even, and those that aren&= #39;t; then of those divisible by 4, half are divisible by 8, and half aren= 't, etc. Of course, no divisibility test is needed - just keep adding a= step, so the procedure of splitting work is extensible to the odd numbers,= too.</div><div dir=3D"auto"><br></div><div dir=3D"auto">If you notice, we = actually end up multiplying a very small number and a very large one at fir= st - say, 1 and 1 million. This is kind of against my premise that we multi= ply mostly equally sized numbers. But the idea is that the other branch is = doing roughly the same - multiplying 2 and 1000001. This certainly is going= to get us into Karatsuba range very quickly, too.</div><div dir=3D"auto"><= br></div><div dir=3D"auto">So I really wonder why you are getting 12x worse= numbers. If this isn't due to some additional debugging that wasn'= t commented out, I wonder if there is some strange fact about how the work = gets split - eg do we get to juggle work that gets blocked more?</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, 11:= 00 Dr Heinz M. Kabutz, <<a href=3D"mailto:[email protected]">hein= [email protected]</a>> wrote:<br></div><blockquote class=3D"gmail_quo= te" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-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" 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 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" target=3D"_bla= nk" rel=3D"noreferrer">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]" ta= rget=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 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" target=3D"_blank">heinz@javaspecialist= s.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" targ= et=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" target=3D"_blank">www.javaspecialists.eu</a> Java Champion - <a href=3D"http://www.javachampions.org" rel=3D"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" target=3D"_blank">https://bit.ly/3oV= FeTD</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" 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" target=3D"_blank">https://do= cs.oracle.com/en/java/javase/11/docs/api/java.base/java/util/concurrent/Rec= ursiveTask.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" 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" target=3D"_blank">www.javasp= ecialists.eu</a><br> Java Champion - <a href=3D"http://www.javachampions.o= rg" rel=3D"noreferrer noreferrer noreferrer noreferrer noreferrer" target=3D"_blank">www.javach= ampions.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" target=3D"_blank">Conc= [email protected]</a><br> <a href=3D"http://cs.oswego.edu/mailman/listinfo/conc= urrency-interest" rel=3D"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> --0000000000002e012c05d1ad3f67-- --===============3209604593362972223== 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 --===============3209604593362972223==--