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