Intel Threading Building Blocks

Quicksort: Visualizing Task Stealing

Although Quicksort is a recursive algorithm, no explicit recursion is needed in Threading Building Blocks. Aside from studying the code for Quicksort, look to this example as an illustration of task stealing and range splitting. Let’s go through how it would work using Threading Building Blocks.

Part of the magic is realizing that when you are splitting a parallel range, you are free to adjust the data in that range before considering it split and handing it off. It is safe to do this because when a range is being split, there is no concurrent use on that particular range.

The Quicksort range shown in Example 11-31 is where the partitioning step is done (using std::swap). Partitioning involves making sure that all the numbers on one side of a pivot are smaller than or equal to the pivot, and the numbers on the other side are larger than or equal to it. Without this step, you would end up with a bunch of sort sections in the array. They appear sorted overall only because of this partitioning. See Example 11-32 for the Quicksort functions.

Tip

Aha! Recursive splitting so that tasks fit available parallelism is very powerful.

Example 11-31. Quicksort range

template<typename RandomAccessIterator, typename Compare> struct quick_sort_range { static const size_t grainsize = 500; const Compare &comp; RandomAccessIterator begin; size_t size; quick_sort_range( RandomAccessIterator begin_, size_t size_, const Compare &comp_ ) : comp(comp_), begin(begin_), size(size_) ...