algorithm sort vs parallel_sort

[mblizz]

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.

[jimdempseyatthecove]

What system are you running on?

Jim

[mblizz]

Quoting - jimdempseyatthecove

What system are you running on?

Jim

OS: Windows Xp

Processor: Intel Pentium D 3.0Ghz (2 CPUs)

Memory: 1 Gb ram

[jimdempseyatthecove]

Can you post a small example for us to examine?

Jim Dempsey

[mblizz]

Quoting - jimdempseyatthecove

Can you post a small example for us to examine?

Jim Dempsey

here is my code..

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

using namespace std;
using namespace tbb;



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

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

ifstream infile(fileInput.c_str());
if (!infile){
cout << "error";
return 0;
}
cout << "Reading file... Please wait";
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

http://www.mediafire.com/?sharekey=7ed570201efad75dd2db6fb9a8902bda

Tell me if there is something wrong with my code. Thanks.. Advance merry christmas..

[jimdempseyatthecove]

Try this change

vector sList;
concurrent_vector pList;

Jim Dempsey

[Alexey-Kukanov]

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!

[mblizz]

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.

[ARCH_R_Intel]

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.