Parallel sorting

After my problems with parallel_scan, I approached parallel_sort with some trepidation. I was pleasantly surprised when parallel_sort worked as advertised. (I did have a few problems, but these were related to my C++ skills and not to TBB directly.)

The simple program shown below generates a vector of randomly-spaced, three-dimensional points and sorts them in ascending order based on their distance from the origin:

// example5.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <math.h>
#include <vector>
#include <iostream>
#include "tbb/task_scheduler_init.h"
#include "tbb/parallel_sort.h"

using namespace tbb;
using namespace std;

// 3-D point object
class point {
public:
    double x, y, z; // point coordinates
    // compute the distance from the point to the origin
    double radius() const { return sqrt(x*x + y*y + z*z); }
    // operator that determines which point is closer to the origin
    bool operator< (const point& that) const { return radius() < that.radius(); }
};

int _tmain(int argc, _TCHAR* argv[])
{
    // create a vector of points randomly distributed in space
    vector<point> points(10000);
    for(size_t i=0; i<points.size(); i++) {
        points[i].x = rand();
        points[i].y = rand();
        points[i].z = rand();
    }

    // do a parallel sort of the points
    task_scheduler_init init;
    // provide iterators to the beginning and end of the vector and
    // a function object for ordering the points
    parallel_sort(points.begin(), points.end(), std::less<point>());

    // check to make sure the points are sorted correctly
    for(size_t i=1; i<points.size(); i++)
        if(points[i].radius() < points[i-1].radius()) {
            cout << "Error: vector is not sorted correctly starting at location" << i << endl;
            return 1;
        }

    // output the sorted radii
    for(size_t i=0; i<points.size(); i++)
        cout << points[i].radius() << endl;

    return 0;
}

There really isn’t a lot to say about this program. The call to parallel_sort is on line 38. I just passed it a pair of iterators that point to the beginning and end of the vector of point objects. I also passed a function object, less, that makes use of the < operator (line 21) and radius method (line 19) in point to determine which 3-D point is closer to the origin. Upon return from parallel_sort, the points are properly ordered by their distance from the origin. It’s really no harder than calling a standard sort subroutine, with the added benefit of a speedup from parallel execution.

You can also do this with standard arrays instead of STL objects like vectors and lists. Just pass pointers to the beginning and ending of the array instead of iterators. And, obviously, you can sort in a different direction by supplying a different function object, e.g. greater.

Here’s the source code for this example if you want to try it.

About these ads