fork/join计算Fibonacci数测试性能问题

一、说明

Java 并发之 Fork/Join一文中尝试了一个计算Fibonacci数的例子。即根据Fibonacci数的

Fibonacci(n)=Fibonacci(n-1)+Fibonacci(n-2)

的递归特征,使用Fork/Join框架来对任务进行分解,创建子任务来执行。本来只是想示例一下功能。在写main函数调用的时候又顺手写了个传统递归的执行方式,Fibonacci的递归太典型了。想“欣赏”下,在Fork/Join框架下采用并发方式进行执行的优越性。但是结果却和期望大相径庭

原因待分析,问题先记录下来。

二、代码:

1. 一个RecursiveTask,可以返回每次计算的值。

2. 调用入口main函数,顺便再改类中写了个递归计算的方法calculateFibonacciByIterate()。在main函数中比较两种方法分别计算第n个Fibonacci数所花费的时间。

?三、执行结果输出。

| Fibonacci[itet](1) = 1 | Takes: 0millis
| Fibonacci[fork](1) = 1 | Takes: 16millis
| Fibonacci[itet](2) = 2 | Takes: 0millis
| Fibonacci[fork](2) = 2 | Takes: 0millis
| Fibonacci[itet](3) = 3 | Takes: 0millis
| Fibonacci[fork](3) = 3 | Takes: 0millis
| Fibonacci[itet](4) = 5 | Takes: 0millis
| Fibonacci[fork](4) = 5 | Takes: 0millis
| Fibonacci[itet](5) = 8 | Takes: 0millis
| Fibonacci[fork](5) = 8 | Takes: 0millis
| Fibonacci[itet](6) = 13 | Takes: 0millis
| Fibonacci[fork](6) = 13 | Takes: 0millis
| Fibonacci[itet](7) = 21 | Takes: 0millis
| Fibonacci[fork](7) = 21 | Takes: 0millis
| Fibonacci[itet](8) = 34 | Takes: 0millis
| Fibonacci[fork](8) = 34 | Takes: 0millis
| Fibonacci[itet](9) = 55 | Takes: 0millis
| Fibonacci[fork](9) = 55 | Takes: 0millis
| Fibonacci[itet](10) = 89 | Takes: 0millis
| Fibonacci[fork](10) = 89 | Takes: 0millis
| Fibonacci[itet](11) = 144 | Takes: 0millis
| Fibonacci[fork](11) = 144 | Takes: 0millis
| Fibonacci[itet](12) = 233 | Takes: 0millis
| Fibonacci[fork](12) = 233 | Takes: 0millis
| Fibonacci[itet](13) = 377 | Takes: 0millis
| Fibonacci[fork](13) = 377 | Takes: 0millis
| Fibonacci[itet](14) = 610 | Takes: 0millis
| Fibonacci[fork](14) = 610 | Takes: 0millis
| Fibonacci[itet](15) = 987 | Takes: 0millis
| Fibonacci[fork](15) = 987 | Takes: 31millis
| Fibonacci[itet](16) = 1597 | Takes: 0millis
| Fibonacci[fork](16) = 1597 | Takes: 16millis
| Fibonacci[itet](17) = 2584 | Takes: 0millis
| Fibonacci[fork](17) = 2584 | Takes: 0millis
| Fibonacci[itet](18) = 4181 | Takes: 0millis
| Fibonacci[fork](18) = 4181 | Takes: 15millis
| Fibonacci[itet](19) = 6765 | Takes: 0millis
| Fibonacci[fork](19) = 6765 | Takes: 16millis
| Fibonacci[itet](20) = 10946 | Takes: 0millis
| Fibonacci[fork](20) = 10946 | Takes: 16millis
| Fibonacci[itet](21) = 17711 | Takes: 0millis
| Fibonacci[fork](21) = 17711 | Takes: 46millis
| Fibonacci[itet](22) = 28657 | Takes: 0millis
| Fibonacci[fork](22) = 28657 | Takes: 891millis
| Fibonacci[itet](23) = 46368 | Takes: 0millis
| Fibonacci[fork](23) = 46368 | Takes: 94millis
| Fibonacci[itet](24) = 75025 | Takes: 0millis
| Fibonacci[fork](24) = 75025 | Takes: 156millis
| Fibonacci[itet](25) = 121393 | Takes: 0millis
| Fibonacci[fork](25) = 121393 | Takes: 422millis
| Fibonacci[itet](26) = 196418 | Takes: 16millis
| Fibonacci[fork](26) = 196418 | Takes: 4531millis
| Fibonacci[itet](27) = 317811 | Takes: 0millis
| Fibonacci[fork](27) = 317811 | Takes: 10516millis
| Fibonacci[itet](28) = 514229 | Takes: 15millis
java.util.concurrent.ExecutionException: java.lang.OutOfMemoryError
at java.util.concurrent.ForkJoinTask.get(Unknown Source)
at ibm.idouba.forkjoin.recursiveActionRetrun.CompareFibo.calculateFibonacciByForkJoin(CompareFibo.java:19)
at ibm.idouba.forkjoin.recursiveActionRetrun.CompareFibo.main(CompareFibo.java:78)
Caused by: java.lang.OutOfMemoryError
at sun.reflect.GeneratedConstructorAccessor1.newInstance(Unknown Source)
at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(Unknown Source)
at java.lang.reflect.Constructor.newInstance(Unknown Source)
at java.util.concurrent.ForkJoinTask.getThrowableException(Unknown Source)
… 3 more
Caused by: java.lang.OutOfMemoryError
at sun.reflect.GeneratedConstructorAccessor1.newInstance(Unknown Source)
at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(Unknown Source)
at java.lang.reflect.Constructor.newInstance(Unknown Source)
at java.util.concurrent.ForkJoinTask.getThrowableException(Unknown Source)
at java.util.concurrent.ForkJoinTask.reportResult(Unknown Source)
at java.util.concurrent.ForkJoinTask.join(Unknown Source)
at ibm.idouba.forkjoin.recursiveActionRetrun.FibonacciTask.compute(FibonacciTask.java:30)
at ibm.idouba.forkjoin.recursiveActionRetrun.FibonacciTask.compute(FibonacciTask.java:1)
at java.util.concurrent.RecursiveTask.exec(Unknown Source)
at java.util.concurrent.ForkJoinTask.doExec(Unknown Source)
at java.util.concurrent.ForkJoinWorkerThread.execTask(Unknown Source)
at java.util.concurrent.ForkJoinPool.scan(Unknown Source)
at java.util.concurrent.ForkJoinPool.work(Unknown Source)
at java.util.concurrent.ForkJoinWorkerThread.run(Unknown Source)
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError: unable to create new native thread
at java.lang.Thread.start0(Native Method)
at java.lang.Thread.start(Unknown Source)
at java.util.concurrent.ForkJoinPool.addWorker(Unknown Source)
at java.util.concurrent.ForkJoinPool.tryPreBlock(Unknown Source)
at java.util.concurrent.ForkJoinPool.tryAwaitJoin(Unknown Source)
at java.util.concurrent.ForkJoinWorkerThread.joinTask(Unknown Source)
at java.util.concurrent.ForkJoinTask.doJoin(Unknown Source)
… 9 more
java.util.concurrent.ExecutionException: java.lang.OutOfMemoryError
at java.util.concurrent.ForkJoinTask.get(Unknown Source)
at ibm.idouba.forkjoin.recursiveActionRetrun.CompareFibo.calculateFibonacciByForkJoin(CompareFibo.java:19)
at ibm.idouba.forkjoin.recursiveActionRetrun.CompareFibo.main(CompareFibo.java:78)
Caused by: java.lang.OutOfMemoryError
at sun.reflect.GeneratedConstructorAccessor1.newInstance(Unknown Source)
at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(Unknown Source)
at java.lang.reflect.Constructor.newInstance(Unknown Source)
at java.util.concurrent.ForkJoinTask.getThrowableException(Unknown Source)
… 3 more
Caused by: java.lang.OutOfMemoryError
at sun.reflect.GeneratedConstructorAccessor1.newInstance(Unknown Source)
at sun.reflect.DelegatingConstructorAccessorImpl.newInstance(Unknown Source)
at java.lang.reflect.Constructor.newInstance(Unknown Source)
at java.util.concurrent.ForkJoinTask.getThrowableException(Unknown Source)
at java.util.concurrent.ForkJoinTask.reportResult(Unknown Source)
at java.util.concurrent.ForkJoinTask.join(Unknown Source)
at ibm.idouba.forkjoin.recursiveActionRetrun.FibonacciTask.compute(FibonacciTask.java:30)
at ibm.idouba.forkjoin.recursiveActionRetrun.FibonacciTask.compute(FibonacciTask.java:1)
at java.util.concurrent.RecursiveTask.exec(Unknown Source)
at java.util.concurrent.ForkJoinTask.doExec(Unknown Source)
at java.util.concurrent.ForkJoinWorkerThread.execTask(Unknown Source)
at java.util.concurrent.ForkJoinPool.scan(Unknown Source)
at java.util.concurrent.ForkJoinPool.work(Unknown Source)
at java.util.concurrent.ForkJoinWorkerThread.run(Unknown Source)
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError
… 14 more
Caused by: java.lang.OutOfMemoryError: unable to create new native thread
at java.lang.Thread.start0(Native Method)
at java.lang.Thread.start(Unknown Source)
at java.util.concurrent.ForkJoinPool.addWorker(Unknown Source)
at java.util.concurrent.ForkJoinPool.tryPreBlock(Unknown Source)
at java.util.concurrent.ForkJoinPool.tryAwaitJoin(Unknown Source)
at java.util.concurrent.ForkJoinWorkerThread.joinTask(Unknown Source)
at java.util.concurrent.ForkJoinTask.doJoin(Unknown Source)
… 9 more
| Fibonacci[fork](28) = -1 | Takes: 46188millis
| Fibonacci[itet](29) = 832040 | Takes: 0millis
| Fibonacci[fork](29) = -1 | Takes: 4594millis

四、分析

在实验中计算第0到30个Fibonacci数的比较中递归算法的时间消耗都比for/join快的多,如:| Fibonacci[itet](27) = 317811 | Takes: 0millis
| Fibonacci[fork](27) = 317811 | Takes: 10516millis显示计算第27个Fibonacci数时传统递归还是0毫秒,而fork/join需要10516毫秒。

而在计算第30个的时候for/join资源不够报错了,没有能计算出结果来。

感觉是不是有点像在做一个很简单的事情,用了简单的老办法很快有效,一堆人期待着引进了一个高级方法,但却在这个小地方拉不开架势,更别提效率了。

 

 

原创文章。为了维护文章的版本一致、最新、可追溯,转载请注明: 转载自idouba

本文链接地址: fork/join计算Fibonacci数测试性能问题


,

No comments yet.

发表评论