## algorithm sort vs parallel_sort Beginner
474 Views

I have some questions about parallel_sort. When I tried to compare the performance of the parallel_sort() with sort(), why is that sort() is faster than the parallel_sort?

Is it because of the grainsize value which is 500?

And while sorting, I saw that the CPU usage is not that good, actually it utilizes CPU less than what the sort utilizes, why is that?

Is the load balancing an issue here and selecting a good pivot?

Sorry if I have too many questions, I just can't get the answers on my own. I have tried it with an input of 500000, 100000 and 10000 numbers to sort and unfortunately, sort() is better.

8 Replies Black Belt
474 Views

What system are you running on?

Jim Beginner
474 Views

What system are you running on?

Jim

OS: Windows Xp

Processor: Intel Pentium D 3.0Ghz (2 CPUs)

Memory: 1 Gb ram Black Belt
474 Views

Can you post a small example for us to examine?

Jim Dempsey Beginner
474 Views

Can you post a small example for us to examine?

Jim Dempsey

here is my code..

#include
#include
#include
#include
#include
#include "tbb/parallel_sort.h"
#include "tbb/tick_count.h"

using namespace std;
using namespace tbb;

int main(){
vector sList, pList;
string fileInput, numInput;

cout << "Quicksortn" << "Enter filename: ";
cin >> fileInput;

ifstream infile(fileInput.c_str());
if (!infile){
cout << "error";
return 0;
}
while (infile >> numInput){
//Filters the valid inputs
if (atoi(numInput.c_str()))
sList.push_back(atoi(numInput.c_str()));
}
infile.close();

pList = sList;

cout << endl << sList.size() << " numbers to sortn";

cout << "Parallel Implementation" << endl;
tick_count parallel_t0 = tick_count::now();
parallel_sort(pList.begin(), pList.end());
tick_count parallel_t1 = tick_count::now();
cout << "Done with parallel versionn";
cout << (parallel_t1 - parallel_t0).seconds()<< " seconds" << endl;

cout << "Serial Implementation" << endl;
tick_count serial_t0 = tick_count::now();
sort(sList.begin(), sList.end());
tick_count serial_t1 = tick_count::now();
cout << "Done with serial versionn";
cout << (serial_t1 - serial_t0).seconds()<< " seconds" << endl;

for (long i = 0; i < sList.size(); ++i) {
if (sList != pList) {
cout << "ERROR: Serial and Parallel Results are Different!" << endl;
cout << sList << " " << pList << "position " << i << endl;
break;
}
}
cout << " Done validating results." << endl;
cout << "Resulting in a speedup of " << (serial_t1 - serial_t0).seconds() / (parallel_t1 - parallel_t0).seconds() << endl;

return 0;

}

I dont know how to attach file here in this site so I uploaded it here

Tell me if there is something wrong with my code. Thanks.. Advance merry christmas.. Black Belt
474 Views

Try this change

vector sList;
concurrent_vector pList;

Jim Dempsey Employee
474 Views

I checked the above test, and I must admit that tbb::parallel_sort is slower than std::sort for the given workload, even with two threads. I do not think concurrent_vector will improve things here, because the vector size is constant and so benefits of concurrent_vector are not needed.

I will look at what could be improved in the parallel_sort algorithm. Thanks for raising the issue! Beginner
474 Views

Alexey Kukanov, what do you think is/are the reason/s behind this? But when you somehow visualize it, it must be faster. Inform me as soon as possible if there is any improvement in the tbb::parallel_sort. Employee
474 Views
So far we've found that the problem is Windows-specific. If the example is run with a single thread ("task_scheduler_init init(1);"), the slowdown of tbb::parallel_sort compared to std::sort is 2x on Windows, but only about 5% on Linux. Evidently there isan importantcompiler, STL, or OS difference.
We'll let you know when we figure out more. 