1[/=========================================================================== 2 Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters 3 4 5 Distributed under the Boost Software License, Version 1.0 6 See accompanying file LICENSE_1_0.txt or copy at 7 http://www.boost.org/LICENSE_1_0.txt 8=============================================================================/] 9 10[section:parallel_stable_sort 3.3.- Parallel_stable_sort] 11[section:parallel_description Description] 12[: 13This is an adaptation of the [*[@https://en.wikipedia.org/wiki/Samplesort Samplesort]] algorithm, 14using an additional memory a half of the memory used by the data 15(the original algorithm uses an additional memory as the used by the data). 16 17It is a highly efficient [*parallel stable sort], optimized for use with many threads. 18 19 20 21[*[teletype] 22`` 23 | | | | 24 Algorithm |Stable | Additional memory |Best, average, and worst case | 25 ----------------------+-------+------------------------+------------------------------+ 26 parallel_stable_sort | yes | N / 2 | N, N LogN , N LogN | 27 | | | | 28`` 29] 30 31You can see their performance in the [*[link sort.parallel.linux_parallel Benchmarks]] chapter 32] 33[endsect] 34 35[section:parallel_programming Programming] 36[: 37[h4[_Thread specification]] 38 39[: 40This algorithm has an integer parameter indicating the *number of threads* to use in the sorting process, 41which always is the last value in the call. 42 43The default value (if left unspecified) is the number of HW threads of 44the machine where the program is running provided by std::thread::hardware_concurrency(). 45If the number is 1 or 0, the algorithm runs with only 1 thread. 46 47The number of threads is not a fixed number, but is calculated in each execution. The number of threads passed can be greater 48than the number of hardware threads on the machine. We can pass 100 threads in a machine with 4 HW threads, 49and in the same mode we can pass a function as (std::thread::hardware_concurrency() / 4 ). 50If this value is 0, the program is executed with 1 thread. 51 52] 53 54 55[h4[_Programming]] 56[: 57You only need to include the file boost/sort/sort.hpp to use this code. 58 59This algorithm run in the namespace boost::sort. 60 61[c++] 62`` 63 #include <boost/sort/sort.hpp> 64 65 66 template <class iter_t> 67 void parallel_stable_sort (iter_t first, iter_t last); 68 69 template <class iter_t, typename compare> 70 void parallel_stable_sort (iter_t first, iter_t last, compare comp); 71 72 template <class iter_t> 73 void parallel_stable_sort (iter_t first, iter_t last, uint32_t num_thread); 74 75 template <class iter_t, typename compare> 76 void parallel_stable_sort (iter_t first, iter_t last, compare comp, uint32_t num_thread); 77 78`` 79 80This algorithm needs a *C++11 compliant compiler*, and doesn't need any other code or library. Correct operation is not guaranteed with older compilers. 81 82If the number of threads is unspecified, this uses the result of std::thread::hardware_concurrency(). 83 84This algorithm uses a *comparison object*, in the same way as the standard library sort 85algorithms. If not defined, the comparison object is std::less, which uses 86the < operator internally. 87 88This algorithm is [*exception safe], meaning that, the exceptions generated by the algorithm 89guarantee the integrity of the objects to sort, but not their relative order. If the exception 90is generated inside the objects (in the move or in the copy constructor.. ) the results can be 91unpredictable. 92 93] 94] 95[endsect] 96[endsect] 97 98 99 100