ViewVC Help

View File | Revision Log | Show Annotations | Download File | Root Listing

root/jsr166/jsr166/src/test/loops/DynamicLeftSpineFib.java

Comparing jsr166/src/test/loops/DynamicLeftSpineFib.java (file contents):
Revision 1.7 by dl, Sat Nov 14 20:58:11 2009 UTC vs.
Revision 1.17 by dl, Sat Sep 12 18:26:21 2015 UTC

#	Line 1 | Line 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/licenses/publicdomain
4	>	* http://creativecommons.org/publicdomain/zero/1.0/
5		*/
6
7		import java.util.*;
#	Line 9 | Line 9 | import java.util.concurrent.*;
9
10		public final class DynamicLeftSpineFib extends RecursiveAction {
11
12	–	// Performance-tuning constant:
12		static long lastStealCount;
13	<
13	>
14		public static void main(String[] args) throws Exception {
15		int procs = 0;
16	<	int num = 43;
16	>	int num = 45;
17		try {
18		if (args.length > 0)
19		procs = Integer.parseInt(args[0]);
#	Line 26 | Line 25 | public final class DynamicLeftSpineFib e
25		return;
26		}
27
29	–
28		for (int reps = 0; reps < 2; ++reps) {
29	<	ForkJoinPool g = procs == 0? new ForkJoinPool() :
29	>	ForkJoinPool g = (procs == 0) ? ForkJoinPool.commonPool() :
30		new ForkJoinPool(procs);
31		lastStealCount = g.getStealCount();
32	<	for (int i = 0; i < 10; ++i) {
32	>	for (int i = 0; i < 20; ++i) {
33		test(g, num);
34		}
35		System.out.println(g);
36	<	g.shutdown();
36	>	if (g != ForkJoinPool.commonPool()) {
37	>	g.shutdown();
38	>	if (!g.awaitTermination(10, TimeUnit.SECONDS))
39	>	throw new Error();
40	>	}
41	>	Thread.sleep(1000);
42		}
43		}
44
#	Line 57 | Line 60 | public final class DynamicLeftSpineFib e
60		System.out.println();
61		}
62
60	–
63		// Initialized with argument; replaced with result
64		int number;
65		DynamicLeftSpineFib next;
66
67	<	DynamicLeftSpineFib(int n, DynamicLeftSpineFib nxt) {
68	<	number = n; next = nxt;
67	>	DynamicLeftSpineFib(int n, DynamicLeftSpineFib nxt) {
68	>	number = n; next = nxt;
69		}
70
71		int getAnswer() {
72		return number;
73		}
74
75	<	public final void compute() {
76	<	int n = number;
77	<	if (n > 1) {
78	<	int r = 0;
79	<	DynamicLeftSpineFib rt = null;
80	<	while (getSurplusQueuedTaskCount() <= 3) {
81	<	int m = n - 2;
82	<	n -= 1;
83	<	if (m <= 1) {
84	<	r += m;
85	<	if (n > 1) {
86	<	r += n - 2;
87	<	n -= 1;
88	<	}
87	<	break;
88	<	}
75	>	public void compute() {
76	>	number = fib(number);
77	>	}
78	>
79	>	static final int fib(int n) {
80	>	if (n <= 1)
81	>	return n;
82	>	int r = 0;
83	>	DynamicLeftSpineFib rt = null;
84	>	while (getSurplusQueuedTaskCount() <= 3) {
85	>	int m = n - 2;
86	>	if (m <= 1)
87	>	r += m;
88	>	else
89		(rt = new DynamicLeftSpineFib(m, rt)).fork();
90	<	}
91	<	r += seqFib(n);
92	<	while (rt != null) {
93	<	if (rt.tryUnfork()) rt.compute(); else rt.helpJoin();
90	>	if (--n <= 1)
91	>	break;
92	>	}
93	>	r += n <= 1 ? n : seqFib(n);
94	>	if (rt != null)
95	>	r += collectRights(rt);
96	>	return r;
97	>	}
98	>
99	>
100	>	static final int collectRights(DynamicLeftSpineFib rt) {
101	>	int r = 0;
102	>	while (rt != null) {
103	>	DynamicLeftSpineFib rn = rt.next;
104	>	rt.next = null;
105	>	if (rt.tryUnfork())
106	>	r += fib(rt.number);
107	>	else {
108	>	rt.join();
109		r += rt.number;
95	–	rt = rt.next;
110		}
111	<	number = r;
111	>	rt = rn;
112		}
113	+	return r;
114		}
115
116		// Sequential version for arguments less than threshold
117	<	static int seqFib(int n) {
118	<	if (n <= 1)
119	<	return n;
120	<	else
121	<	return seqFib(n-1) + seqFib(n-2);
117	>	static final int seqFib(int n) { // unroll left only
118	>	int r = 1;
119	>	do {
120	>	int m = n - 2;
121	>	r += m <= 1 ? m : seqFib(m);
122	>	} while (--n > 1);
123	>	return r;
124		}
108	–
109	–	}
125
126	+	}

Diff Legend

–	Removed lines
+	Added lines
<	Changed lines
>	Changed lines