# Demonstrating the speed advantage of parallel computation

I am teaching a class on parallel computation and am looking for a simple example that illustrate the speed gains from using "CompletableFuture"s in Java. Currently my example problem is very simple: calculate the sum of an array. Each CompletableFuture calculates the sum of about 1/4 of the array, and when all of them finish, the main program calculates the total sum.

The line sum += Math.pow(Math.pow(Math.pow(array[i],0.3),0.4),0.5); was initially just sum += array[i]; I added all the "pow"s just to make the serial computation appear longer.

Currently, on my machine with 4 cores, when I put NUM_OF_THREADS = 1 the sum is calculated in 4 seconds, while with NUM_OF_THREADS = 4 the sum is calculated in 5.5 seconds, so this is not a good example - it does not show that parallel computation is more efficient.

what should I change in the example, to demonstrate the advantage of parallel computation?

public class ConcurrencyTest {

static final int SIZE = 10000000;
static final int NUM_OF_THREADS = 1;

@SuppressWarnings("unchecked")
public static void main(String[] args) throws InterruptedException, ExecutionException {
Arrays.fill(array, 1);

Instant startTime = Instant.now();

futures[iThread] = CompletableFuture.supplyAsync( () -> {
int sum=0;
for (int i=start; i<end; ++i) {
sum += Math.pow(Math.pow(Math.pow(array[i],0.3),0.4),0.5);
}
"   "+Duration.between(startTime, Instant.now()).toMillis()+" [ms]");
return sum;
}, executor);
}

CompletableFuture.allOf(futures).thenRun(
() -> {
try {
Arrays.stream(new int[] {1,2,3}).sum();
int totalSum = 0;
System.out.println("Total: "+totalSum+
"   "+Duration.between(startTime, Instant.now()).toMillis()+" [ms]");
} catch (InterruptedException | ExecutionException e) {
e.printStackTrace();
}
}
);

executor.shutdown();
}
}

• Parallel sleep() ;) Nov 28, 2017 at 7:47

Currently each future processes SIZE elements (increasing the NUM_OF_THREADS increases the total workload (NUM_OF_THREADS * SIZE)). Instead you want to divide the workload between each of the futures:

int start = SIZE / NUM_OF_THREADS * iThreadLocal;


Besides that iThread could (and should) be a local variable. The spacing between operators is inconsistent, you should add whitespace around the operators (except for unary operators) to improve readability.

• So, as I suspected, I had a bug! The other suggestions are also great. Thank you. Nov 29, 2017 at 8:19

I'd argue that this is a perfect example. Only like you say, it's an example of the downside of parallel computations. Namely that you get a lot of extra overhead in splitting it up and recombining afterwards.

Computing in parallel CAN be faster though. Try to simulate "doing a heavy computation by running sleep() instead.

Side note: Don't forget that your "main" thread also takes up the CPU, so it might be better to use 2 or 3 threads for the parallel computing.

• My students are very practical, an example with sleep will make them ask "why do we need this?!"... I am looking for an example where a CompletableFuture will actually be useful. Also, I am not sure if I am using CompletableFuture correctly. Is it possible that the results I get are a bug? Nov 28, 2017 at 10:25
• There are easy heavy computations: e.g. calculating N! for large N. The eight-fold speedup by using four cores of that example can also serve to illustrate other issues in optimisation... Nov 28, 2017 at 16:10

For the love of \$DEITY don't use yield. You're teaching the students bad habits!

If you want to show your students the awesome power of parallel computing, pick an inherently parallel problem. Like computing a Mandelbrot image, or compute pair wise edit distance of a large dataset of strings or compute character frequencies of a large codebase. Or brute force a password or something, there are endless embarrassingly parallel problems.

Pick a real workload, and show them a real use case instead of a contrived example.

## Edit: Why is use of Thread.yield() bad?

First of all we should carefully read the the documentation on Thread.yield() where it clearly says that:

It is rarely appropriate to use this method.

Which means, you probably shouldn't show if to your students on the first multi-threaded program they see, lest they get the idea that it is something they need to use.

Second we need to understand what yield() actually does. It only gives a hint (which the OS or JVM is completely free to ignore) that the OS might want to give the core to some other thread. It does not in-fact act as any sort of synchronisation or way to implement thread-to-thread communication. And frankly in your case I do not see why you would want to call yield() where you do.

In general the usage of yield() indicates a design problem with the program. Any place where you use yield() you should probably block your thread on a signal or mutex instead. These also let the OS schedule something else on the core, thus having the same effect as yield() but instead of being just a hint they actually stop execution of the thread.

Some examples:

• If you have a work queue, instead of your worker yielding when it has no work to do. It should block on a "new work available" signal.
• If you n+1 threads that need to stay roughly in sync in a pipeline you should use a monitor or other appropriate synchronisation primitive at interesting check points instead of yielding the fast thread();
• If you are writing a spinlock/mutex implementation. Don't! You'll probably get it wrong and the standard library already provides these.
For almost all places where you might consider yield() you can probably do something better by fixing your design or using the other functionality of Thread.
• @ErelSegal-Halevi What you're describing is a typical effect of the poor scheduling on Windows platforms (I've seen it countless times) and I'd recommend you use Linux for your server for this reason. Even so your problem should have been solvable by increasing the priority of the thread accepting requests and decreasing the priority of the computational threads via setPriority. Or even better use a work queue and reserve 1 core for serving requests and de-couple the computation from the serving. Yield was not guaranteed to work in your case and may fail on other systems as it is only a hint Dec 2, 2017 at 18:37