test/loops/DynamicLeftSpineFib.java

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