1

I am playing with RecursiveTask of the concurrent package from Java 7. It says this class has an implementation of forkJoin approach and can split my tasks in different threads. So I used a fibonacci example from the Java doc and compared the execution time with a normal recursive fibonacci. And for my surprise the normal recursive took less time! Why? Am I doing anything wrong?

import java.util.concurrent.RecursiveTask;

public class FibonacciJava extends RecursiveTask<Long> {

    private static final long serialVersionUID = -2495228492435217747L;

    private long n;

    protected long valor;

    public FibonacciJava(long n) {
        this.n = n;
    }

    @Override
    protected Long compute() {
        if (n <= 1) {
            return n;
        }
        FibonacciJava f1 = new FibonacciJava(n - 1);
        f1.fork();
        FibonacciJava f2 = new FibonacciJava(n - 2);
        return f2.compute() + f1.join();
    }

    public long fibonacci(long valor) {
        if (valor <= 1)
            return valor;
        else {
            return fibonacci(valor - 1) + fibonacci(valor - 2);
        }
    }

    public static void main(String[] args) {

        long value = 40;

        FibonacciJava fibonacciJava = new FibonacciJava(value);

        long startTimeMillis = System.currentTimeMillis();
        System.out.println("RecursiveTask FibonacciJava: "
                + fibonacciJava.compute() + " in "
                + (System.currentTimeMillis() - startTimeMillis)
                + " miliseconds.");

        startTimeMillis = System.currentTimeMillis();
        System.out.println("Recursive FibonacciJava: "
                + fibonacciJava.fibonacci(value) + " in "
                + (System.currentTimeMillis() - startTimeMillis)
                + " miliseconds.");
    }
}

time:

RecursiveTask FibonacciJava: 102334155 in 3681 miliseconds.
Recursive FibonacciJava: 102334155 in 573 miliseconds.
Felipe
  • 7,013
  • 8
  • 44
  • 102
  • How many processors do you have? Have you tested with higher values? – shmosel Jan 30 '17 at 23:00
  • I have 4 cores on my machine. If I test with Fibonacci(50) it takes too long and I gave up. – Felipe Jan 30 '17 at 23:03
  • 3
    According to the SE 8 doc: "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." I suspect this is because fibionnaci is not a good use for what appears to be a very random feature of Java. – SomeStudent Jan 30 '17 at 23:05
  • 1
    I agree with the others. To use the full power of fork/join you need to have clear values to operate on which do not rely on eachother. For instance you have a list of 5 Million numbers and you want do determine the sum. Then fork/join would really improve the speed of computation, as each thread can operate independently on its small part of the list. With Fibonacci you have the Problem that you had to know in advance with which number the next thread was supposed to start. That's impossible. –  Jan 30 '17 at 23:22
  • Thanks, I will create another program to test fork/join with a list predetermined. – Felipe Jan 31 '17 at 08:48

0 Answers0