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 3.- Parallel Algorithms] 11 12[: 13 14[h4[_Parallel Algorithms]] 15[: 16This table provides a brief description of the parallel algorithms of the library. 17 18 19[*[teletype] 20`` 21 | | | | 22 Algorithm |Stable | Additional memory |Best, average, and worst case | 23 ----------------------+-------+------------------------+------------------------------+ 24 block_indirect_sort | no |block_size * num_threads| N, N LogN , N LogN | 25 sample_sort | yes | N | N, N LogN , N LogN | 26 parallel_stable_sort | yes | N / 2 | N, N LogN , N LogN | 27 | | | | 28`` 29] 30 31* *Sample_sort* is a implementation of the [*[@ https://en.wikipedia.org/wiki/Samplesort Samplesort algorithm]] done by Francisco Tapia. 32 33* *Parallel_stable_sort* is based on the samplesort algorithm, but using a half of the memory used by sample_sort, conceived and implemented by Francisco Tapia. 34 35* *Block_indirect_sort* is a novel parallel sort algorithm, very fast, with low additional memory consumption, conceived and implemented by Francisco Tapia. 36 37The *block_size* is an internal parameter of the algorithm, which in order to achieve the 38highest speed, changes according to the size of the objects to sort according to the next table. The strings use a block_size of 128. 39 40[*[teletype] 41`` 42 | | | | | | | | 43object size (bytes) | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 - | 44--------------------------------+--------+---------+---------+---------+---------+---------+----------+ 45block_size (number of elements) | 4096 | 2048 | 1024 | 768 | 512 | 256 | 128 | 46 | | | | | | | | 47`` 48] 49] 50 51[h4[_Thread Specification]] 52[: 53 54The parallel algorithms have a integer parameter indicating the *number of threads* to use in the sorting process, 55which always is the last value in the call. 56 57The default value (if left unspecified) is the number of HW threads of 58the machine where the program is running provided by std::thread::hardware_concurrency(). 59If the number is 1 or 0, the algorithm runs with only 1 thread. 60 61The number of threads is not a fixed number, but is calculated in each execution. The number of threads passed can be greater 62than the number of hardware threads on the machine. We can pass 100 threads in a machine with 4 HW threads, and in the same mode we can pass a function as (std::thread::hardware_concurrency() / 4 ). If this value is 0, the program is executed with 1 thread. 63 64] 65 66[h4[_Programming]] 67[: 68You only need to include the file boost/sort/sort.hpp to use these algorithms. 69 70All the algorithms run in the namespace boost::sort 71 72[c++] 73`` 74 #include <boost/sort/sort.hpp> 75`` 76 77The parallel algorithms have 4 invocation formats: 78 79[c++] 80`` 81 82 algorithm ( first iterator, last iterator, comparison object, number of threads ) 83 algorithm ( first iterator, last iterator, comparison object ) 84 algorithm ( first iterator, last iterator, number of threads ) 85 algorithm ( first iterator, last iterator ) 86`` 87These algorithms need a *C++11 compliant compiler*, but don't need any other code or library. With older compilers correct operation isn't guaranteed. 88 89If the number of threads is unspecified, use the result of std::thread::hardware_concurrency() 90 91These algorithms use a [*comparison object], in the same way as the standard library sort algorithms. If you don't define it, 92the comparison object defaults to std::less, which uses the < operator internally for comparisons. 93 94These algorithms are [*exception safe], meaning that, the exceptions generated by the algorithms guarantee the integrity 95of the objects to sort, but not their relative order. If the exception is generated inside the objects (in the move or copy constructors) the results are undefined. 96 97] 98 99] 100 101[include block_indirect_sort.qbk] 102[include sample_sort.qbk] 103[include parallel_stable_sort.qbk] 104[include linux_parallel.qbk] 105[include windows_parallel.qbk] 106[endsect] 107 108 109 110