skip to content

What does passing std::execution::par to std::sort require of your C++ code, and what does it not guarantee?

level: seniorimportance: should knowfreq 30%

answer

  1. C++17 overloads, first argument
  2. no data races in your callables
  3. exceptions end in terminate
  4. permission, not a promise
  5. libstdc++ needs TBB

basics

~20 s

std::execution::par lets std::sort run comparisons on several threads, so the comparator must be free of data races and must not modify its arguments; an exception escaping it calls std::terminate. It permits parallelism but does not promise it or any speedup.

solid answer

~40 s

C++17 added overloads taking an execution policy as the first argument: `std::sort(std::execution::par, v.begin(), v.end(), comp)`. `par` permits the library to call `comp` from threads it creates, so `comp` must be safe to call concurrently: it may not modify objects through its arguments, rely on their identity, or touch shared state without synchronisation. `par_unseq` and C++20's `unseq` additionally allow interleaving calls on one thread, so even a mutex inside the comparator risks deadlock. If any element access function exits via an exception, `std::terminate` is called instead of propagating it. Nothing obliges the library to use threads: libstdc++ runs serially unless `<tbb/tbb.h>` is found and TBB is linked, and libc++ ships the policies only under `-fexperimental-library`. Measure before assuming a speedup; C++26 adds the same policies to `std::ranges` algorithms.

code

cpp · 17 lines
cpp
#include <algorithm>
#include <cstdio>
#include <execution>
#include <random>
#include <vector>

