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