multi-threaded quicksort

[neuneudr]

Hi all,

On Oreilly's website there's a column about implementing
multi-threaded algoriths, with an example of quicksort in Java.

I'm scratching my head on someting...

May Column: Multi-threaded Algorithm Implementations

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

I read the column and thought "that ain't working", then downloaded
the code.

Here's the array to be sorted:

/** Elements to be sorted. */
@SuppressWarnings("unchecked")
final Comparable[] ar;

So it's a regular array.

I fail to see what guarantees are made in the sorting code
that swaps made by spawned threads are visible to someone
who would be observing the [].

Say we have 8,7,6,5,4,3,2,1 and the code makes the swaps
in the array and as now 4,3,2,1,8,7,6,5 and asks to two threads
to take care respectively of the 4,3,2,1 part and the 8,7,6,5 part.

I agree that the spawned threads are going to see correctly what
they should. But what guarantee are there that an observer will
indeed see the array sorted at the end?

To me to work the code needs to be changed, the following
doesn't seem correct:

final Comparable[] ar;

I'd replace it with:

final AtomicReferenceArray<Comparable> ar;

To me you can't simply spawn thread and pass them
a reference to an [] and indexes and tell it "go ahead,
swap and re-arrange the [] as you like" and hope that
changes are going to be visible. Java makes no such
guarantees right!?

While a AtomiceReferenceArray it's guaranteed to work,
but it incurs a performance hit compare to the [] version.

