Multi - threading

Question

I have tried to create a parallel quicksort in Java which I assume is a naive one (cause I haven't studied yet Interface Executor etc)

I needed a way to print the sorted array once all the threads are done..but I didn't know how many threads I am going to have in advance.. so I was doing it in a way that it will wait each time recursively with the join() method.. so the first join method that was invoked has to wait till all the other threads are done.. right ?

In that way when I execute my last two lines in main() ( of the printing array) I can be sure that all my threads are done...

so I have two questions ..

1. It is a multi-threading program that runs in parallel, right ? or am I making some mistakes that it actually runs in a linear way thread after thread ?

2. was I correct with my solution for displaying the sorted array in the main method?

Here is my code:

public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> array = new ArrayList();
        //please assume that I have invoked the input for the array from the user 
        QuickSortWithThreads obj = new QuickSortWithThreads(array,0 ,array.size()-1 );
        for(int i = 0; i < array.size(); i++)
            System.out.println(array.get(i));
    }
}

public class QuickSortWithThreads {
    public QuickSortWithThreads(ArrayList <Integer> arr, int left, int right){  
        quicksort(arr, left, right);
    }

    static void  quicksort(ArrayList <Integer> arr, int left, int right)  {
        int pivot;

        if(left<right){
            pivot = partition(arr, left, right);    
            QuickSortThread threadLeftSide = new QuickSortThread(arr, pivot + 1, right);
            threadLeftSide.start();  
            quicksort(arr, left, pivot - 1);
            try {
                threadLeftSide.join();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }           
        }
    }

    static  int partition(ArrayList<Integer> arr, int left, int right)  {
        int pivot = arr.get(right);
        int i = left -1;
        for( int j = left; j <= right - 1; j++) {
            if (arr.get(j) <= pivot){
                i = i + 1;
                exchange(arr, i, j);
            }
        }
        exchange(arr, i + 1, right);
        return i + 1;
    }
    static void exchange(ArrayList<Integer> arr, int i, int j) {
        int swap = arr.get(i);
        arr.set(i, arr.get(j)); 
        arr.set(j, swap);
    }

    private static class QuickSortThread extends Thread {
        int right;
        int left;
        ArrayList<Integer> refArray; 

        public QuickSortThread(ArrayList<Integer> array, int left, int right) {
            this.right = right;
            this.left = left;
            refArray = new ArrayList<Integer>();
            refArray = array;   
        }

        public void run() {
            quicksort(refArray, left, right);
        }
    }
}

Answer 1

If we knew the overall number of threads, we could use CountDownLatch initialized with the number of threads. But as we don't know the number of threads, we need an extended CountDownLatch which allows to increase the counter after its creation. Unfortunately we cannot just extend the class CountDownLatch as underlying counter is private. One way is to duplicate the original code of CountDownLatch to make access to the underlying counter. Less verbose way is to extend Semaphore to get access to the reducePermits method as it is done in Reduceable Semaphore. In principle, CountDownLatch and Semaphore are similar tools but differ in interpretation of the internal counter: the first counts vetoes and the latter counts permits.

The whole idea is to reduce the number of permits when a thread is created or started, and release permit when it is finished, at the end of the method run(). Initial number of permits is 1, so that if no threads started, the main procedure finishes freely. Note that reducing the number of permits at the beginning of the method run() is too late.

To get really good working code, you need also use a thread pool with fixed number of threads, and make sorting serially for small arrays.

Answer 2

General opinion

Yes, your code runs in parallel. And the result printing looks all right as well.

Limiting number of threads via depth

One problem is the fact that you create a huge number of threads: at the lowest level, you'll have approximately as many threads as there are list elements. And you don't catch exceptions resulting from this, so you'll not know (in your main thread) that this didn't work as intended.

You should probably limit the number of levels for which you spwan new threads. Once you have passes the for say 3 levels, you'll have about 2³=8 threads, which should be enough to keep all cores busy on most reasonable machines. You can then let the rest of the computation proceed wthout branching off further threads. You could do that by passing an additional parameter branching to your quicksort method. Set that to 3 in the invocation from the QuickSortWithThreads constructor, and decrement it on every call. Don't branch once the count reaches 0. This will give you the following calls:

quicksort(3, …)
  quicksort(2, …)
    quicksort(1, …)
      quicksort(0, …)
      quicksort(0, …)
    quicksort(1, …)
      quicksort(0, …)
      quicksort(0, …)
  quicksort(2, …)
    quicksort(1, …)
      quicksort(0, …)
      quicksort(0, …)
    quicksort(1, …)
      quicksort(0, …)
      quicksort(0, …)

Since each non-leaf call shares a thread with one of its children, you can deduct the maximum of 8 threads from the number of leafs above.

Limiting number of threads via Executors

As an alternative to this home-made way of restricting the number of threads, you might of course do this using the Executor interface you mentioned. You could create a ThreadPoolExecutor to manage your threads, and pass each recursive invocation as an instance of Runnable (which might look similar to your QuickSortThread). One major problem with this approach is detecting termination. Particularly if you want to avoid deadlock in case of an error. So it might be better to use a ForkJoinTask instead, since in that case you can have each task wait on the conclusion of its other child, very similar to what you wrote, and you can still limit the number of actual threads in the associated ForkJoinPool. Your actual implementation would best use RecursiveAction, a specialization of ForkJoinTask if you have no return value, for which the documentation contains an example very similar to your scenario.