RecursiveAction Benchmarking

README.md

Recursive Fibonacci Code

For n = 42, fib(n) = 267914296

ForkJoinPoolFibonacci.java

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class ForkJoinPoolFibonacci extends RecursiveAction {

    private int n;
    private int result;

    public ForkJoinPoolFibonacci(int n) {
        this.n = n;
    }

    @Override
    public void compute() {
        if (n <= 2) {
            result = 1;
        } else {
            ForkJoinPoolFibonacci left = new ForkJoinPoolFibonacci(n - 1);
            ForkJoinPoolFibonacci right = new ForkJoinPoolFibonacci(n - 2);

            left.fork();
            right.fork();
            left.join();
            right.join();

            result = left.result + right.result;
        }
    }

    public static void main(String[] args) {
        int iterations = 10;
        float seconds = 0;

        for (int i = 0; i < iterations; i++) {
            long start = System.currentTimeMillis();

            ForkJoinPool forkJoinPool = new ForkJoinPool(4);
            ForkJoinPoolFibonacci fibonacci = new ForkJoinPoolFibonacci(42);
            forkJoinPool.invoke(fibonacci);

            long end = System.currentTimeMillis();
            float delta = (end - start);
            seconds += delta / 1000;

            System.out.println(fibonacci.result + ", Time: " + Float.toString(delta / 1000) + "s");
        }

        System.out.println("Average Execution Time for " + Integer.toString(iterations) + " iterations:");
        System.out.println((seconds / iterations) + "s");
    }
}

ForkJoinPoolFibonacci.txt

267914296, Time: 13.33s
267914296, Time: 13.829s
267914296, Time: 14.673s
267914296, Time: 14.197s
267914296, Time: 15.631s
267914296, Time: 14.342s
267914296, Time: 14.079s
267914296, Time: 15.281s
267914296, Time: 16.148s
267914296, Time: 14.281s
Average Execution Time for 10 iterations:
14.5791s

ForkJoinPoolFibonacciWithThreshold.java

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

public class ForkJoinPoolFibonacciWithThreshold extends RecursiveAction {

    private static int threshold = 30;

    private int n;
    private int result;

    public ForkJoinPoolFibonacciWithThreshold(int n) {
        this.n = n;
    }

    public static int fib(int n) {
        if (n <= 2) {
            return 1;
        } else {
            return fib(n - 1) + fib(n - 2);
        }
    }

    @Override
    public void compute() {
        if (n <= threshold) {
            result = fib(n);
        } else {
            ForkJoinPoolFibonacciWithThreshold left = new ForkJoinPoolFibonacciWithThreshold(n - 1);
            ForkJoinPoolFibonacciWithThreshold right = new ForkJoinPoolFibonacciWithThreshold(n - 2);

            left.fork();
            right.fork();
            left.join();
            right.join();

            result = left.result + right.result;
        }
    }

    public static void main(String[] args) {
        int iterations = 10;
        float seconds = 0;

        for (int i = 0; i < iterations; i++) {
            long start = System.currentTimeMillis();

            ForkJoinPool forkJoinPool = new ForkJoinPool(4);
            ForkJoinPoolFibonacciWithThreshold fibonacci = new ForkJoinPoolFibonacciWithThreshold(42);
            forkJoinPool.invoke(fibonacci);

            long end = System.currentTimeMillis();
            float delta = (end - start);
            seconds += delta / 1000;

            System.out.println(fibonacci.result + ", Time: " + Float.toString(delta / 1000) + "s");
        }

        System.out.println("Average Execution Time for " + Integer.toString(iterations) + " iterations:");
        System.out.println((seconds / iterations) + "s");
    }
}

ForkJoinPoolFibonacciWithThreshold.txt

267914296, Time: 0.439s
267914296, Time: 0.398s
267914296, Time: 0.383s
267914296, Time: 0.443s
267914296, Time: 0.471s
267914296, Time: 0.342s
267914296, Time: 0.327s
267914296, Time: 0.423s
267914296, Time: 0.339s
267914296, Time: 0.323s
Average Execution Time for 10 iterations:
0.3888s

SequentialFibonacci.java

public class SequentialFibonacci {

    private int n;
    private int result;

    public SequentialFibonacci(int n) {
        this.n = n;
        result = 0;
    }

    public void compute() {
        if (n <= 2) {
            result = 1;
        } else {
            SequentialFibonacci left = new SequentialFibonacci(n - 1);
            SequentialFibonacci right = new SequentialFibonacci(n - 2);

            left.compute();
            right.compute();

            result = left.result + right.result;
        }
    }

    public static void main(String[] args) {
        int iterations = 10;
        float seconds = 0;

        for (int i = 0; i < iterations; i++) {
            long start = System.currentTimeMillis();

            SequentialFibonacci fib42 = new SequentialFibonacci(42);
            fib42.compute();

            long end = System.currentTimeMillis();
            float delta = (end - start);
            seconds += delta / 1000;

            System.out.println(fib42.result + ", Time: " + Float.toString(delta / 1000) + "s");
        }

        System.out.println("Average Execution Time for " + Integer.toString(iterations) + " iterations:");
        System.out.println((seconds / iterations) + "s");
    }
}

SequentialFibonacci.txt

267914296, Time: 2.004s
267914296, Time: 1.344s
267914296, Time: 1.36s
267914296, Time: 1.407s
267914296, Time: 1.393s
267914296, Time: 1.375s
267914296, Time: 1.366s
267914296, Time: 1.361s
267914296, Time: 1.376s
267914296, Time: 1.359s
Average Execution Time for 10 iterations:
1.4345001s