Channels ▼

Clay Breshears

Dr. Dobb's Bloggers

Beneath the Planet of the Iterative Quicksort

October 18, 2011

The secret ingredient for parallel iterative sorting is okra!

No, that doesn't sound right. That's the secret ingredient on next week's Iron Chef episode. (Shhh, don't spoil it for anyone. Try to act surprised when they announce it.)

For parallel iterative Quicksort, the missing piece from my last blog is how to terminate the sorting threads. To review, we need to use a thread-safe structure that can hold the index pairs of sub-arrays to be partitioned and then sorted. We don't want to drop an index pair or sort the same sub-array more than once. A quick and dirty implementation of a thread-safe queue using Windows threads includes a CriticalSection object as part of the queue structure to protect access to the queue. Most of the code for both enqueue() and dequeue() operations will be protected by the lock, which will serialize access to the queue. That's the quick part.

The dirty part would be not having a separate test for the queue being empty, but returning an error code when a thread tries to dequeue() from an empty queue. To use this modification in serial, the body of the iterative Quicksort function is enclosed in an infinite while-loop. When the function finds an empty queue (only after the sort is complete since the initial pair of index values for the whole array to be sorted was pushed onto the queue before the Quicksort function was first called), it returns the error code and then breaks out of the infinite loop.

Why go to such lengths? Why not just have a separate test for the queue being empty? Two reasons:

  • First, when threaded, the nondeterministic execution can allow one thread to find a non-empty queue and, before it can pull out the single index pair on the queue, another thread also finds the queue holds something. Both threads expect to find an index pair, but only one will get it and the other will get garbage.
  • Second, the empty queue can no longer be used to determine sort completion when more than one thread is involved in the sort. Once the initial index pair is taken out of the queue by one thread, any other threads involved with the sort will find the queue empty. If those threads terminate their execution, the first thread will be left alone to sort the whole array.

So, getting back to terminating threads, you first need to know when it is okay for threads to terminate. If the empty queue cannot be used to signal when the sorting is done, what other condition could be used to know when all items have been placed in their final position? Fortunately, the Quicksort algorithm has a special property that we can exploit: every time we call the Partition() function at least one item — the pivot element — is known to be in its sorted position. That means we can simply increment a shared counter after Partition() is executed and, when the counter equals the total number of items that were to be sorted, every item is in its final position.

Obviously the increment operation on the shared counter needs to be done in a protected way. If we use Windows threads for our parallelism, the InterlockedIncrement() function to perform an atomic increment after returning from calls to Partition(). Also, we can test for the special case where the sub-array to be sorted has a single element in it. Because this item must also be in its final position, there will be no need to call QuickSort() on that one thing, but simply increment the counter.

Before we go all the way with a parallel solution, let's take a look at how all the ideas discussed above can be implemented into the serial iterative QuickSort() function.

long tCount = 0;
BOOL Done = FALSE;

void QuickSort(void *pArg)
{
  int p, r, q;
  qSortIndex *d, *d1, *d2;

  while (1) {
    if (Done) break; // signal to terminate 
    Q.dequeue(&d);
    p = d.lo; r = d.hi;
    if (p < r) { // more than one thing to sort
      q = Partition(p, r);
      InterlockedIncrement(&tCount);
      d1.lo = p; d1.hi = q-1;
      Q.enqueue(d1);
      d2.lo = q+1; d2.hi = r;
      Q.enqueue(d2);
    }
    else if (p == r) {  // exactly one thing to be sorted
      InterlockedIncrement(&tCount);
      if (tCount == N) Done = TRUE;   // Signal that sorting is done
    }
  }
}

The (shared) variables tCount and Done are defined and initialized external to the QuickSort() function. The sort is completed when tCount reaches the number of items (N) in the original array to be sorted. This sets Done to TRUE and the next iteration of the while-loop will break out rather than attempt to remove something from the (now empty) queue, Q. Notice that even though I talked about the modification of an error code being returned from the dequeue() method, we don't use it here in the serial version.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video