[concurrency-interest] question from new-user/instructor: "x.fork(); x.join()" vs. x.compute()

Dan Grossman djg at cs.washington.edu
Sun Mar 14 19:13:06 EDT 2010


 From a new user of JSR166 on Java 1.6...

Short version of question:

   Why am I seeing "x.fork(); x.join()" causing a trivial program to take about
   40x longer than the same program written using x.compute()?

Long version:

Context:

I wrote my first program using the JSR166 classes today because I am preparing 
to teach an _introductory_ data structures course.  This is a new course that 
will pair traditional material for such a course (asymptotic complexity, 
balanced trees, hashtables, etc.) with an _introduction_ to parallelism and 
concurrency.  I would like them to write some very simple fork-join 
computations (even if parallelism isn't useful for the problem size) as part 
of a project and to gain some understanding of reasoning about (nearly 
trivial) parallel algorithms.  JSR166 seem like the ideal framework; I don't 
plan on using anything fancy.

Who Should I Ask:

I apologize if my question is not appropriate for this list. If there is a 
better list for newcomers, a FAQ or other documentation, etc., just politely 
point me in the right direction.  I also apologize if my code has a stupid bug 
or I'm just a parallel-programming neophyte..  Web searches led me here.

Platform:

I am using http://gee.cs.oswego.edu/dl/jsr166/dist/jsr166.jar with Java 1.6, 
compiling with -cp jsr166.jar and running with -Xbootclasspath/p:jsr166.jar

I am getting roughly similar behavior with this JVM on Windows with
a 6-year-old uniprocessor:
  java version "1.6.0_12"
  Java(TM) SE Runtime Environment (build 1.6.0_12-b04)
  Java HotSpot(TM) Client VM (build 11.2-b01, mixed mode, sharing)
and this JVM on Linux with 4 processors (but I'm not the only compute job):
  java version "1.6.0_17"
  Java(TM) SE Runtime Environment (build 1.6.0_17-b04)
  Java HotSpot(TM) Server VM (build 14.3-b01, mixed mode)

I need to use Java 1.6 so that my students can stick with their standard Java 
installations in their lab, etc.

The program:

I have pasted the entire program below. All it does it initialize a large 
array and then add all the elements, making two fork-join passes over the 
array.

With FORK set to false, both passes use fork() to process the left half of the 
array and compute() to process the right half.  The performance is only 
1.5x-2x worse than the sequential algorithm (which takes about 50ms), which is 
impressive on a uniprocessor given all the extra bookkeeping the fork-join 
computation does.  Just what I wanted!

With FORK set to true, both passes use fork for both halves of the array.  The 
performance is about 80x slower than the sequential algorithm and I had to 
increase the Java max heap size.

The question:

Why is there such a difference in these two versions? Clearly "foo.fork(); 
foo.join()" is wasteful, but one could also argue it's more natural.  More 
importantly, I'd like to be able to explain to students _why_ they need to use 
foo.compute().

Thank you!

--Dan

====


import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;
import java.util.concurrent.RecursiveTask;

public class FirstFJProgram {
	static final boolean FORK = false;
	static final ForkJoinPool mainPool = new ForkJoinPool();
	static final int SEQUENTIAL_THRESHOLD = 1000;
	
	static final int ARRAY_SIZE = 5000000;
	
	static int[] array;

	static class InitializeArray extends RecursiveAction {
		int low;
		int high;
		InitializeArray(int lo, int hi) {
			low = lo;
			high = hi;
		}
		protected void compute() {
			if(high - low <= SEQUENTIAL_THRESHOLD) {
				for(int i=low; i < high; ++i)
					array[i] = i+1;
			} else {
				int mid = low + (high - low) / 2;
				InitializeArray left  = new InitializeArray(low, mid);
				InitializeArray right = new InitializeArray(mid, high);
				left.fork();
				if(FORK) {
					right.fork();
					right.join();
				} else {
					right.compute();
				}
				left.join();
			}
		}
	}
	
	static class SumArray extends RecursiveTask<Long> {
		int low;
		int high;
		SumArray(int lo, int hi) {
			low = lo;
			high = hi;
		}
		protected Long compute() {
			if(high - low <= SEQUENTIAL_THRESHOLD) {
				long sum = 0;
				for(int i=low; i < high; ++i)
					sum += array[i];
				return sum;
			} else {
				int mid = low + (high - low) / 2;
				SumArray left  = new SumArray(low, mid);
				SumArray right = new SumArray(mid, high);
				left.fork();
				if(FORK) {
					right.fork();
					return left.join() + right.join();
				} else {
					return right.compute() + left.join();
				}
			}
		}
	}
	
	static long sequential() {
		for(int i=0; i < array.length; ++i)
			array[i] = i+1;
		long sum = 0;
		for(int i=0; i < array.length; ++i)
			sum += array[i];
		return sum;
	}
	
	public static void main(String[] args) {
		array = new int[ARRAY_SIZE];
				
		System.gc();
		long sStart = System.currentTimeMillis();
		long sequential = sequential();
		long sEnd = System.currentTimeMillis();

		System.gc();
		long pStart = System.currentTimeMillis();
		mainPool.invoke(new InitializeArray(0,array.length));
		System.out.println();
		long answer = mainPool.invoke(new SumArray(0,array.length));
		long pEnd = System.currentTimeMillis();
				
		long check = ((long)ARRAY_SIZE * (ARRAY_SIZE+1)) / 2;
		
		System.out.println(answer + " " + sequential + " " + check);
		System.out.println("parallel: " + (pEnd - pStart) + " sequential: " + (sEnd 
- sStart));
	}
}


More information about the Concurrency-interest mailing list