Chapter 10: Chapter 10. Parallel algorithms

Introduction

The introduction connects earlier work on concurrent code and thread pools to the chapter’s focus on C++17 standard parallel algorithms.

• C++17 parallel algorithms focus: Describe how this chapter moves from the earlier discussion of designing concurrent code, illustrated with parallel algorithms, to parallel algorithms provided by the C++17 standard.
  Why it matters: This distinction sets up why the chapter examines standard-library facilities rather than another hand-written parallel implementation.

Key terms: C++17 parallel algorithms, parallel algorithms, thread pools

10.1 Parallelizing the standard library algorithms

Introduces C++17 parallel-algorithm overloads, showing how execution policies permit parallel work and change complexity expectations.

• Parallel algorithm overloads: Describe how C++17 adds overloads of range algorithms such as std::find and std::transform, with an execution policy as a new first argument.
  Why it matters: This is how callers request parallel execution without switching to a different algorithm.
• Parallel permission and work tradeoff: Explain that std::execution::par permits, but does not require, multithreaded execution, and that specifying a policy usually relaxes complexity requirements because parallel implementations may do more total work while finishing sooner.
  Why it matters: A parallel policy neither guarantees multiple threads nor promises less total work.

Key terms: parallel algorithms, execution policy, overloads, std::execution::par, complexity, parallelism

10.2 Execution policies

Introduces the three standard execution policies, the objects used to pass them to algorithms, and the limits on creating policies.

• Standard policy names and objects: State the three standard execution policy classes and their corresponding objects: sequenced_policy and seq, parallel_policy and par, and parallel_unsequenced_policy and par_unseq. Explain that they are defined in <execution> and that the objects are passed to algorithms.
  Why it matters: These are the names you use when choosing a policy for a standard algorithm.
• Policy creation and extension limits: Explain that users cannot rely on constructing standard policy objects themselves, apart from copying the supplied objects, because initialization may be special. Distinguish implementation-defined additional policies from user-defined ones: implementations may add policies, but users cannot define their own.
  Why it matters: It clarifies which policy objects you can safely use and who can provide additional policies.

Key terms: std::execution::sequenced_policy, std::execution::parallel_policy, std::execution::parallel_unsequenced_policy, std::execution::seq, std::execution::par, std::execution::par_unseq, execution policies, implementation-specific behavior

10.2.1 General effects of specifying an execution policy

Specifying an execution policy changes an algorithm’s complexity guarantees, exception behavior, and where and when its steps may run.

• Execution policy complexity changes: Explain that policy-based algorithms may perform extra core operations and incur scheduling overhead in pursuit of lower elapsed time. State that an exact or at-most operation count can become an O(expression) bound, with the extra factor depending on the library and platform rather than the input data.
  Why it matters: A parallel algorithm can do more operations yet still finish sooner.
• Policy based exception behavior: Describe what happens to uncaught exceptions under standard execution policies: they cause std::terminate, while std::bad_alloc may be thrown if the library cannot obtain memory for internal operations. Distinguish std::execution::seq from calling the algorithm without a policy, which can propagate an exception.
  Why it matters: Even the sequenced policy changes how an algorithm call handles exceptions.
• Algorithm step execution constraints: Explain that an execution policy determines which execution agents perform algorithm steps and what ordering, interleaving, or parallel execution of those steps is permitted. State that these execution constraints are the fundamental aspect that differs among the standard policies.
  Why it matters: These constraints determine which assumptions code inside a parallel algorithm can safely make.

Key terms: execution policy, algorithm complexity, O(some-expression), scheduling overhead, std::terminate, std::bad_alloc, std::execution::seq, uncaught exceptions, execution agents, ordering constraints

10.2.2 std::execution::sequenced_policy

The section explains that sequenced execution stays on the calling thread but does not guarantee the operation order of an algorithm call without a policy.

• Single-threaded sequenced execution: Explain that std::execution::sequenced_policy runs every operation on the calling thread, so it provides no parallelism, while remaining an execution policy with the standard policies’ consequences for complexity and exceptions.
  Why it matters: A sequenced policy changes an algorithm’s guarantees without making it parallel.
• Definite but unspecified operation order: Distinguish the guarantee that operations occur in some definite, non-interleaved order from a guarantee of any particular order. Explain that the order may vary between calls and need not match the corresponding overload without an execution policy.
  Why it matters: Code must not depend on the sequenced-policy overload visiting elements in the same order as the ordinary overload.
• Permitted callable synchronization: Describe why iterators, values, and callable objects may use synchronization and rely on operations running on one thread, but must not rely on the order in which those operations are invoked.
  Why it matters: These guarantees determine what assumptions code passed to the algorithm may safely make.

Key terms: std::execution::sequenced_policy, execution policy, calling thread, definite order, unspecified order, std::for_each, iterators, values, callable objects, synchronization mechanisms

10.2.3 std::execution::parallel_policy

This section explains how the parallel execution policy schedules algorithm operations and what callers must do to avoid data races.

• Parallel execution guarantees: Describe where operations under std::execution::parallel_policy may run and what ordering and thread-identity guarantees they have.
  Why it matters: These guarantees determine what code is safe to run inside a parallel algorithm.
• Parallel callable requirements: Explain when iterators, values, and callable objects are suitable for the parallel policy, including the roles of data races, thread assumptions, and ordering between elements.
  Why it matters: Most ordinary algorithm uses can be parallelized, but shared state and ordering requirements can make a call invalid or unsuitable.
