1
\$\begingroup\$

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;

    static int iThread;
    @SuppressWarnings("unchecked")
    public static void main(String[] args) throws InterruptedException, ExecutionException {
        int[] array = new int[NUM_OF_THREADS*SIZE];
        Arrays.fill(array, 1);

        ExecutorService executor = Executors.newCachedThreadPool();
        Instant startTime = Instant.now();

        CompletableFuture<Integer>[] futures = new CompletableFuture[NUM_OF_THREADS];
        for (iThread=0; iThread<NUM_OF_THREADS; ++iThread) {
            final int iThreadLocal = iThread;
            futures[iThread] = CompletableFuture.supplyAsync( () -> {
                int sum=0;
                int start = iThreadLocal*SIZE;
                int end = (iThreadLocal+1)*SIZE;
                for (int i=start; i<end; ++i) {
                    Thread.yield();
                    sum += Math.pow(Math.pow(Math.pow(array[i],0.3),0.4),0.5);
                }
                System.out.println(iThreadLocal+": "+sum + 
                        "   "+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;
                        for (iThread=0; iThread<NUM_OF_THREADS; ++iThread)
                            totalSum += futures[iThread].get();
                        System.out.println("Total: "+totalSum+ 
                                "   "+Duration.between(startTime, Instant.now()).toMillis()+" [ms]");
                    } catch (InterruptedException | ExecutionException e) {
                        e.printStackTrace();
                    }
                }
        );

        executor.shutdown();
    }
}
\$\endgroup\$
1
  • \$\begingroup\$ Parallel sleep() ;) \$\endgroup\$ Nov 28, 2017 at 7:47

3 Answers 3

7
\$\begingroup\$

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;
int end = SIZE / NUM_OF_THREADS * (iThreadLocal + 1);

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.

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

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.

\$\endgroup\$
2
  • \$\begingroup\$ 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? \$\endgroup\$ Nov 28, 2017 at 10:25
  • \$\begingroup\$ 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... \$\endgroup\$ Nov 28, 2017 at 16:10
2
\$\begingroup\$

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.
  • If you have one thread that is low priority and should let other threads run first? Use Thread.setPriority(int) instead.

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.

\$\endgroup\$
4
  • \$\begingroup\$ Can you please explain why using yield() is bad? \$\endgroup\$ Nov 29, 2017 at 8:37
  • \$\begingroup\$ @ErelSegal-Halevi Added an edit to explain. Please do consider making a example which uses an embarrassingly parallel problem to show your students the awesomeness of multi-threading. They will appreciate that more. Especially if it is visual, like a Mandelbrot image. \$\endgroup\$
    – Emily L.
    Dec 2, 2017 at 1:39
  • \$\begingroup\$ Thanks for the explanation. Indeed in this case yield is not needed. However, I needed it in another case: I built a web-server that accepts requests for calculating a computationally-hard problem. I wanted to make sure that the server remains responsive and responds to new clients even while it is busy calculating responses for previous clients. I had to insert yield() in the calculation loop since it did not work without it. \$\endgroup\$ Dec 2, 2017 at 16:07
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – Emily L.
    Dec 2, 2017 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.