test/loops/DynamicLeftSpineFib.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/licenses/publicdomain
 */

//import jsr166y.*;
import java.util.*;
import java.util.concurrent.*;

public final class DynamicLeftSpineFib extends RecursiveAction {

    // Performance-tuning constant:
    static long lastStealCount;

    public static void main(String[] args) throws Exception {
        int procs = 0;
        int num = 43;
        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 DynamicLeftSpineFib <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 < 10; ++i) {
                test(g, num);
            }
            System.out.println(g);
            g.shutdown();
        }
    }

    static void test(ForkJoinPool g, int num) throws Exception {
        int ps = g.getParallelism();
        long start = System.currentTimeMillis();
        DynamicLeftSpineFib f = new DynamicLeftSpineFib(num, null);
        g.invoke(f);
        long time = System.currentTimeMillis() - start;
        double secs = (double) time / 1000.0;
        long result = f.getAnswer();
        System.out.print("DynamicLeftSpineFib " + 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: %8d", g.getPoolSize());
        System.out.println();
    }


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

    DynamicLeftSpineFib(int n, DynamicLeftSpineFib nxt) {
        number = n; next = nxt;
    }

    int getAnswer() {
        return number;
    }

    public final void compute() {
        int n = number;
        if (n > 1) {
            DynamicLeftSpineFib rt = null;
            while (n > 1 && getSurplusQueuedTaskCount() <= 3) {
                (rt = new DynamicLeftSpineFib(n - 2, rt)).fork();
                n -= 1;
            }
            int r = seqFib(n);
            while (rt != null) {
                if (rt.tryUnfork()) rt.compute(); else rt.helpJoin();
                r += rt.number;
                rt = rt.next;
            }
            number = r;
        }
    }

    // Sequential version for arguments less than threshold
    static int seqFib(int n) {
        if (n <= 1)
            return n;
        else
            return seqFib(n-1) + seqFib(n-2);
    }

}
Revision:	1.6
Committed:	Tue Nov 3 01:04:02 2009 UTC (14 years, 6 months ago) by jsr166
Branch:	MAIN
Changes since 1.5:	+1 -1 lines
Log Message:	coding style
#	User	Rev	Content
1	dl	1.4	/*
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/licenses/publicdomain
5			*/
6
7	dl	1.1	//import jsr166y.*;
8			import java.util.*;
9			import java.util.concurrent.*;
10
11			public final class DynamicLeftSpineFib extends RecursiveAction {
12
13			// Performance-tuning constant:
14			static long lastStealCount;
15	jsr166	1.2
16	dl	1.1	public static void main(String[] args) throws Exception {
17			int procs = 0;
18			int num = 43;
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	jsr166	1.3	System.out.println("Usage: java DynamicLeftSpineFib <threads> <number> [<sequentialThreshold>]");
27	dl	1.1	return;
28			}
29
30	jsr166	1.2
31	dl	1.1	for (int reps = 0; reps < 2; ++reps) {
32	jsr166	1.5	ForkJoinPool g = (procs == 0) ?
33			new ForkJoinPool() :
34	dl	1.1	new ForkJoinPool(procs);
35			lastStealCount = g.getStealCount();
36			for (int i = 0; i < 10; ++i) {
37			test(g, num);
38			}
39			System.out.println(g);
40			g.shutdown();
41			}
42			}
43
44			static void test(ForkJoinPool g, int num) throws Exception {
45			int ps = g.getParallelism();
46			long start = System.currentTimeMillis();
47			DynamicLeftSpineFib f = new DynamicLeftSpineFib(num, null);
48			g.invoke(f);
49			long time = System.currentTimeMillis() - start;
50	jsr166	1.6	double secs = (double) time / 1000.0;
51	dl	1.1	long result = f.getAnswer();
52			System.out.print("DynamicLeftSpineFib " + num + " = " + result);
53			System.out.printf("\tTime: %7.3f", secs);
54			long sc = g.getStealCount();
55			long ns = sc - lastStealCount;
56			lastStealCount = sc;
57			System.out.printf(" Steals/t: %5d", ns/ps);
58			System.out.printf(" Workers: %8d", g.getPoolSize());
59			System.out.println();
60			}
61
62
63			// Initialized with argument; replaced with result
64			int number;
65			DynamicLeftSpineFib next;
66
67	jsr166	1.2	DynamicLeftSpineFib(int n, DynamicLeftSpineFib nxt) {
68			number = n; next = nxt;
69	dl	1.1	}
70
71			int getAnswer() {
72			return number;
73			}
74
75			public final void compute() {
76			int n = number;
77			if (n > 1) {
78			DynamicLeftSpineFib rt = null;
79			while (n > 1 && getSurplusQueuedTaskCount() <= 3) {
80			(rt = new DynamicLeftSpineFib(n - 2, rt)).fork();
81			n -= 1;
82			}
83			int r = seqFib(n);
84			while (rt != null) {
85			if (rt.tryUnfork()) rt.compute(); else rt.helpJoin();
86			r += rt.number;
87			rt = rt.next;
88			}
89			number = r;
90			}
91			}
92
93			// Sequential version for arguments less than threshold
94			static int seqFib(int n) {
95	jsr166	1.2	if (n <= 1)
96	dl	1.1	return n;
97	jsr166	1.2	else
98	dl	1.1	return seqFib(n-1) + seqFib(n-2);
99			}
100	jsr166	1.2
101	dl	1.1	}