EQ2EMu/EQ2/source/depends/boost_1_72_0/libs/sort/doc/parallel.qbk

[/===========================================================================
 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]