int main() {
    std::vector<int> scores(1'000'000);
    std::mt19937 gen(42);
    std::uniform_int_distribution<int> dist(0, 100'000);
    for (int& s : scores) s = dist(gen);

    std::sort(std::execution::par, scores.begin(), scores.end(),
              [](int a, int b) { return a > b; });
    std::printf("top=%d sorted=%d\n", scores.front(),
                std::is_sorted(scores.begin(), scores.end(), std::greater<>{}));
}

go deeper

for a junior

Recognise the syntax: the policy object goes first, and std::execution::par asks for, but does not force, a parallel run.

for a middle

List the four policies and what each permits, and know that exceptions from the comparator end in std::terminate.

for a senior

Audit comparators for shared state before adding a policy, know libstdc++ needs TBB and libc++ needs -fexperimental-library, and benchmark the change.

for a principal

Decide whether parallel standard algorithms are worth the toolchain dependency and nondeterministic timing, versus an explicit task system the team already operates.

## What the policy overloads are C++17 standardised the Parallelism TS: most algorithms in `<algorithm>` and `<numeric>` gained an overload whose first parameter is an **execution policy** from `<execution>`: | Policy object | Type | Permits | |---|---|---| | `std::execution::seq` | `sequenced_policy` | nothing new: calls stay on the calling thread, in order | | `std::execution::par` | `parallel_policy` | calls on library-created threads | | `std::execution::par_unseq` | `parallel_unsequenced_policy` | threads **and** interleaved, vectorised calls | | `std::execution::unseq` (C++20) | `unsequenced_policy` | interleaved calls on the calling thread | `std::sort`, `std::stable_sort`, `std::partial_sort` and `std::nth_element` all have such overloads. Their semantics are those of the sequential call, with relaxed complexity: the parallel `nth_element`, for example, is specified as `O(N)` predicate applications and `O(N log N)` swaps. ## What it requires from your code The key word is **permits**. A policy grants the library freedoms, and every freedom is a requirement on the comparator and element type: - **No modification through arguments, no reliance on identity.** Comparators and predicates passed to parallel algorithms may not modify objects via their arguments, and the implementation may copy trivially copyable elements, so `&a` inside the comparator is not necessarily an element of your vector. - **No data races.** Under `par`, calls may run concurrently on different threads. A comparator that increments a shared counter, logs to a non-thread-safe sink or reads a cache it also fills is a data race, and that is undefined behaviour. - **No blocking under `unseq` or `par_unseq`.** Interleaved calls on one thread mean a mutex locked in one call can be needed by another call on the same thread; the standard notes this risks deadlock, and calling a vectorization-unsafe library function there is undefined behaviour. - **Exceptions terminate.** For all four standard policies, if a comparator or element operation exits via an exception, `std::terminate` is called. A parallel algorithm that needs temporary memory and cannot get it throws `std::bad_alloc` instead. - **Random access still required.** `std::sort` keeps its random-access iterator requirement; the parallel overloads of other algorithms raise input iterators to forward iterators. ## What it does not guarantee 1. **Parallelism.** The library may run everything on the calling thread. libstdc++ selects its TBB backend only when `<tbb/tbb.h>` is available (`_GLIBCXX_USE_TBB_PAR_BACKEND`), otherwise a serial backend; you also link `-ltbb`. 2. **Availability.** libc++ ships `<execution>` policies only under `-fexperimental-library`; without it, Apple clang 21 rejects `std::execution::par` with "no member named 'par' in namespace 'std::execution'". Its backend - serial, `std::thread` or libdispatch - is fixed when libc++ itself is configured. 3. **Speed.** Thread start-up, partitioning and merging cost something. Small ranges, cheap comparisons or a machine already saturated with other work can make `par` slower than `seq`. 4. **Determinism among ties.** `std::sort` with `par` is no more stable than without it. ## Which algorithms take a policy Not every algorithm has a parallel overload. The sorting family does - `sort`, `stable_sort`, `partial_sort`, `partial_sort_copy`, `nth_element`, `is_sorted` - and so do `transform`, `for_each`, `copy_if` and the numeric `reduce` and `transform_reduce`. The binary searches (`lower_bound`, `upper_bound`, `equal_range`, `binary_search`) have none, not even in C++26: a logarithmic search has too little work to split. `std::accumulate` has none either, because its strict left-to-right order is part of its contract; `std::reduce` exists largely to drop that order so it can be parallelised. A practical consequence for a leaderboard: you might sort the nightly snapshot with `par`, but every rank query afterwards is a sequential `lower_bound`, and that is the right design. ## Using it responsibly - Keep the comparator a pure function of its two arguments. - Benchmark against the sequential call at realistic sizes; keep the policy only where it pays. - Treat a throwing comparator as a bug: under a policy it terminates the process. - Keep the policy out of `constexpr` code paths: the policy overloads are not `constexpr`, unlike the sequential `std::sort` since C++20. - Prefer one parallel call over a big range to many parallel calls over small ones; the fixed cost per call is paid each time. - In C++26, `std::ranges::sort` and friends also accept an execution policy, with sized random-access ranges; check your standard library's status before relying on it.

  • What happens if the comparator throws inside std::sort(std::execution::par, ...)?
    `std::terminate` is called. For the standard policies an exception escaping an element access function is not propagated to the caller, unlike the sequential overload. The only exception a parallel algorithm itself reports is `std::bad_alloc` when it cannot get the temporary memory it needs for parallelisation.
  • Why can locking a std::mutex inside a comparator deadlock under std::execution::par_unseq but not under par?
    Under `par`, calls on one thread are indeterminately sequenced, so each call finishes before another on that thread starts, and a lock-guarded comparator is merely slow. Under `par_unseq` or `unseq`, calls on the same thread may be interleaved, so one call can hold the mutex while another on the same thread tries to acquire it, which is why the standard warns that blocking synchronisation risks deadlock.

  • Saying std::execution::par guarantees the sort runs on several threads
  • Believing exceptions from the comparator propagate to the caller
  • Using a mutex-guarded comparator under par_unseq
  • Assuming par is always faster than the sequential sort
  • Thinking a counting comparator is fine because sort is read-only

Assumes C++23; execution policies arrived in C++17, std::execution::unseq in C++20, and policy overloads of std::ranges algorithms only in C++26.