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