Parallel quicksort: recursion using Boost Bind?
I am working on making quicksort parallel and streams a first try. The non-thread version sorts correctly, but the thread doesn't work (not surprising). What I found interesting was when I was deleting threads, but kept up with boost :: bind calls that still don't work. If boost :: bind is not what I want, please suggest a suggestion. Bind seemed to be the easiest (or only) way to make my function work with upstreams.
void Quicksort( fVec &Array, const int Left, const int Right )
{
if( Right <= Left )
return;
int pivot = Left;
const int pivotNewIndex = Partition( Array, Left, Right, pivot );
// These function calls make it work fine
//Quicksort( Array, Left, pivotNewIndex - 1 );
//Quicksort( Array, pivotNewIndex + 1, Right );
// boost::bind calls only swaps one element, doesn't actually sort
boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 )();
boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right )();
// threaded version that doesn't work, same as above
//boost::thread threadA( boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 ) );
//threadA.join();
//boost::thread threadB( boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right ) );
//threadB.join();
}
source to share
The Boost binding more or less creates a functor that, when called, will call the desired function with the required arguments. In this case, you are creating a functor, but not calling it. Try:
boost::bind( &Quicksort, Array, Left, pivotNewIndex - 1 )();
boost::bind( &Quicksort, Array, pivotNewIndex + 1, Right )();
I guess the first argument is what it messed up. I think bind requires the arguments to be copyable and the links are not actually created, perhaps it is making a copy and passing a link to it, so nothing changes. Try:
boost::bind( &Quicksort, boost::ref(Array), Left, pivotNewIndex - 1 )();
boost::bind( &Quicksort, boost::ref(Array), pivotNewIndex + 1, Right )();
This will help you find out what fVec is and why you are not passing a pointer to the array of what you are sorting.
Also note that this method of threading is unlikely to provide much speedup, since since you get very small sorts, the overhead of starting and scheduling a new thread is much more than good (plus you will create a huge amount of thread that are bad). What you really want is a threadpool that runs on a small port of optimal size or larger and has a fixed number of threads. When sizes less than the limit are reached, it does everything sequentially (and for a smaller size, you obviously want to go from quicksort to insertion sort).
Also note that the order you attach results in serial execution anyway ... you want to attach to both threads after both threads have started.
source to share