test/loops/LeftSpineFib.java


import java.util.*;
import java.util.concurrent.*;

public final class LeftSpineFib extends RecursiveAction {

    // 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 LeftSpineFib <threads> <number> [<sequntialThreshold>]");
            return;
        }


        for (int reps = 0; reps < 2; ++reps) {
            ForkJoinPool g = (procs == 0) ? new ForkJoinPool() :
                new ForkJoinPool(procs);
            //            g.setMaintainsParallelism(false);
            lastStealCount = g.getStealCount();
            for (int i = 0; i < 20; ++i) {
                test(g, num);
                Thread.sleep(50);
            }
            System.out.println(g);
            g.shutdown();
            if (!g.awaitTermination(8, TimeUnit.SECONDS)) {
                System.out.println(g);
                throw new Error();
            }
            g = null;
            //            System.gc();
            Thread.sleep(500);
        }
    }

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


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

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

    int getAnswer() {
        return number;
    }

    public final void compute() {
        int n = number;
        if (n > 1) {
            LeftSpineFib rt = null;
            int r = 0;
            while (n > sequentialThreshold) {
                int m = n - 2;
                if (m <= 1)
                    r += m;
                else
                    (rt = new LeftSpineFib(m, rt)).fork();
                n -= 1;
            }
            r += n <= 1 ? n : seqFib(n);
            if (rt != null)
                r += collectRights(rt);
            number = r;
        }
    }

    static final int collectRights(LeftSpineFib rt) {
        int r = 0;
        while (rt != null) {
            LeftSpineFib rn = rt.next;
            rt.next = null;
            if (rt.tryUnfork()) rt.compute(); else rt.join();
            //            rt.join();
            r += rt.number;
            rt = rn;
        }
        return r;
    }

    // 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.3
Committed:	Mon Nov 29 20:58:07 2010 UTC (13 years, 5 months ago) by jsr166
Branch:	MAIN
CVS Tags:	release-1_7_0
Changes since 1.2:	+1 -1 lines
Log Message:	consistent ternary operator style
#	User	Rev	Content
1	dl	1.1
2			import java.util.*;
3			import java.util.concurrent.*;
4
5			public final class LeftSpineFib extends RecursiveAction {
6
7			// Performance-tuning constant:
8			static int sequentialThreshold;
9			static long lastStealCount;
10	jsr166	1.2
11	dl	1.1	public static void main(String[] args) throws Exception {
12			int procs = 0;
13			int num = 45;
14			sequentialThreshold = 2;
15			try {
16			if (args.length > 0)
17			procs = Integer.parseInt(args[0]);
18			if (args.length > 1)
19			num = Integer.parseInt(args[1]);
20	jsr166	1.2	if (args.length > 2)
21	dl	1.1	sequentialThreshold = Integer.parseInt(args[2]);
22			}
23			catch (Exception e) {
24			System.out.println("Usage: java LeftSpineFib <threads> <number> [<sequntialThreshold>]");
25			return;
26			}
27
28	jsr166	1.2
29	dl	1.1	for (int reps = 0; reps < 2; ++reps) {
30	jsr166	1.3	ForkJoinPool g = (procs == 0) ? new ForkJoinPool() :
31	dl	1.1	new ForkJoinPool(procs);
32			// g.setMaintainsParallelism(false);
33			lastStealCount = g.getStealCount();
34			for (int i = 0; i < 20; ++i) {
35			test(g, num);
36			Thread.sleep(50);
37			}
38			System.out.println(g);
39			g.shutdown();
40			if (!g.awaitTermination(8, TimeUnit.SECONDS)) {
41			System.out.println(g);
42			throw new Error();
43			}
44			g = null;
45			// System.gc();
46			Thread.sleep(500);
47			}
48			}
49
50			static void test(ForkJoinPool g, int num) throws Exception {
51			int ps = g.getParallelism();
52			long start = System.currentTimeMillis();
53			LeftSpineFib f = new LeftSpineFib(num, null);
54			g.invoke(f);
55			long time = System.currentTimeMillis() - start;
56			double secs = ((double)time) / 1000.0;
57			long result = f.getAnswer();
58			System.out.print("JLSFib " + num + " = " + result);
59			System.out.printf("\tTime: %7.3f", secs);
60			long sc = g.getStealCount();
61			long ns = sc - lastStealCount;
62			lastStealCount = sc;
63			System.out.printf(" Steals/t: %5d", ns/ps);
64			// System.out.printf(" Workers: %8d", g.getRunningThreadCount());
65			System.out.printf(" Workers: %8d", g.getPoolSize());
66			System.out.println();
67			}
68
69
70			// Initialized with argument; replaced with result
71			int number;
72			LeftSpineFib next;
73
74			LeftSpineFib(int n, LeftSpineFib nxt) { number = n; next = nxt; }
75
76			int getAnswer() {
77			return number;
78			}
79
80			public final void compute() {
81			int n = number;
82			if (n > 1) {
83			LeftSpineFib rt = null;
84			int r = 0;
85			while (n > sequentialThreshold) {
86			int m = n - 2;
87			if (m <= 1)
88			r += m;
89			else
90			(rt = new LeftSpineFib(m, rt)).fork();
91			n -= 1;
92			}
93			r += n <= 1 ? n : seqFib(n);
94			if (rt != null)
95			r += collectRights(rt);
96			number = r;
97			}
98			}
99
100			static final int collectRights(LeftSpineFib rt) {
101			int r = 0;
102			while (rt != null) {
103			LeftSpineFib rn = rt.next;
104			rt.next = null;
105			if (rt.tryUnfork()) rt.compute(); else rt.join();
106			// rt.join();
107			r += rt.number;
108			rt = rn;
109			}
110			return r;
111			}
112
113			// Sequential version for arguments less than threshold
114			static final int seqFib(int n) { // unroll left only
115			int r = 1;
116			do {
117			int m = n - 2;
118			r += m <= 1 ? m : seqFib(m);
119			} while (--n > 1);
120			return r;
121			}
122
123			}
124