Java merge sort algorithm with wait()/notify() synchronization

Question

I'm trying to implement the merge sorting using only the wait/notify synchronization. I'm aware of more high-level constructions like Fork/Join, Executors. etc. But I need to use work/notify here. Based on this https://courses.cs.washington.edu/courses/cse373/13wi/lectures/03-13/ I refactored the method parallelMergeSort() with synchronized blocks:

public void parallelMergeSort() {
  synchronized (values) {
     if (threadCount <= 1) {
        mergeSort(values);
        values.notify();
     } else if (values.length >= 2) {
        // split array in half
       int[] left = Arrays.copyOfRange(values, 0, values.length / 2);
       int[] right = Arrays.copyOfRange(values, values.length / 2, values.length);
       synchronized(left) {
         synchronized (right) {
            // sort the halves
            // mergeSort(left);
            // mergeSort(right);
           Thread lThread = new Thread(new ParallelMergeSort(left, threadCount / 2));
           Thread rThread = new Thread(new ParallelMergeSort(right, threadCount / 2));
           lThread.start();
           rThread.start();
           /*try {
             lThread.join();
             rThread.join();
           } catch (InterruptedException ie) {}*/
           try {
             left.wait();
             right.wait();
           } catch (InterruptedException e) {
             e.printStackTrace();
           }
           // merge them back together
           merge(left, right, values);
        }
      }
      values.notify();
    }
  }
}

values is an input array here.

As a result I see the performance of sorting is down and it's slower even than a single-thread sorting. I guess that a bottleneck is within two synchronization blocks of left and right parts of an array. Does someone know how to refactor it in order to make it faster than the single-thread sorting?

Answer 1

The problem lies in your nested synchronized blocks:

synchronized(left) {
   synchronized (right) {
       Thread lThread = new Thread(…);
       Thread rThread = new Thread(…);
       lThread.start();
       rThread.start();
       try {
         left.wait();
         right.wait();
       }
       …

You are holding both locks when you start the new threads which in turn try to acquire these locks. Therefore your new threads are blocked until the initiating thread releases these locks. This happens implicitly when the thread calls wait() but … you can only wait for one condition at a time!

So when the initiating thread calls left.wait(), it releases the lock of the left instance and the sub-thread spawned for processing the left part can proceed but the initiating thread still holds the right lock while waiting on left. Once the sub-thread has finished processing left it will call notify, followed by releasing the lock of left which allows wait() to re-acquire it and return.

Then the initiating thread can call right.wait() which will release the right lock and allows the other sub-thread to start its work, hence the equal to sequential performance. For each spawning of sub-threads the sub-threads are enforced to run one after another due to the locks held by the initiating thread.

One way to fix this would be launching the threads first and acquiring the locks afterwards and only the one lock you are about to wait rather then nesting the synchronized blocks. This is still subject to the unspecified timing (now, a sub-thread may have finished its work and called notify even before you enter the synchronized(x) { x.wait(); } block) and the so-called spurious wakeups. Simply said, you need a verifiable condition which is checked before and after calling wait() as explained in the documentation of wait():

As in the one argument version, interrupts and spurious wakeups are possible, and this method should always be used in a loop:

synchronized (obj) {
    while (<condition does not hold>)
        obj.wait();
    ... // Perform action appropriate to condition
}

The condition might be a boolean flag set to true by the sub-thread right before calling notify() to signal that the work is done.

Note that this all is what you get for free when using Thread.join(). The synchronization happens within the join() method and these two invocations cannot overlap. Further, the implementation uses a verifiable condition (the alive state of the thread) to ensure to call wait() only when necessary and to protect itself against “spurious wakeups”.

Answer 2

You will need to sort millions of values to see the effect of the parallelism, if you ever do, because you are copying arrays all over the place and that puts most of the strain on the system on memory access and garbage collection, not on the sorting.

To properly parallelise sorting you would need to do it in-place - which makes a merge sort very unlikely to be a good candidate because it must create a new array for the target.

If all you are doing is experimenting then use a compare/compute intensive algorithm like bubble-sort.

Note that if this has been set as an assignment then your lecturer is probably expecting you to respond with you can't because merge-sort is a bad candidate for parallelism.