C++

Paralelní algoritmy a zásady provádění

Využijte paralelní STL C++17 k paralelizaci třídění, transformace a redukce se zásadami provádění. Pochopte, kdy pomáhá paralelismus, Amdahlův zákon a praktický návrh fondu závitů.

Paralelní STL — Snadný paralelismus

C++17 přidal spouštěcí zásady k většině funkcí. Předáním zásady jako prvního argumentu sdělíte implementaci, aby paralelizovala algoritmus – potenciálně pomocí více vláken, SIMD nebo obojího – beze změny jakéhokoli dalšího kódu.

Toto je nejjednodušší způsob, jak přidat paralelismus do C++: vezměte své stávající volánístd::sort,std::transformnebostd::for_each, přidejte předstd::execution::para nechte implementaci, aby se postarala o zbytek. Samozřejmě musíte zajistit, aby vaše operace byly bezpečné pro souběžné provádění (žádné závody dat v predikátech, žádný sdílený měnitelný stav).

Vysvětlení zásad provádění

Vjsou definovány tři standardní zásady provádění. Každý poskytuje různé záruky paralelismu a vektorizace.

execution_policies.cpp
#include <algorithm>
#include <execution>
#include <vector>
#include <iostream>
#include <chrono>

int main() {
    std::vector<int> data(10'000'000);
    std::iota(data.begin(), data.end(), 0);

    // Sequential — same as no policy
    auto t1 = std::chrono::high_resolution_clock::now();
    std::sort(std::execution::seq, data.begin(), data.end(),
              std::greater<>{});
    auto t2 = std::chrono::high_resolution_clock::now();

    // Parallel — may use multiple threads
    std::sort(std::execution::par, data.begin(), data.end());
    auto t3 = std::chrono::high_resolution_clock::now();

    // Parallel + vectorized — threads AND SIMD
    std::sort(std::execution::par_unseq, data.begin(), data.end(),
              std::greater<>{});
    auto t4 = std::chrono::high_resolution_clock::now();

    auto ms = [](auto a, auto b) {
        return std::chrono::duration_cast<std::chrono::milliseconds>(b - a).count();
    };
    std::cout << "seq: " << ms(t1, t2) << "ms\n";
    std::cout << "par: " << ms(t2, t3) << "ms\n";
    std::cout << "par_unseq: " << ms(t3, t4) << "ms\n";
    return 0;
}

std::reduce vs std::accumulate

std::accumulatezpracovává prvky striktně zleva doprava a nelze je paralelizovat.std::reduce(C++17) umožňuje implementaci zpracovávat prvky v jakémkoli pořadí a kombinovat dílčí výsledky – což umožňuje paralelní provádění. Abyreduceprodukoval správné výsledky, musí být operace asociativní a komutativní.

reduce_demo.cpp
#include <numeric>
#include <execution>
#include <vector>
#include <iostream>

int main() {
    std::vector<double> data(1'000'000, 1.0);

    // Sequential accumulate — always left-to-right
    double sum1 = std::accumulate(data.begin(), data.end(), 0.0);

    // Parallel reduce — may split and combine in any order
    double sum2 = std::reduce(std::execution::par,
                              data.begin(), data.end(), 0.0);

    // Transform-reduce: parallel dot product
    std::vector<double> a(1'000'000, 2.0);
    std::vector<double> b(1'000'000, 3.0);
    double dot = std::transform_reduce(
        std::execution::par,
        a.begin(), a.end(), b.begin(),
        0.0);  // default: multiply + add

    std::cout << "accumulate: " << sum1 << "\n";
    std::cout << "reduce:     " << sum2 << "\n";
    std::cout << "dot product: " << dot << "\n";  // 6'000'000
    return 0;
}
Úskalí

Při použití zásad paralelního provádění může být volatelná (predikát, transformační funkce, operátor redukce), kterou předáte algoritmu, vyvolána současně z více vláken. Pokud vaše volatelné přistupuje ke sdílenému proměnlivému stavu, máte datový závod:

int count = 0;
std::for_each(std::execution::par, v.begin(), v.end(),
    [&count](int x) {
        if (x > 0) ++count;  // DATA RACE! Multiple threads increment count
    });

