Skip to content

Algorithms

The header algorithm.h and the corresponding Algorithms Module includes parallel implementations of common STL algorithms using the library primitives.

int c = futures::reduce(v.begin(), v.end(), 0); // parallel by
                                                // default
assert(c == 1250025000);

Like the C++20 ranges library, these algorithms accept both iterators or ranges as parameters.

int c = futures::reduce(v, 0); // parallel by default
assert(c == 1250025000);

Better future algorithms

This library includes:

  • Large set of the STL-like algorithms in terms of futures and executors
  • Easy access to async algorithms based on executors without requiring other external libraries
    • This is common with C++ execution policies, such as TTB.

Executors

Like other parallel functions defined in this library, these algorithms allow simple execution policies to be replaced by concrete executors.

futures::thread_pool pool(4);
auto ex = pool.get_executor();
futures::for_each(ex, v.begin(), v.begin() + 10, [](int x) {
    assert(x >= 0 && x <= 50000);
    long_task(x);
});

Parallel by default

Unless an alternative policy or executor is provided, all algorithms are executed in parallel by default whenever it is "reasonably safe" to do so. A parallel algorithm is considered "reasonably safe" if there are no implicit data races and deadlocks in its provided functors.

To execute algorithms sequentially, an appropriate executor or policy should be provided:

int c = futures::reduce(make_inline_executor(), v, 0); // sequential
                                                       // execution
assert(c == 1250025000);

int c = futures::reduce(futures::seq, v, 0); // sequential execution
assert(c == 1250025000);

Unless a policy is explicitly stated, all algorithms are parallel by default. These algorithms give us access to parallel algorithms that rely only on executors. This allows us to avoid of more complex libraries, such as TBB, to execute efficient parallel algorithms.

Compile time algorithms

Like in C++20, these algorithms can also be used in constexpr contexts with the default inline executor for these contexts.

constexpr std::array<int, 5> a = { 1, 2, 3, 4, 5 };
constexpr int n = futures::reduce(a);
constexpr std::array<int, n> b{};
assert(b.size() == 15);

This feature depends on an internal library implementation equivalent to std::is_constant_evaluated. This implementation is available in most compilers (MSVC 1925, GCC 6, Clang 9), even when C++20 is not available. The macro FUTURES_HAS_CONSTANT_EVALUATED can be used to identify if the feature is available.