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/publicdomain/zero/1.0/
 */

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

public final class DynamicLeftSpineFib extends RecursiveAction {

    static long lastStealCount;

    public static void main(String[] args) throws Exception {
        int 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 DynamicLeftSpineFib <threads> <number> [<sequntialThreshold>]");
            return;
        }

        for (int reps = 0; reps < 2; ++reps) {
            ForkJoinPool g = (procs == 0) ? ForkJoinPool.commonPool() :
                new ForkJoinPool(procs);
            lastStealCount = g.getStealCount();
            for (int i = 0; i < 20; ++i) {
                test(g, num);
            }
            System.out.println(g);
            if (g != ForkJoinPool.commonPool()) {
                g.shutdown();
                if (!g.awaitTermination(10, TimeUnit.SECONDS))
                    throw new Error();
            }
            Thread.sleep(1000);
        }
    }

    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("DLSFib " + 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 void compute() {
        number = fib(number);
    }

    static final int fib(int n) {
        if (n <= 1)
            return n;
        int r = 0;
        DynamicLeftSpineFib rt = null;
        while (getSurplusQueuedTaskCount() <= 3) {
            int m = n - 2;
            if (m <= 1)
                r += m;
            else
                (rt = new DynamicLeftSpineFib(m, rt)).fork();
            if (--n <= 1)
                break;
        }
        r += n <= 1 ? n : seqFib(n);
        if (rt != null)
            r += collectRights(rt);
        return r;
    }

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