test/loops/CCFib.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/
 */

// A CountedCompleter version of Fibonacci

import java.util.concurrent.*;

public abstract class CCFib extends CountedCompleter {
    static int sequentialThreshold;
    int number;
    int rnumber;

    public CCFib(CountedCompleter parent, int n) {
        super(parent, 1);
        this.number = n;
    }

    public final void compute() {
        CountedCompleter p;
        CCFib f = this;
        int n = number;
        while (n > sequentialThreshold) {
            new RCCFib(f, n - 2).fork();
            f = new LCCFib(f, --n);
        }
        f.number = (n <= 1) ? n : seqFib(n);
        f.onCompletion(f);
        if ((p = f.getCompleter()) != null)
            p.tryComplete();
        else
            f.quietlyComplete();
    }

    static final class LCCFib extends CCFib {
        public LCCFib(CountedCompleter parent, int n) {
            super(parent, n);
        }
        public final void onCompletion(CountedCompleter caller) {
            CCFib p = (CCFib)getCompleter();
            int n = number + rnumber;
            if (p != null)
                p.number = n;
            else
                number = n;
        }
    }

    static final class RCCFib extends CCFib {
        public RCCFib(CountedCompleter parent, int n) {
            super(parent, n);
        }
        public final void onCompletion(CountedCompleter caller) {
            CCFib p = (CCFib)getCompleter();
            int n = number + rnumber;
            if (p != null)
                p.rnumber = n;
            else
                number = n;
        }
    }

    static long lastStealCount;

    public static void main(String[] args) throws Exception {
        int num = 45;
        sequentialThreshold = 5;
        try {
            if (args.length > 0)
                num = Integer.parseInt(args[0]);
            if (args.length > 1)
                sequentialThreshold = Integer.parseInt(args[1]);
        }
        catch (Exception e) {
            System.out.println("Usage: java CCFib <number> <threshold>]");
            return;
        }

        ForkJoinPool g = ForkJoinPool.commonPool();
        for (int reps = 0; reps < 2; ++reps) {
            lastStealCount = g.getStealCount();
            for (int i = 0; i < 20; ++i) {
                test(g, num);
            }
            System.out.println(g);
        }
    }

    /** for time conversion */
    static final long NPS = (1000L * 1000 * 1000);

    static void test(ForkJoinPool g, int num) throws Exception {
        int ps = g.getParallelism();
        long start = System.nanoTime();
        CCFib f = new LCCFib(null, num);
        f.invoke();
        long time = System.nanoTime() - start;
        double secs = ((double)time) / NPS;
        long number = f.number;
        System.out.print("CCFib " + num + " = " + number);
        System.out.printf("\tTime: %9.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();
    }

    // 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.2
Committed:	Thu Sep 18 06:00:27 2014 UTC (9 years, 8 months ago) by jsr166
Branch:	MAIN
CVS Tags:	HEAD
Changes since 1.1:	+5 -7 lines
Log Message:	whitespace
#	User	Rev	Content
1	dl	1.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			// A CountedCompleter version of Fibonacci
8
9			import java.util.concurrent.*;
10
11			public abstract class CCFib extends CountedCompleter {
12			static int sequentialThreshold;
13			int number;
14			int rnumber;
15
16			public CCFib(CountedCompleter parent, int n) {
17			super(parent, 1);
18			this.number = n;
19			}
20
21			public final void compute() {
22			CountedCompleter p;
23			CCFib f = this;
24			int n = number;
25			while (n > sequentialThreshold) {
26			new RCCFib(f, n - 2).fork();
27			f = new LCCFib(f, --n);
28			}
29	jsr166	1.2	f.number = (n <= 1) ? n : seqFib(n);
30	dl	1.1	f.onCompletion(f);
31			if ((p = f.getCompleter()) != null)
32			p.tryComplete();
33	jsr166	1.2	else
34			f.quietlyComplete();
35	dl	1.1	}
36
37			static final class LCCFib extends CCFib {
38			public LCCFib(CountedCompleter parent, int n) {
39			super(parent, n);
40			}
41			public final void onCompletion(CountedCompleter caller) {
42			CCFib p = (CCFib)getCompleter();
43			int n = number + rnumber;
44			if (p != null)
45			p.number = n;
46			else
47			number = n;
48			}
49			}
50	jsr166	1.2
51	dl	1.1	static final class RCCFib extends CCFib {
52			public RCCFib(CountedCompleter parent, int n) {
53			super(parent, n);
54			}
55			public final void onCompletion(CountedCompleter caller) {
56			CCFib p = (CCFib)getCompleter();
57			int n = number + rnumber;
58			if (p != null)
59			p.rnumber = n;
60			else
61			number = n;
62			}
63			}
64	jsr166	1.2
65	dl	1.1	static long lastStealCount;
66
67			public static void main(String[] args) throws Exception {
68			int num = 45;
69			sequentialThreshold = 5;
70			try {
71			if (args.length > 0)
72			num = Integer.parseInt(args[0]);
73			if (args.length > 1)
74			sequentialThreshold = Integer.parseInt(args[1]);
75			}
76			catch (Exception e) {
77			System.out.println("Usage: java CCFib <number> <threshold>]");
78			return;
79			}
80
81			ForkJoinPool g = ForkJoinPool.commonPool();
82			for (int reps = 0; reps < 2; ++reps) {
83			lastStealCount = g.getStealCount();
84			for (int i = 0; i < 20; ++i) {
85			test(g, num);
86			}
87			System.out.println(g);
88			}
89			}
90
91			/** for time conversion */
92			static final long NPS = (1000L * 1000 * 1000);
93
94			static void test(ForkJoinPool g, int num) throws Exception {
95			int ps = g.getParallelism();
96			long start = System.nanoTime();
97			CCFib f = new LCCFib(null, num);
98			f.invoke();
99			long time = System.nanoTime() - start;
100			double secs = ((double)time) / NPS;
101			long number = f.number;
102			System.out.print("CCFib " + num + " = " + number);
103			System.out.printf("\tTime: %9.3f", secs);
104			long sc = g.getStealCount();
105			long ns = sc - lastStealCount;
106			lastStealCount = sc;
107			System.out.printf(" Steals/t: %5d", ns/ps);
108			System.out.printf(" Workers: %8d", g.getPoolSize());
109			System.out.println();
110			}
111
112			// Sequential version for arguments less than threshold
113			static final int seqFib(int n) { // unroll left only
114			int r = 1;
115			do {
116			int m = n - 2;
117			r += m <= 1 ? m : seqFib(m);
118			} while (--n > 1);
119			return r;
120			}
121
122			}