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.4
Committed:	Mon Nov 29 20:58:06 2010 UTC (13 years, 5 months ago) by jsr166
Branch:	MAIN
CVS Tags:	release-1_7_0
Changes since 1.3:	+1 -1 lines
Log Message:	consistent ternary operator style
#	User	Rev	Content
1	dl	1.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	jsr166	1.2	* fibonacci(0) = 0;
8			* fibonacci(1) = 1.
9	dl	1.1	* </pre>
10	jsr166	1.3	*/
11	dl	1.1	public final class FibTask extends RecursiveTask<Integer> {
12
13			// Performance-tuning constant:
14			static int sequentialThreshold;
15
16			static long lastStealCount;
17	jsr166	1.2
18	dl	1.1	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	jsr166	1.2	if (args.length > 2)
28	dl	1.1	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	jsr166	1.4	ForkJoinPool g = (procs == 0) ? new ForkJoinPool() :
37	dl	1.1	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	jsr166	1.2
61	dl	1.1	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	jsr166	1.2	return f2.compute() + f1.join();
92	dl	1.1	}
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			}
105