• Shared counter race and remedies: Explain why modifying a captured plain counter from every parallel lambda invocation is undefined behavior, and describe the synchronization options and their likely cost.
  Why it matters: The counter example shows that a parallel call must be valid by its requirements, not merely happen to run safely on one implementation.

Key terms: std::execution::parallel_policy, parallel execution policy, operations, iterators, values, callable objects, data races, ordering between elements, undefined behavior, data race

10.2.4 std::execution::parallel_unsequenced_policy

This section explains the freedom the parallel unsequenced policy gives an algorithm and the resulting restrictions on the operations supplied to it.

• Unsequenced execution freedom: Explain that the parallel unsequenced policy gives the library its greatest scope to parallelize an algorithm: steps may run on unspecified threads, without ordering or sequencing between them, and an operation may be interleaved with another or migrate between threads.
  Why it matters: You cannot assume an operation runs uninterrupted on one thread or in a particular order relative to another.
• Operation and synchronization restrictions: Describe why this policy imposes the strictest requirements on supplied iterators, values, and callable objects: their operations must not synchronize, directly or through called functions, and must not modify state shared between threads or elements. They must operate only on the relevant element or data accessible from it.
  Why it matters: These restrictions let the library use its broad execution freedom without operations depending on synchronization or shared changes.

Key terms: std::execution::parallel_unsequenced_policy, unordered, unsequenced, threads of execution, iterators, values, callable objects, synchronization, relevant element

10.3 The parallel algorithms from the C++ Standard Library

This section identifies which standard algorithms accept execution policies and explains why their policy overloads require stronger iterator guarantees.

• Parallel algorithm coverage: Describe how most algorithms in <algorithm> and <numeric> have execution-policy overloads, while std::accumulate remains serial and std::reduce provides a generalized alternative. Explain why a reduction can produce a nondeterministic result if its operation is not both associative and commutative.
  Why it matters: Choosing a policy-enabled algorithm also means accounting for how parallel execution may combine results.
• Policy overload signatures: Explain that each normal overload of a covered algorithm gains a variant with the execution policy as its first argument, followed by the normal arguments. State that policy overloads require Forward Iterators wherever the normal overload permits Input or Output Iterators.
  Why it matters: The policy argument changes both how an algorithm is called and, for some algorithms, which iterators are valid.
• Multipass iterator requirement: Explain why single-pass Input and Output Iterators cannot support the independent iterator copies needed for parallel work, whereas Forward Iterators can be copied and advanced without invalidating other copies. Distinguish Forward Iterators from Bidirectional and Random Access Iterators by the additional movement each permits.
  Why it matters: Iterator guarantees determine whether threads can work on different parts of a sequence without serializing access to one iterator.

Key terms: execution policy, std::accumulate, std::reduce, associative, commutative, overload, Input Iterator, Output Iterator, Forward Iterator, single-pass

10.3.1 Examples of using parallel algorithms

This section shows how to apply parallel algorithms to independent elements and how execution-policy choices affect synchronization and access to the container.

• Independent element processing: Explain how a parallel Standard Library algorithm can apply an operation to each element of a range when the elements are independent, while leaving the division of work among threads to the library.
  Why it matters: Independence between elements is what makes the loop a natural candidate for parallel execution.
• Execution policy choice: Distinguish the usual choice of std::execution::par from the possible use of std::execution::par_unseq: the latter permits more reordering and interleaving but imposes tighter requirements, and neither policy guarantees a particular amount of parallelism.
  Why it matters: A more permissive policy may offer performance opportunities only when the code meets its restrictions.
• Synchronization and lock granularity: Explain why per-element internal mutexes make the first class example unsuitable for std::execution::par_unseq, and how locking the whole container outside the algorithm makes the second example suitable at the cost of blocking other threads for the entire operation.
  Why it matters: The placement of synchronization determines both which policy is safe and how long other threads must wait.

Key terms: parallel loop, embarrassingly parallel, range, std::execution::par, std::execution::par_unseq, execution policy, internal mutex, per-element mutex, whole-container mutex, external synchronization

10.3.2 Counting visits

This section uses website-log visit counting to show how std::transform_reduce can parse independent entries, combine partial totals, and delegate parallel execution to the Standard Library.

• Independent parsing and aggregation: Explain why website-log analysis suits parallel algorithms: each line can be parsed independently, and partial visit counts can be combined as long as the final totals are correct.
  Why it matters: Separating independent work from aggregation makes it easier to see where parallelism is possible.
• Visit counting with transform_reduce: Describe how count_visits_per_page wraps std::transform_reduce: parse_log_line extracts information from entries, and a reduction operation combines the results into per-page visit counts.
  Why it matters: This connects the log-analysis task to the algorithm’s transformation and reduction roles.
• Four visit combination cases: Explain why combine_visits needs four call-operator overloads: it must combine two log_info values, a log_info and a map in either order, and two maps; this rules out a simple lambda for the reduction.
  Why it matters: The reduction must handle the different forms that intermediate results can take.
• Parallel policy and delegation: Explain that passing std::execution::par lets the std::transform_reduce implementation use available hardware in parallel, leaving the difficult parallel implementation to the Standard Library.
  Why it matters: Using the policy lets the programmer focus on the desired result rather than manually implementing parallelism.

Key terms: log entries, parse_log_line, aggregate, parallel algorithms, count_visits_per_page, std::transform_reduce, reduction operation, combine_visits, log_info, map

10.4 Summary

The chapter recap connects using C++ Standard Library parallel algorithms with choosing execution policies and applying an algorithm in real code.