110 lines
4.6 KiB
Plaintext
110 lines
4.6 KiB
Plaintext
[/===========================================================================
|
|
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]
|
|
|
|
|
|
|