Re: Parallel quicksort
In article <85ad3bFkk5U1@mid.individual.net>,
Mike Amling <mamling@rmcis.com> wrote:
Arne Vajh?j wrote:
On 15-05-2010 11:35, Jon Harrop wrote:
I cannot find an implementation of parallel quicksort in Java. Does
anyone have one or know where I can get one?
public static void tqsint_help(int n1, int n2, int[] ia, int depth,
int tdepth) {
...
>
if (depth >= tdepth) {
if (n1 < r)
tqsint_help(n1, r, ia, depth + 1, tdepth);
if (l < n2)
tqsint_help(l, n2, ia, depth + 1, tdepth);
} else {
ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1,
tdepth);
ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1,
tdepth);
...
Rather than make the caller guess a good value for tdepth, I think
you'd be better off with
if (r-n1>WORTH_THREADING) {
...new TheadSortHelp(...
} else if (n1<r) {
tqsint_help(...
}
and similar for l, n2.
The partition sizes can vary, and you could find in some partitions
that n1>=r before depth>=tdepth.
(Okay, oldish thread, but -- yeah well. I've been playing lately with
various parallel sorts, and am at a good break point to comment here,
maybe.)
A hearty "indeed" on Mike's closing remark. A somewhat related
point is that limiting the number of threads to the number of
available processors/cores, as is somewhat standard when adding
multithreading for performance, may lead to very poor load balance
(and hence poor performance), since there's no guarantee even
for random data that quicksort partitioning produces two pieces
of roughly equal size. This can lead to startling results,
such as situations in which going from one thread to two yields
no benefit, but going from two threads to four does.
It does help a bit to take Mike's advice about only creating
new threads if the amount of work is "enough". I've had more
success, though, with setting up a thread pool (using the classes
in java.util.concurrent) and creating new tasks to be assigned to
the thread pool rather than starting new threads -- and again,
only doing so if the amount of work is past some threshold.
I'm still tinkering a bit with how to specify the threshold, but
preliminary results are that with this approach you get somewhat
more predictable behavior, in that increasing the number of
threads improves better performance in a fairly consistent way.
Just sayin', maybe. (And I'd post my code, but it's part of a
larger experiment and hence maybe more complicated than it needs
to be, and I'm too lazy to extract a postable version.)
--
B. L. Massingill
ObDisclaimer: I don't speak for my employers; they return the favor.