But then I guess I don't understand anything about the Java
memory model nor about the code posted (there a tiny code.zip
file, once you keep only the .java files related to quicksort
it's tiny).

Thoughts?

 

[neuneudr]

re all,

adding to my own question... At the end of each spawned thread,
we can see this:

new Thread () {
public void run () {
// invoke single-thread qsort
qsortN (left, pivotIndex - 1);
synchronized(helpRequestedMutex) {
helpersWorking--;
}
}
}.start();

Is the synchronization on the mutex at the end of each
sort enough to guarantee that changes made to the array
are indeed visible? (and hence guaranteed to work seen
that due to quicksort's nature we're sure each thread
is working on a different part of the array)?

 

[neuneudr]

Here's the code...

http://pastebin.com/m41b42a91

And even if synchronizing on 'helpRequestedMutex' would
be enough (would it be?) I fail to see how the caller
can synchronize on it too.

 

[markspace]

I'm scratching my head on someting...

May Column: Multi-threaded Algorithm Implementations

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

I'm scratching my head also. Did you download the source code? I don't
see at least one whole package of his. His package:

algs.model.array

just seems to be missing. It's not in the bin directory either. Broken
code, not tested. Hmm, maybe his book isn't great too.

 

[neuneudr]

The top-level waits on the volatile variable "helpersWorking", and since
that variable is volatile and is modified only after the worker threads
complete their effort and decrement the variable to 0. The use of
"volatile" preserves ordering of the operations, ensuring the main
thread does not return until all of the sorting has in fact been completed.

OK, I think I understand it better now...

Leaving the minor issue and the bigger performance issue aside,
then because the call to quicksort I'd make is blocking:

public void qsort (final int left, final int right) {
...
(wait on helpersWorking) [blocking here on volatile]
}

Then, because that call is blocking on that volatile, I'm
guaranteed to have the correct, sorted, array at the end
(because I'm calling it from a thread that is synchronizing
on the volatile).

Well, I may be wrong in my understanding, but that's how
I understand it now

Time to get out my copy of Java Concurrency In Practice,
read on CountdownLatch, and modify the example.

From the example code, apparently on thread is not just lost
monitoring the volatile variable: it's lost *busy looping* on
the variable:

while (helpersWorking > 0) { }

Sadly I only have a two-cores machine here so can't make
a lot of test but I'll still try to modify it.

Thanks a lot and don't hesitate to correct any further
misunderstanding I'm making here!

 

[neuneudr]

I'm scratching my head also. Did you download the source code? I don't
see at least one whole package of his. His package:

algs.model.array

just seems to be missing. It's not in the bin directory either. Broken
code, not tested. Hmm, maybe his book isn't great too.

There's a "code.zip" included in the article. Various classes from
the package are in there (including tests/benchmarks) but maybe not
the pivot selection method.

Anyway just for testing a pivot picking lo+hi/2 is probably
sufficient.

As Peter Duniho wrote, there's one thread 'lost' monitoring the
volatile and I think it's lost busy-looping doing that, which
seems bad but not hard to fix.

 

[markspace]

There's a "code.zip" included in the article. Various classes from
the package are in there (including tests/benchmarks) but maybe not
the pivot selection method.

Yes, code.zip is what I have. Unzipped it, popped it into NetBeans, got
all sorts of silly red underlining saying "package does not exist."

Oh well, I was trying to do it the easy way. I can roll my own if I
have to.

Note that there seems to be even more multi-threading stuff going into
Java 7, so you might want to hold off on that home brew all sining, all
dancing multi-threading code library:

<http://blogs.sun.com/mr/entry/closures>

 

[Mike Amling]

re all,

adding to my own question... At the end of each spawned thread,
we can see this:

new Thread () {
public void run () {
// invoke single-thread qsort
qsortN (left, pivotIndex - 1);
synchronized(helpRequestedMutex) {
helpersWorking--;
}
}
}.start();

Is the synchronization on the mutex at the end of each
sort enough to guarantee that changes made to the array
are indeed visible?

Yes. When the code leaves the synchronized(){}, all changes made by
the running Thread get flushed to RAM, where they will become visible to
other Threads no later than when those other Threads enter a
synchronized(){}.

--Mike Amling

 

[Roedy Green]

To me you can't simply spawn thread and pass them
a reference to an [] and indexes and tell it "go ahead,
swap and re-arrange the [] as you like" and hope that
changes are going to be visible. Java makes no such
guarantees right!?

I think the trick is the different threads, because of the way
Quicksort works, never touch the same parts of the array. Thus there
is no need for synchronisation.

 

[Roedy Green]

Is the synchronization on the mutex at the end of each
sort enough to guarantee that changes made to the array
are indeed visible? (and hence guaranteed to work seen
that due to quicksort's nature we're sure each thread
is working on a different part of the array)?

you could instrument the code in your Comparator too see if any other
threads would interfere.

 

[Kevin McMurtrie]

Hi all,

On Oreilly's website there's a column about implementing
multi-threaded algoriths, with an example of quicksort in Java.

I'm scratching my head on someting...

May Column: Multi-threaded Algorithm Implementations

http://broadcast.oreilly.com/2009/06/may-column-multithreaded-algor.html

I read the column and thought "that ain't working", then downloaded
the code.

Here's the array to be sorted:

/** Elements to be sorted. */
@SuppressWarnings("unchecked")
final Comparable[] ar;

So it's a regular array.

I fail to see what guarantees are made in the sorting code
that swaps made by spawned threads are visible to someone
who would be observing the [].

Say we have 8,7,6,5,4,3,2,1 and the code makes the swaps
in the array and as now 4,3,2,1,8,7,6,5 and asks to two threads
to take care respectively of the 4,3,2,1 part and the 8,7,6,5 part.

I agree that the spawned threads are going to see correctly what
they should. But what guarantee are there that an observer will
indeed see the array sorted at the end?

To me to work the code needs to be changed, the following
doesn't seem correct:

final Comparable[] ar;

I'd replace it with:

final AtomicReferenceArray<Comparable> ar;

To me you can't simply spawn thread and pass them
a reference to an [] and indexes and tell it "go ahead,
swap and re-arrange the [] as you like" and hope that
changes are going to be visible. Java makes no such
guarantees right!?

While a AtomiceReferenceArray it's guaranteed to work,
but it incurs a performance hit compare to the [] version.

But then I guess I don't understand anything about the Java
memory model nor about the code posted (there a tiny code.zip
file, once you keep only the .java files related to quicksort
it's tiny).

Thoughts?

The synchronized block syncs up everything - local caches in the
compiled code of the current thread and CPU caches. However, not having
a synchronized block doesn't mean that everything is running
independently at full speed. Some CPUs do automatic syncing of memory
blocks in their internal caches at great cost to performance. You don't
want multiple cores working on adjacent memory.


George T. Heineman's implementation in his blog is suspect. If he
really is using a spin lock on a long task he needs to be booted out of
the O'Reilly community. I don't have his full source code so I'll use
another example.

To modify this code:
http://www.cs.princeton.edu/introcs/42sort/QuickSort.java.html

First, delete the two static counter variables used for debugging. They
can not perform well with multiple threads.

Second, modify the nested quicksort to put the left sub-sort on a thread
if there are many values and not too much threaded recursion. The right
sub-sort will be calculated by the current thread. Make sure the left
thread finishes before leaving the method.

That's the basics of it. It doesn't run a whole lot faster in this
simple case because it's mostly memory-bound. Real-world cases with
complex comparison methods should perform much better.

public static void quicksort(double[] a)
{
shuffle(a); // to guard against worst-case
quicksort(a, 0, a.length - 1, 0);
}

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

if ((tdepth < 4) && ((i - left) > 1000))
{
final Thread t = new Thread()
{
public void run()
{
quicksort(a, left, i - 1, tdepth + 1);
}
};
t.start();
quicksort(a, i + 1, right, tdepth + 1);

try
{
t.join();
}
catch (InterruptedException e)
{
throw new RuntimeException("Cancelled", e);
}
} else
{
quicksort(a, left, i - 1, tdepth);
quicksort(a, i + 1, right, tdepth);
}
}

 

[markspace]

George T. Heineman's implementation in his blog is suspect.

To say the least.

If he
really is using a spin lock on a long task he needs to be booted out of
the O'Reilly community.

Well, it might be that he wants to add an extra thread, so he can
include some task switching with his testing. But I agree he really
ought to explain himself here, it looks hokey as all heck.

I don't have his full source code so I'll use
another example.

This is the other problem. I notice at least two errors in the code he
does provide.

1. He claims that his testing uses a maximum R (the ratio) of 51 yet his
code has MAX_R set to 21.

2. He uses Comparable as a raw type. It's just so 1.4.