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.9 by dl, Wed Jul 7 20:32:04 2010 UTC vs.
Revision 1.15 by jsr166, Wed Dec 31 17:00:58 2014 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
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 28 | Line 27 | public final class DynamicLeftSpineFib e
27
28
29		for (int reps = 0; reps < 2; ++reps) {
30	<	ForkJoinPool g = procs == 0? new ForkJoinPool() :
30	>	ForkJoinPool g = (procs == 0) ? new ForkJoinPool() :
31		new ForkJoinPool(procs);
32		lastStealCount = g.getStealCount();
33	<	for (int i = 0; i < 10; ++i) {
33	>	for (int i = 0; i < 20; ++i) {
34		test(g, num);
35		}
36		System.out.println(g);
37		g.shutdown();
38	+	if (!g.awaitTermination(10, TimeUnit.SECONDS))
39	+	throw new Error();
40	+	Thread.sleep(1000);
41		}
42		}
43
#	Line 69 | Line 71 | public final class DynamicLeftSpineFib e
71		int getAnswer() {
72		return number;
73		}
74	+	public void compute() {
75	+	number = fib(number);
76	+	}
77
78	<	public final void compute() {
79	<	int n = number;
80	<	if (n > 1) {
81	<	int r = 0;
82	<	DynamicLeftSpineFib rt = null;
83	<	while (getSurplusQueuedTaskCount() <= 3) {
84	<	int m = n - 2;
85	<	n -= 1;
86	<	if (m <= 1) {
87	<	r += m;
88	<	if (n > 1) {
89	<	r += n - 2;
90	<	n -= 1;
86	<	}
87	<	break;
78	>	static final int fib(int n) {
79	>	if (n <= 1)
80	>	return n;
81	>	int r = 0;
82	>	DynamicLeftSpineFib rt = null;
83	>	while (getSurplusQueuedTaskCount() <= 3) {
84	>	int m = n - 2;
85	>	n -= 1;
86	>	if (m <= 1) {
87	>	r += m;
88	>	if (n > 1) {
89	>	r += n - 2;
90	>	n -= 1;
91		}
92	<	(rt = new DynamicLeftSpineFib(m, rt)).fork();
92	>	break;
93		}
94	<	r += seqFib(n);
95	<	while (rt != null) {
96	<	if (rt.tryUnfork()) rt.compute(); else rt.join();
94	>	(rt = new DynamicLeftSpineFib(m, rt)).fork();
95	>	}
96	>	if (n <= 1)
97	>	r += n;
98	>	else
99	>	r += seqFib(n - 2) + fib(n - 1);
100	>	if (rt != null)
101	>	r += collectRights(rt);
102	>	return r;
103	>	}
104	>
105	>	static final int collectRights(DynamicLeftSpineFib rt) {
106	>	int r = 0;
107	>	while (rt != null) {
108	>	DynamicLeftSpineFib rn = rt.next;
109	>	rt.next = null;
110	>	if (rt.tryUnfork())
111	>	r += fib(rt.number);
112	>	else {
113	>	rt.join();
114		r += rt.number;
95	–	rt = rt.next;
115		}
116	<	number = r;
116	>	rt = rn;
117		}
118	+	return r;
119		}
120
121		// Sequential version for arguments less than threshold
122	<	static int seqFib(int n) {
123	<	if (n <= 1)
124	<	return n;
125	<	else
126	<	return seqFib(n-1) + seqFib(n-2);
122	>	static final int seqFib(int n) { // unroll left only
123	>	int r = 1;
124	>	do {
125	>	int m = n - 2;
126	>	r += m <= 1 ? m : seqFib(m);
127	>	} while (--n > 1);
128	>	return r;
129		}
130
131		}
110	–

Diff Legend

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