test/loops/FibTask.java

import java.util.concurrent.*;

/**
 * Recursive task-based version of Fibonacci. Computes:
 * <pre>
 * Computes fibonacci(n) = fibonacci(n-1) + fibonacci(n-2);  for n> 1
 *          fibonacci(0) = 0;
 *          fibonacci(1) = 1.
 * </pre>
 */
public final class FibTask extends RecursiveTask<Integer> {

    // Performance-tuning constant:
    static int sequentialThreshold;

    static long lastStealCount;

    public static void main(String[] args) throws Exception {
        int procs = 0;
        int num = 45;
        sequentialThreshold = 2;
        try {
            if (args.length > 0)
                procs = Integer.parseInt(args[0]);
            if (args.length > 1)
                num = Integer.parseInt(args[1]);
            if (args.length > 2)
                sequentialThreshold = Integer.parseInt(args[2]);
        }
        catch (Exception e) {
            System.out.println("Usage: java Fib <threads> <number> [<sequentialThreshold>]");
            return;
        }

        for (int reps = 0; reps < 2; ++reps) {
            ForkJoinPool g = (procs == 0) ? new ForkJoinPool() :
                new ForkJoinPool(procs);
            lastStealCount = g.getStealCount();
            for (int i = 0; i < 20; ++i) {
                test(g, num);
                //            Thread.sleep(1000);
            }
            System.out.println(g);
            g.shutdown();
        }
    }


    /** for time conversion */
    static final long NPS = (1000L * 1000 * 1000);

    static void test(ForkJoinPool g, int num) throws Exception {
        int ps = g.getParallelism();
        long start = System.nanoTime();
        int result = g.invoke(new FibTask(num));
        long time = System.nanoTime() - start;
        double secs = ((double)time) / NPS;
        System.out.print("FibTask " + num + " = " + result);
        System.out.printf("\tTime: %7.3f", secs);

        long sc = g.getStealCount();
        long ns = sc - lastStealCount;
        lastStealCount = sc;
        System.out.printf(" Steals/t: %5d", ns/ps);
        System.out.printf(" Workers: %5d", g.getPoolSize());
        System.out.println();
    }


    // Initialized with argument; replaced with result
    int number;

    FibTask(int n) { number = n; }

    public Integer compute() {
        int n = number;

        // Handle base cases:
        if (n <= 1) {
            return n;
        }
        // Use sequential code for small problems:
        else if (n <= sequentialThreshold) {
            return seqFib(n);
        }
        // Otherwise use recursive parallel decomposition:
        else {
            FibTask f1 = new FibTask(n - 1);
            f1.fork();
            FibTask f2 = new FibTask(n - 2);
            return f2.compute() + f1.join();
        }
    }

    // Sequential version for arguments less than threshold
    static final int seqFib(int n) { // unroll left only
        int r = 1;
        do {
            int m = n - 2;
            r += m <= 1 ? m : seqFib(m);
        } while (--n > 1);
        return r;
    }
}
Revision:	1.5
Committed:	Wed Jul 4 20:07:01 2012 UTC (11 years, 10 months ago) by jsr166
Branch:	MAIN
Changes since 1.4:	+0 -1 lines
Log Message:	trailing newlines
#	Content
1	import java.util.concurrent.*;
2
3	/**
4	* Recursive task-based version of Fibonacci. Computes:
5	* <pre>
6	* Computes fibonacci(n) = fibonacci(n-1) + fibonacci(n-2); for n> 1
7	* fibonacci(0) = 0;
8	* fibonacci(1) = 1.
9	* </pre>
10	*/
11	public final class FibTask extends RecursiveTask<Integer> {
12
13	// Performance-tuning constant:
14	static int sequentialThreshold;
15
16	static long lastStealCount;
17
18	public static void main(String[] args) throws Exception {
19	int procs = 0;
20	int num = 45;
21	sequentialThreshold = 2;
22	try {
23	if (args.length > 0)
24	procs = Integer.parseInt(args[0]);
25	if (args.length > 1)
26	num = Integer.parseInt(args[1]);
27	if (args.length > 2)
28	sequentialThreshold = Integer.parseInt(args[2]);
29	}
30	catch (Exception e) {
31	System.out.println("Usage: java Fib <threads> <number> [<sequentialThreshold>]");
32	return;
33	}
34
35	for (int reps = 0; reps < 2; ++reps) {
36	ForkJoinPool g = (procs == 0) ? new ForkJoinPool() :
37	new ForkJoinPool(procs);
38	lastStealCount = g.getStealCount();
39	for (int i = 0; i < 20; ++i) {
40	test(g, num);
41	// Thread.sleep(1000);
42	}
43	System.out.println(g);
44	g.shutdown();
45	}
46	}
47
48
49	/** for time conversion */
50	static final long NPS = (1000L * 1000 * 1000);
51
52	static void test(ForkJoinPool g, int num) throws Exception {
53	int ps = g.getParallelism();
54	long start = System.nanoTime();
55	int result = g.invoke(new FibTask(num));
56	long time = System.nanoTime() - start;
57	double secs = ((double)time) / NPS;
58	System.out.print("FibTask " + num + " = " + result);
59	System.out.printf("\tTime: %7.3f", secs);
60
61	long sc = g.getStealCount();
62	long ns = sc - lastStealCount;
63	lastStealCount = sc;
64	System.out.printf(" Steals/t: %5d", ns/ps);
65	System.out.printf(" Workers: %5d", g.getPoolSize());
66	System.out.println();
67	}
68
69
70	// Initialized with argument; replaced with result
71	int number;
72
73	FibTask(int n) { number = n; }
74
75	public Integer compute() {
76	int n = number;
77
78	// Handle base cases:
79	if (n <= 1) {
80	return n;
81	}
82	// Use sequential code for small problems:
83	else if (n <= sequentialThreshold) {
84	return seqFib(n);
85	}
86	// Otherwise use recursive parallel decomposition:
87	else {
88	FibTask f1 = new FibTask(n - 1);
89	f1.fork();
90	FibTask f2 = new FibTask(n - 2);
91	return f2.compute() + f1.join();
92	}
93	}
94
95	// Sequential version for arguments less than threshold
96	static final int seqFib(int n) { // unroll left only
97	int r = 1;
98	do {
99	int m = n - 2;
100	r += m <= 1 ? m : seqFib(m);
101	} while (--n > 1);
102	return r;
103	}
104	}