Wait for all threads in an Executor to finish?

Question

I'm implementing a parellel quicksort as programming practice, and after I finished, I read the Java tutorial page on Executors, which sound like they could make my code even faster. Unfortunately, I was relying on join()'s to make sure that the program doesn't continue until everything is sorted. Right now I'm using:

public static void quicksort(double[] a, int left, int right) {
    if (right <= left) return;
    int i = partition(a, left, right);

    // threads is an AtomicInteger I'm using to make sure I don't
    // spawn a billion threads.
    if(threads.get() < 5){

        // ThreadSort's run method just calls quicksort()
        Future leftThread = e.submit(new ThreadSort(a, left, i-1));
        Future rightThread = e.submit(new ThreadSort(a, i+1, right));

        threads.getAndAdd(2);
        try {
            leftThread.get();
            rightThread.get();
        }
        catch (InterruptedException ex) {}
        catch (ExecutionException ex) {}
    }
    else{
        quicksort(a, left, i-1);
        quicksort(a, i+1, right);
    }
}

This seems to work ok, but if I run e.shutdown() right after I call my non-recursive quicksort() method, it has a bunch of RejectedExecutionExceptions, so I assume this isn't working as well as I had wanted.

So anyway, I'm basically trying to get the same functionality as leftThread.join() but with an Executor, and my questions is:

Is this the best way to wait until all of the threads are done?

EDIT: Ok, so I figured out why I got a bunch of errors after shutting down my Executor, it was because I was calling this function in a loop (to even out run times) and not creating a new Executor.

Answer 1

What type of executor are you using?

ThreadPoolExecutor.awaitTermination() will do what you are asking about (it's effectively a bulk join operation).

As a total aside, ThreadPoolExecutor will allow you to set limits on the # of threads, etc... (might be better than going recursive like what you are doing if the thread count goes high, not sure).

PS - I doubt that executors will make your code run any faster, but they may make your code easier to read and maintain. Using a Thread pool will make things faster for this sort of algorithm, and the Executor makes it easy to work with thread pools.

Answer 2

Take a look at Executors.newFixedThreadPool which lets you create a pool of at most n threads (gets rid of your "if") and the ExecutorService.shutdown method and the ExecutorsService.awaitTermination method.

Answer 3

You could use a CountDownLatch

Answer 4

PS - I doubt that executors will make your code run any faster, but they may make your code easier to read and maintain. Using a Thread pool will make things faster for this sort of algorithm, and the Executor makes it easy to work with thread pools.

This is not correct.

The executor can be 'backed' by any number of different execution systems including pooled threads.

You need to call the factory class correctly.

Furthermore you also need to decide on a policy for dealing with situations where jobs are submitted to the queue faster than they can be consumed, because you may not initially run out of memory due to limits on the thread execution, but if you queue millions of jobs, then they have to be stored some place whilst they wait for execution.