Re: multi-threaded quicksort
In article
<a27534d9-2925-4ee6-83f0-3bbde23e83ea@1g2000vbm.googlegroups.com>,
neuneudr@yahoo.fr wrote:
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);
}
}
--
I won't see Goolge Groups replies because I must filter them as spam