test/loops/DynamicFib.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.*;

public final class DynamicFib extends RecursiveAction {
    static int procs;
    static long lastStealCount; // to display steal counts

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

    public static void main(String[] args) throws Exception {
        procs = 0;
        int num = 45;
        try {
            if (args.length > 0)
                procs = Integer.parseInt(args[0]);
            if (args.length > 1)
                num = Integer.parseInt(args[1]);
        }
        catch (Exception e) {
            System.out.println("Usage: java DynamicFib <threads> <number>");
            return;
        }
        for (int reps = 0; reps < 2; ++reps) {
            ForkJoinPool pool = (procs == 0) ? new ForkJoinPool() :
                new ForkJoinPool(procs);
            for (int i = 0; i < 20; ++i)
                test(pool, num);
            System.out.println(pool);
            pool.shutdown();
        }
    }

    static void test(ForkJoinPool pool, int num) throws Exception {
        int ps = pool.getParallelism();
        long start = System.nanoTime();
        DynamicFib f = new DynamicFib(num);
        pool.invoke(f);
        long time = System.nanoTime() - start;
        double secs = ((double)time) / NPS;
        long result = f.number;
        System.out.print("DynamicFib " + num + " = " + result);
        System.out.printf("\tTime: %9.3f", secs);
        long sc = pool.getStealCount();
        long ns = sc - lastStealCount;
        lastStealCount = sc;
        System.out.printf(" Steals: %4d", ns/ps);
        System.out.printf(" Workers: %4d", pool.getPoolSize());
        System.out.println();
    }


    int number;     // Initialized with argument; replaced with result
    DynamicFib(int n) { number = n; }
    public void compute() {
        number = fib(number);
    }

    static int fib(int n) {
        int res;
        if (n <= 1)
            res = n;
        else if (getSurplusQueuedTaskCount() >= 4)
            res = seqFib(n);
        else {
            DynamicFib f2 = new DynamicFib(n - 2);
            f2.fork();
            res = fib(n - 1);
            if (f2.tryUnfork())
                res += fib(n - 2);
            else {
                f2.quietlyJoin();
                res += f2.number;
            }
        }
        return res;
    }

    // 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:	Sat Feb 16 21:37:44 2013 UTC (11 years, 3 months ago) by jsr166
Branch:	MAIN
Changes since 1.4:	+6 -0 lines
Log Message:	add missing public domain notices
#	User	Rev	Content
1	jsr166	1.5	/*
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			public final class DynamicFib extends RecursiveAction {
10			static int procs;
11			static long lastStealCount; // to display steal counts
12
13			/** for time conversion */
14			static final long NPS = (1000L * 1000 * 1000);
15
16			public static void main(String[] args) throws Exception {
17			procs = 0;
18			int num = 45;
19			try {
20			if (args.length > 0)
21			procs = Integer.parseInt(args[0]);
22			if (args.length > 1)
23			num = Integer.parseInt(args[1]);
24			}
25			catch (Exception e) {
26			System.out.println("Usage: java DynamicFib <threads> <number>");
27			return;
28			}
29			for (int reps = 0; reps < 2; ++reps) {
30	jsr166	1.3	ForkJoinPool pool = (procs == 0) ? new ForkJoinPool() :
31	dl	1.1	new ForkJoinPool(procs);
32	jsr166	1.2	for (int i = 0; i < 20; ++i)
33	dl	1.1	test(pool, num);
34			System.out.println(pool);
35			pool.shutdown();
36			}
37			}
38
39			static void test(ForkJoinPool pool, int num) throws Exception {
40			int ps = pool.getParallelism();
41			long start = System.nanoTime();
42			DynamicFib f = new DynamicFib(num);
43			pool.invoke(f);
44			long time = System.nanoTime() - start;
45			double secs = ((double)time) / NPS;
46			long result = f.number;
47			System.out.print("DynamicFib " + num + " = " + result);
48			System.out.printf("\tTime: %9.3f", secs);
49			long sc = pool.getStealCount();
50			long ns = sc - lastStealCount;
51			lastStealCount = sc;
52			System.out.printf(" Steals: %4d", ns/ps);
53			System.out.printf(" Workers: %4d", pool.getPoolSize());
54			System.out.println();
55			}
56
57
58			int number; // Initialized with argument; replaced with result
59			DynamicFib(int n) { number = n; }
60	jsr166	1.2	public void compute() {
61			number = fib(number);
62	dl	1.1	}
63
64			static int fib(int n) {
65			int res;
66	jsr166	1.2	if (n <= 1)
67	dl	1.1	res = n;
68			else if (getSurplusQueuedTaskCount() >= 4)
69			res = seqFib(n);
70			else {
71			DynamicFib f2 = new DynamicFib(n - 2);
72			f2.fork();
73			res = fib(n - 1);
74			if (f2.tryUnfork())
75			res += fib(n - 2);
76			else {
77			f2.quietlyJoin();
78			res += f2.number;
79			}
80			}
81			return res;
82			}
83
84			// Sequential version for arguments less than threshold
85			static final int seqFib(int n) { // unroll left only
86			int r = 1;
87			do {
88			int m = n - 2;
89			r += m <= 1 ? m : seqFib(m);
90			} while (--n > 1);
91			return r;
92			}
93
94			}