Dr Heinz M. Kabutz <heinz <at> javaspecialists.eu>
2011-12-08 20:23:14 GMT
Thanks for the pointer, Mattias, I did not know about these demos and
was looking for something like this.
I've started translating them to Java 7, in order to figure out how
Fork/Join is supposed to work. Here is my first example, the Fibonacci
calculator, which is a silly example as it is O(2^n). But it's a good
one to get to know what you can do with Fork/Join. In the compute()
method, if n is above a threshold, we call invokeAll() on the two new
tasks Fib(n-1) and Fib(n-2) and then we join() both results together in
the end. Also in my version I decided to rather not have a volatile
shared field that we had in Doug's sample. We don't need it, since the
value is going to be returned from compute() anyway. The reason it had
to be volatile in Doug's sample is that it was set by the forking
thread and then updated by the forked thread. It was later read back
again by the forking thread. In my version it is a lot simpler.
Of course, we all know that fib can be implemented very easily in O(n)
using an iterative solution, but that's not the point of this exercise.
import java.util.concurrent.*;
/**
* Recursive task-based version of Fibonacci. Computes:
* <pre>
* Computes fibonacci(n) = fibonacci(n-1) + fibonacci(n-2); for n> 1
* fibonacci(0) = 0;
* fibonacci(1) = 1.
* </pre>
*
* Based on Fib.java found on
*
http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/taskDemo/demos.html
* <at> author Heinz Kabutz
*/
public class Fib extends RecursiveTask<Integer> {
// Performance-tuning constant:
private static int sequentialThreshold = 0;
private final int n;
public Fib(int n) {
this.n = n;
}
protected Integer compute() {
if (n <= 1) {
// fib(0) = 0; fib(1) = 1
return n;
} else if (n <= sequentialThreshold) {
return seqFib(n);
} else {
Fib f1 = new Fib(n - 1);
Fib f2 = new Fib(n - 2);
invokeAll(f1, f2);
return f1.join() + f2.join();
}
}
// 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);
}
public static void main(String[] args) throws InterruptedException {
int procs;
int num;
try {
procs = Integer.parseInt(args[0]);
num = Integer.parseInt(args[1]);
if (args.length > 2) sequentialThreshold =
Integer.parseInt(args[2]);
} catch (Exception e) {
System.out.println("Usage: java Fib <threads>
<number> [<sequentialThreshold>]");
return;
}
ForkJoinPool pool = new ForkJoinPool(procs);
Fib f = new Fib(num);
long time = System.currentTimeMillis();
int result = pool.invoke(f);
time = System.currentTimeMillis() - time;
System.out.println(pool);
System.out.println("Fib: Size: " + num + " Answer: " + result);
System.out.println("time = " + time);
}
}
The output on my 8 core machine, with increasing number of threads and
a sequentialThreshold of 20, gives me:
java.util.concurrent.ForkJoinPool <at> 4302a01f[Running, parallelism = 1,
size = 1, active = 0, running = 0, steals = 1, tasks = 0, submissions =
0]
Fib: Size: 45 Answer: 1134903170
time = 5920
java.util.concurrent.ForkJoinPool <at> 5999ae9c[Running, parallelism = 2,
size = 2, active = 0, running = 0, steals = 5, tasks = 0, submissions =
0]
Fib: Size: 45 Answer: 1134903170
time = 3391
java.util.concurrent.ForkJoinPool <at> 49cda7e7[Running, parallelism = 3,
size = 3, active = 0, running = 0, steals = 9, tasks = 0, submissions =
0]
Fib: Size: 45 Answer: 1134903170
time = 2255
java.util.concurrent.ForkJoinPool <at> 5cca548b[Running, parallelism = 4,
size = 4, active = 0, running = 0, steals = 9, tasks = 0, submissions =
0]
Fib: Size: 45 Answer: 1134903170
time = 1962
java.util.concurrent.ForkJoinPool <at> 6dc8f3cd[Running, parallelism = 5,
size = 5, active = 1, running = 1, steals = 25, tasks = 0, submissions
= 0]
Fib: Size: 45 Answer: 1134903170
time = 1618
java.util.concurrent.ForkJoinPool <at> d38d2fc[Running, parallelism = 6,
size = 6, active = 0, running = 0, steals = 34, tasks = 0, submissions
= 0]
Fib: Size: 45 Answer: 1134903170
time = 1855
java.util.concurrent.ForkJoinPool <at> da3a52c[Running, parallelism = 7,
size = 7, active = 0, running = 0, steals = 31, tasks = 0, submissions
= 0]
Fib: Size: 45 Answer: 1134903170
time = 1485
java.util.concurrent.ForkJoinPool <at> 3f0dbef1[Running, parallelism = 8,
size = 8, active = 0, running = 0, steals = 51, tasks = 0, submissions
= 0]
Fib: Size: 45 Answer: 1134903170
time = 1425
java.util.concurrent.ForkJoinPool <at> c390508[Running, parallelism = 16,
size = 16, active = 0, running = 0, steals = 184, tasks = 0,
submissions = 0]
Fib: Size: 45 Answer: 1134903170
time = 1444
java.util.concurrent.ForkJoinPool <at> fa5e4e4[Running, parallelism = 32,
size = 32, active = 0, running = 0, steals = 339, tasks = 0,
submissions = 0]
Fib: Size: 45 Answer: 1134903170
time = 1449
Regards
Heinz
--
Dr Heinz M. Kabutz (PhD CompSci)
Author of "The Java(tm) Specialists' Newsletter"
Sun Java Champion
IEEE Certified Software Development Professional
http://www.javaspecialists.eu
Tel: +30 69 72 850 460
Skype: kabutz
On 12/8/11 4:29 PM, Mattias De Wael wrote:
Dear
In the paper of Doug Lea "A Java Fork/Join Framework" a battery
of demo-apps is used to provide data about the performance of the
framework. These demo-applications can be found on Doug Lea's Homepage.
The demo code, however, is written for what seems to be a early
version of the framework (Version 1.3.4 with FJTasks instead of
ForkJoinTasks, FJRunnerGroups instead of ForkJoinPool, etc.)
Is anyone aware of an implementation of these demo-applications
for the framework in its current state (JDK7), and where I can find
them?
Thanks in advance,
Mattias
De Wael
Vrije Universiteit Brussel
Faculty of Sciences, DINF - SOFT
Room 10F736, Pleinlaan 2, B-1050 Brussels, Belgium
e-mail: madewael <at> vub.ac.be
_______________________________________________
Concurrency-interest mailing list
Concurrency-interest <at> cs.oswego.edu
http://cs.oswego.edu/mailman/listinfo/concurrency-interest
RSS Feed