Use std::atomic, thread-local accumulators, or better yet, use std::reduce / std::count_if, které bezpečně zpracovávají agregaci.

Amdahl's Law — When Parallelism Helps

Amdahl's law states that the maximum speedup from parallelism is limited by the sequential fraction of your program. If 10% of the work must be done sequentially, then even with infinite threads, the maximum speedup is 10x.

Speedup = 1 / (S + P/N), where S is the sequential fraction, P is the parallel fraction, and N is the number of threads.

Parallelism also has overhead: thread creation, synchronization, cache contention, and false sharing. For small data sets, the overhead can exceed the benefit. Rules of thumb:

- Sort: Parallelstd::sorttypically helps above ~100K elements.
- Transform/for_each: Benefits above ~10K elements with non-trivial work per element.
- Reduce: Benefits above ~100K elements or with expensive operations.
- Always measure — profile with and withoutstd::execution::par.

Practical Thread Pool Overview

The C++ standard does not provide a thread pool (as of C++23), but the pattern is straightforward: a fixed set of worker threads pulls tasks from a shared queue. Here is a minimal sketch.

thread_pool.cpp
#include <iostream>
#include <thread>
#include <mutex>
#include <condition_variable>
#include <queue>
#include <functional>
#include <vector>

class ThreadPool {
    std::vector<std::thread> workers_;
    std::queue<std::function<void()>> tasks_;
    std::mutex mtx_;
    std::condition_variable cv_;
    bool stop_ = false;

public:
    explicit ThreadPool(size_t n) {
        for (size_t i = 0; i < n; ++i) {
            workers_.emplace_back([this] {
                while (true) {
                    std::function<void()> task;
                    {
                        std::unique_lock lock(mtx_);
                        cv_.wait(lock, [this] {
                            return stop_ || !tasks_.empty();
                        });
                        if (stop_ && tasks_.empty()) return;
                        task = std::move(tasks_.front());
                        tasks_.pop();
                    }
                    task();  // run outside the lock
                }
            });
        }
    }

    void enqueue(std::function<void()> task) {
        {
            std::lock_guard lock(mtx_);
            tasks_.push(std::move(task));
        }
        cv_.notify_one();
    }

    ~ThreadPool() {
        {
            std::lock_guard lock(mtx_);
            stop_ = true;
        }
        cv_.notify_all();
        for (auto& w : workers_) w.join();
    }
};

int main() {
    ThreadPool pool(4);
    for (int i = 0; i < 20; ++i) {
        pool.enqueue([i] {
            std::cout << "Task " << i << " on thread "
                      << std::this_thread::get_id() << "\n";
        });
    }
    // pool destructor waits for all tasks
    return 0;
}
Osvědčený postup

Preferstd::execution::parover hand-rolled parallelism for standard algorithms — the implementation knows your hardware. Always verify that your callable is free of data races and side effects. Usestd::reduceinstead ofstd::accumulatewhen you need parallelism. Benchmark with realistic data sizes; for small inputs, sequential may be faster. Remember thatpar_unseqforbids calling anything that acquires a lock (including memory allocation on some platforms).

Klíčové poznatky
  • C++17 execution policies (seq,par,par_unseq) add parallelism to standard algorithms with minimal code changes
  • std::reduceis the parallel-friendly replacement forstd::accumulate— your operation must be associative and commutative
  • Amdahl's law limits speedup: the sequential portion of your code becomes the bottleneck
  • Parallel algorithms have overhead — only beneficial for sufficiently large data sets or expensive per-element work
  • Always ensure callables passed to parallel algorithms are free of data races
  • Thread pools reuse a fixed set of threads to avoid the cost of thread creation for many small tasks

Kvíz — Otestujte své znalosti

(15 XP)

1. Why can't`std::accumulate`be used with execution policies?

2. What constraint does`std::execution::par_unseq`place on the callable?

3. Jaké je podle Amdahlova zákona maximální zrychlení, pokud je 20 % programu sekvenční?

Předchozí
Atomové operace a uspořádání paměti
Další
C++17: The Practical Standard