test/loops/FibTask.java

/*
 * Written by Doug Lea with assistance from members of JCP JSR-166
 * Expert Group and released to the public domain, as explained at
 * http://creativecommons.org/publicdomain/zero/1.0/
 */

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