Re: Parallel quicksort

Discussion in 'Java' started by Arne Vajhøj, May 16, 2010.

  1. Arne Vajhøj

    Arne Vajhøj Guest

    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(int[] ia, int tdepth) {
    tqsint_help(0, ia.length - 1, ia, 0, tdepth);
    return;
    }
    public static void tqsint_help(int n1, int n2, int[] ia, int depth,
    int tdepth) {
    int tmp;
    int l = n1;
    int r = n2;
    int pivot = ia[(n1 + n2) / 2];
    do {
    while (ia[l] < pivot)
    l++;
    while (ia[r] > pivot)
    r--;
    if (l <= r) {
    tmp = ia[l];
    ia[l] = ia[r];
    ia[r] = tmp;
    l++;
    r--;
    }
    } while (l <= r);
    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);
    h1.start();
    h2.start();
    try {
    h1.join();
    h2.join();
    } catch (InterruptedException e) {
    e.printStackTrace();
    }
    }
    return;
    }

    ....

    class ThreadSortHelp extends Thread {
    private int n1;
    private int n2;
    private int[] ia;
    private int depth;
    private int tdepth;
    public ThreadSortHelp(int n1, int n2, int[] ia, int depth, int tdepth) {
    super();
    this.n1 = n1;
    this.n2 = n2;
    this.ia = ia;
    this.depth = depth;
    this.tdepth = tdepth;
    }
    public void run() {
    ThreadSort.tqsint_help(n1, n2, ia, depth, tdepth);
    }
    }

    Arne
     
    Arne Vajhøj, May 16, 2010
    #1
    1. Advertising

  2. Arne Vajhøj

    markspace Guest

    Arne Vajhøj wrote:
    > } else {
    > ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1,
    > tdepth);
    > ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1,
    > tdepth);



    Just a thought: Why spawn two threads here? You already have one
    thread running (the current one). Spawn one thread (proabaly on the
    larger span between pivot and start/end) and sort the other bit
    recursively in the current thread. Then just wait on the other thread
    after you're done with the recursive sort.


    However, I played around with this myself a while ago, and I'm not sure
    the whole idea is a great one. Quicksorts are god-awful at sorting many
    real world types of data. If a list is already sorted, then quicksort
    degenerates into a bubble sort. That's N^2 performance. And pre-sorted
    data is pretty common so you're likely to hit this issue often.

    I think it would be better to change the problem to some kind of
    multi-threaded mergesort . Merge sort always takes n log n, it's got no
    weird corners like quicksort. You could probably speed up the
    multi-threaded version by having higher level "merges" merge data as it
    becomes available, rather than waiting for an entire lower level pass to
    complete.
     
    markspace, May 16, 2010
    #2
    1. Advertising

  3. Arne Vajhøj

    Arne Vajhøj Guest

    On 15-05-2010 19:47, markspace wrote:
    > Arne Vajhøj wrote:
    >> } else {
    >> ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1, tdepth);
    >> ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1, tdepth);

    >
    > Just a thought: Why spawn two threads here? You already have one thread
    > running (the current one). Spawn one thread (proabaly on the larger span
    > between pivot and start/end) and sort the other bit recursively in the
    > current thread. Then just wait on the other thread after you're done
    > with the recursive sort.


    It may be more efficient. But I like the symmetric approach of
    this code.

    > However, I played around with this myself a while ago, and I'm not sure
    > the whole idea is a great one. Quicksorts are god-awful at sorting many
    > real world types of data. If a list is already sorted, then quicksort
    > degenerates into a bubble sort. That's N^2 performance. And pre-sorted
    > data is pretty common so you're likely to hit this issue often.


    Not quite correct.

    Quicksort degenerate into O(n^2) for sorted data *if* the first
    or last element is used as pivot.

    My code used the middle element.

    For the very same reason.

    That works super for sorted data.

    Ofcourse there still exists some orders that degenerate
    into O(n^2), but they are not very likely (unlike the already
    sorted order).

    Arne
     
    Arne Vajhøj, May 16, 2010
    #3
  4. Arne Vajhøj

    Tom Anderson Guest

    On Sat, 15 May 2010, Arne Vajh?j wrote:

    > On 15-05-2010 19:47, markspace wrote:
    >> Arne Vajh?j wrote:
    >>> } else {
    >>> ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1, tdepth);
    >>> ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1, tdepth);

    >>
    >> Just a thought: Why spawn two threads here? You already have one thread
    >> running (the current one). Spawn one thread (proabaly on the larger span
    >> between pivot and start/end) and sort the other bit recursively in the
    >> current thread. Then just wait on the other thread after you're done
    >> with the recursive sort.

    >
    > It may be more efficient. But I like the symmetric approach of
    > this code.


    This would be an ideal use for the JSR-166y fork-join framework, which
    lets you express the two branches symmetrically, but have the executed
    without unnecessary thread creations. If you can't wait for java 7, get it
    from Doug Lea:

    http://gee.cs.oswego.edu/dl/concurrency-interest/index.html

    >> However, I played around with this myself a while ago, and I'm not sure
    >> the whole idea is a great one. Quicksorts are god-awful at sorting many
    >> real world types of data. If a list is already sorted, then quicksort
    >> degenerates into a bubble sort. That's N^2 performance. And pre-sorted
    >> data is pretty common so you're likely to hit this issue often.

    >
    > Not quite correct.
    >
    > Quicksort degenerate into O(n^2) for sorted data *if* the first
    > or last element is used as pivot.
    >
    > My code used the middle element.
    >
    > For the very same reason.
    >
    > That works super for sorted data.
    >
    > Ofcourse there still exists some orders that degenerate
    > into O(n^2), but they are not very likely (unlike the already
    > sorted order).


    All correct. But for real-world data, even tweakedd quicksorts are
    routinely beaten by adaptive sorts like Timsort. Of course, what's
    relevant right here is that quicksort can be parallelised - i'm not aware
    that Timsort can be, and i have no idea about any other adaptive sorts.

    tom

    --
    eviscerated by obfuscation
     
    Tom Anderson, May 16, 2010
    #4
  5. Arne Vajhøj

    Mike Amling Guest

    markspace wrote:
    > Arne Vajhøj wrote:
    >> } else {
    >> ThreadSortHelp h1 = new ThreadSortHelp(n1, r, ia, depth + 1,
    >> tdepth);
    >> ThreadSortHelp h2 = new ThreadSortHelp(l, n2, ia, depth + 1,
    >> tdepth);

    >
    >
    > Just a thought: Why spawn two threads here? You already have one
    > thread running (the current one). Spawn one thread (proabaly on the
    > larger span between pivot and start/end) and sort the other bit
    > recursively in the current thread. Then just wait on the other thread
    > after you're done with the recursive sort.
    >
    >
    > However, I played around with this myself a while ago, and I'm not sure
    > the whole idea is a great one. Quicksorts are god-awful at sorting many
    > real world types of data. If a list is already sorted, then quicksort
    > degenerates into a bubble sort. That's N^2 performance. And pre-sorted
    > data is pretty common so you're likely to hit this issue often.


    While the original QuickSort used the first element as the pivot, an
    improved variant swaps the first, last and middle elements until they're
    in order, then uses the resulting middle element as the pivot. Those
    swaps are over long distances, and hence are consistent with the spirit
    of QuickSort. This improvement was published shortly after the original
    QuickSort, back in the '60s. The improved algorithm is robust over lots
    of original orders of the data, probably over all data that hasn't been
    deliberately arranged to foil QS.

    --Mike Amling
     
    Mike Amling, May 16, 2010
    #5
  6. Arne Vajhøj

    Mike Amling Guest

    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.

    --Mike Amling
     
    Mike Amling, May 16, 2010
    #6
  7. Arne Vajhøj

    Eric Sosman Guest

    On 5/16/2010 10:01 AM, Mike Amling wrote:
    >
    > While the original QuickSort used the first element as the pivot, an
    > improved variant swaps the first, last and middle elements until they're
    > in order, then uses the resulting middle element as the pivot. Those
    > swaps are over long distances, and hence are consistent with the spirit
    > of QuickSort. This improvement was published shortly after the original
    > QuickSort, back in the '60s. The improved algorithm is robust over lots
    > of original orders of the data, probably over all data that hasn't been
    > deliberately arranged to foil QS.


    Look up "Engineering a Sort Function" by Bentley and McIlroy
    for a real-world data set that drove a widely-used real-world
    qsort() implementation completely over the edge. While studying
    the issue, Bentley and McIlroy learned

    "In fact, among a dozen different Unix libraries we found
    no qsort that could not easily be driven to quadratic
    behavior [...]"

    After a good deal of work, Bentley and McIlroy settled on a
    threefold scheme, with the breakpoints determined emprically:

    - For "small" arrays or sub-arrays, use the middle element

    - For "medium" arrays, use the median of the first, middle,
    and last elements

    - For "large" arrays, choose nine evenly-spread elements,
    take them in groups of three and find the three medians,
    and use the median of those medians

    They also lay a good deal of stress on the practical importance
    of using the "Dutch National Flag" partitioning scheme. Equal keys,
    they found, turn out to be quite common in real-world data sets.

    --
    Eric Sosman
    lid
     
    Eric Sosman, May 16, 2010
    #7
  8. Arne Vajhøj

    Guest

    In article <>,
    Mike Amling <> 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.
     
    , May 29, 2010
    #8
  9. Arne Vajhøj

    markspace Guest

    wrote:
    >
    > somewhat related
    > point is that limiting the number of threads to the number of
    > available processors/cores,



    This doesn't work, at least given the algorithms above.

    I tried this, long ago, when Java first started tinkering around with
    replacing the current merge-sort with a Tim-sort. A multi-threaded
    merge- or quicksort seemed like just the thing to beat any single
    threaded solution. Alas, it was not to be.

    The up shot is that these algorithms here wait() on a child thread. And
    if you limit your total threads... then you spawn two sub-threads, they
    spawn four sub-tasks... which need threads... which they can't get
    because the the two threads are still consumed by waiting.

    Trust me, limited thread pools locks up hard.

    Having CPU time and having a Thread are two different things. You could
    program around this by having the threads NOT wait... they'd need some
    sort of completion task... but now you are getting a lot of tasks
    running in lots of threads. The overhead is high, and I couldn't get
    the overhead down low enough to beat the supplied single-threaded merge
    sort.

    At some point you to admit that really robust, fast sorting is a hard
    enough problem that you don't want to re-invent it, and leave it to the
    Java folks to implement. If Jon (the OP) can beat his head against it
    and devise a solution, then great. I don't have the time to actually
    track down every possible solution and test them all out sufficiently.
     
    markspace, May 29, 2010
    #9
  10. Arne Vajhøj

    kebodi

    Joined:
    Nov 6, 2010
    Messages:
    1
    Who can show me how to implement parallel quicksort between two computers?
     
    kebodi, Nov 6, 2010
    #10
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. simo

    Parallel quicksort (MPI)

    simo, Mar 7, 2007, in forum: C Programming
    Replies:
    2
    Views:
    2,135
    user923005
    Mar 7, 2007
  2. Soren
    Replies:
    4
    Views:
    1,269
    c d saunter
    Feb 14, 2008
  3. Kevin McMurtrie

    Re: Parallel quicksort

    Kevin McMurtrie, May 16, 2010, in forum: Java
    Replies:
    0
    Views:
    697
    Kevin McMurtrie
    May 16, 2010
  4. aminer
    Replies:
    1
    Views:
    536
    aminer
    Aug 18, 2012
  5. aminer
    Replies:
    0
    Views:
    368
    aminer
    Aug 18, 2012
Loading...

Share This Page