123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109 |
- [/===========================================================================
- Copyright (c) 2017 Steven Ross, Francisco Tapia, Orson Peters
- Distributed under the Boost Software License, Version 1.0
- See accompanying file LICENSE_1_0.txt or copy at
- http://www.boost.org/LICENSE_1_0.txt
- =============================================================================/]
- [section:parallel 3.- Parallel Algorithms]
- [:
- [h4[_Parallel Algorithms]]
- [:
- This table provides a brief description of the parallel algorithms of the library.
- [*[teletype]
- ``
- | | | |
- Algorithm |Stable | Additional memory |Best, average, and worst case |
- ----------------------+-------+------------------------+------------------------------+
- block_indirect_sort | no |block_size * num_threads| N, N LogN , N LogN |
- sample_sort | yes | N | N, N LogN , N LogN |
- parallel_stable_sort | yes | N / 2 | N, N LogN , N LogN |
- | | | |
- ``
- ]
- * *Sample_sort* is a implementation of the [*[@ https://en.wikipedia.org/wiki/Samplesort Samplesort algorithm]] done by Francisco Tapia.
- * *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.
- * *Block_indirect_sort* is a novel parallel sort algorithm, very fast, with low additional memory consumption, conceived and implemented by Francisco Tapia.
- The *block_size* is an internal parameter of the algorithm, which in order to achieve the
- highest speed, changes according to the size of the objects to sort according to the next table. The strings use a block_size of 128.
- [*[teletype]
- ``
- | | | | | | | |
- object size (bytes) | 1 - 15 | 16 - 31 | 32 - 63 | 64 - 127|128 - 255|256 - 511| 512 - |
- --------------------------------+--------+---------+---------+---------+---------+---------+----------+
- block_size (number of elements) | 4096 | 2048 | 1024 | 768 | 512 | 256 | 128 |
- | | | | | | | |
- ``
- ]
- ]
- [h4[_Thread Specification]]
- [:
- The parallel algorithms have a integer parameter indicating the *number of threads* to use in the sorting process,
- which always is the last value in the call.
- The default value (if left unspecified) is the number of HW threads of
- the machine where the program is running provided by std::thread::hardware_concurrency().
- If the number is 1 or 0, the algorithm runs with only 1 thread.
- The number of threads is not a fixed number, but is calculated in each execution. The number of threads passed can be greater
- than 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.
- ]
- [h4[_Programming]]
- [:
- You only need to include the file boost/sort/sort.hpp to use these algorithms.
- All the algorithms run in the namespace boost::sort
- [c++]
- ``
- #include <boost/sort/sort.hpp>
- ``
- The parallel algorithms have 4 invocation formats:
- [c++]
- ``
- algorithm ( first iterator, last iterator, comparison object, number of threads )
- algorithm ( first iterator, last iterator, comparison object )
- algorithm ( first iterator, last iterator, number of threads )
- algorithm ( first iterator, last iterator )
- ``
- These algorithms need a *C++11 compliant compiler*, but don't need any other code or library. With older compilers correct operation isn't guaranteed.
- If the number of threads is unspecified, use the result of std::thread::hardware_concurrency()
- These algorithms use a [*comparison object], in the same way as the standard library sort algorithms. If you don't define it,
- the comparison object defaults to std::less, which uses the < operator internally for comparisons.
- These algorithms are [*exception safe], meaning that, the exceptions generated by the algorithms guarantee the integrity
- of 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.
- ]
- ]
- [include block_indirect_sort.qbk]
- [include sample_sort.qbk]
- [include parallel_stable_sort.qbk]
- [include linux_parallel.qbk]
- [include windows_parallel.qbk]
- [endsect]
|