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/licenses/publicdomain
 */

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

public final class DynamicLeftSpineFib extends RecursiveAction {

    // Performance-tuning constant:
    static long lastStealCount;

    public static void main(String[] args) throws Exception {
        int procs = 0;
        int num = 43;
        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 < 10; ++i) {
                test(g, num);
            }
            System.out.println(g);
            g.shutdown();
        }
    }

    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 final void compute() {
        int n = number;
        if (n > 1) {
            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();
            }
            r += seqFib(n);
            while (rt != null) {
                if (rt.tryUnfork()) rt.compute(); else rt.join();
                r += rt.number;
                rt = rt.next;
            }
            number = r;
        }
    }

    // Sequential version for arguments less than threshold
    static int seqFib(int n) {
        if (n <= 1)
            return n;
        else
            return seqFib(n-1) + seqFib(n-2);
    }

}

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