Re: [boost] [SORT] Parallel Algorithms

On Sun, Mar 29, 2015 at 6:25 AM Francisco José Tapia wrote:

Hi Steven

Thanks by your message.

Until now , I had been focused mainly in the algorithms, and I didn't dedicate many time to others things as the test format and the integration with boost::sort.Now, the first things to do are :

- Try to detect when the data are ordered,

Just verify that each successive element is not less than the previous. If inputs are unique (or completely identical if they compare the same), then you can compare results with those of std::sort.

- Revise in deep your library and code , in order to adapt the test and benchmarks to the procedures used in your library

About the object used in the benchmarks, we can do something simple. Reburcio is a very small class in the file Benchmarks/GCC/algorithm/reburcio.hpp. Please rewrite and send me, and only need to recompile the benchmarks.

I suggest renaming the variables to be clearer, but here's the idea: template struct intarray { uint32_t M[NN]; bool operator < ( const intarray &R) const{ for (int i = 0; i < NN; ++i) { if (M[i] != R.M[i]) { return M[i] < R.M[i]; } } return false; } }; Use /libs/sort/example/randomgen.cpp (b2 libs/sort/randomgen --tune will build the binary in the libs/sort dir) to generate randomized input files, and memcpy them into arrays of intarray to fill them with the data to sort. This will emulate the large non-vector objects the indirect sorting approach you've designed is optimized for, and will fill the entire object with randomized contents, along with having a full (default) copy constructor. You can use strings in the place of intarray also for testing strings; I randomize them by just using the >> operator on strings to read them in; it will automatically break on some characters, causing the strings to have randomized length.

*About the parts to include*

With the parallel unstable sort, all the algorithms I examined have the same approach, and due this, similar performances. The range of decision is small.

The goal is provide algorithms independent of any library or Operating System, fast , robust and easy to use. The idea of to do the same than a company is the origin of many Free SW, think about Oracle and MySQL, Internet Explorer and Firefox. Even the C++ standard, is to do the same than many companies are doing since many years ago, each with its own way. The final users are grateful because simplify our work.

TBB is available in Windows, Linux and Os X. With others operating system ( by example Android and all the real time OS), you must recompile all the source code, and I have not clear about the dynamic linking of TBB in these operating systems. Many small machines don't have task scheduler, but have threads. To force to recompile TBB for to use a parallel sort is like force to rent a bus, for to transport only one person.

Who wants to do a parallel sort on Android? The OS often only gives you one core (depending on priorities), and it would burn the battery at ridiculous speed. I just don't see the use case, unless you can provide some advantage in some fairly common use case, and it would have to fully match tbb's features to within a few percent, including efficiency on already-sorted input.

Our code have similar performance, small code, independent of any Operating System, of any other code or library. If you are C++11 compliant you have parallel sort. I think, we must include sort, parallel sort, stable sort and parallel stable sort. Perhaps, too, sample sort, but it's less important

Your stable sort and parallel stable sort look promising, and sample sort is a possibility. I recommend concentrating on them for now.