Algorithmes parallèles et politiques d'exécution
Tirez parti de la STL parallèle de C++17 pour paralléliser le tri, la transformation et la réduction grâce aux politiques d'exécution. Comprenez quand le parallélisme est utile, la loi d'Amdahl et la conception pratique d'un pool de threads.
La STL parallèle — le parallélisme facile
C++17 a ajouté des politiques d'exécution à la plupart des fonctions de
C'est le moyen le plus simple d'ajouter du parallélisme en C++ : prenez votre appel existant à std::sort, std::transform ou std::for_each, ajoutez std::execution::par en tête, et laissez l'implémentation faire le reste. Bien sûr, vous devez vous assurer que vos opérations peuvent s'exécuter de manière concurrente en toute sécurité (pas de data races dans les prédicats, pas d'état modifiable partagé).
Les politiques d'exécution expliquées
Il existe trois politiques d'exécution standard définies dans
#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::accumulate traite les éléments strictement de gauche à droite et ne peut pas être parallélisé. std::reduce (C++17) permet à l'implémentation de traiter les éléments dans n'importe quel ordre et de combiner des résultats partiels — ce qui rend possible l'exécution parallèle. L'opération doit être associative et commutative pour que reduce produise des résultats corrects.
#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;
}Avec les politiques d'exécution parallèles, le callable (prédicat, fonction de transformation, opérateur de réduction) que vous passez à l'algorithme peut être invoqué simultanément depuis plusieurs threads. Si votre callable accède à un état modifiable partagé, vous avez une data race :
int count = 0;
std::for_each(std::execution::par, v.begin(), v.end(),
[&count](int x) {
if (x > 0) ++count; // DATA RACE ! Plusieurs threads incrémentent count
});Utilisez std::atomic, des accumulateurs locaux à chaque thread, ou mieux encore, std::reduce / std::count_if, qui gèrent l'agrégation en toute sécurité.
La loi d'Amdahl — quand le parallélisme est utile
La loi d'Amdahl énonce que l'accélération maximale apportée par le parallélisme est limitée par la fraction séquentielle de votre programme. Si 10 % du travail doit être effectué séquentiellement, alors même avec une infinité de threads, l'accélération maximale est de 10x.
Accélération = 1 / (S + P/N), où S est la fraction séquentielle, P la fraction parallèle et N le nombre de threads.
Le parallélisme a aussi un coût : création des threads, synchronisation, contention de cache et faux partage (false sharing). Pour de petits jeux de données, ce coût peut dépasser le bénéfice. Quelques règles empiriques :
- Tri : std::sort en parallèle est généralement utile au-delà d'environ 100K éléments.
- Transform/for_each : bénéfique au-delà d'environ 10K éléments avec un travail non trivial par élément.
- Reduce : bénéfique au-delà d'environ 100K éléments ou avec des opérations coûteuses.
- Mesurez toujours — profilez avec et sans std::execution::par.
Aperçu pratique d'un pool de threads
La norme C++ ne fournit pas de pool de threads (à la date de C++23), mais le principe est simple : un ensemble fixe de threads de travail récupère des tâches dans une file partagée. En voici une ébauche minimale.
#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;
}Pour les algorithmes standard, préférez std::execution::par à un parallélisme fait main — l'implémentation connaît votre matériel. Vérifiez toujours que votre callable est exempt de data races et d'effets de bord. Utilisez std::reduce au lieu de std::accumulate lorsque vous avez besoin de parallélisme. Faites des benchmarks avec des tailles de données réalistes ; pour de petites entrées, la version séquentielle peut être plus rapide. N'oubliez pas que par_unseq interdit d'appeler quoi que ce soit qui acquiert un verrou (y compris l'allocation mémoire sur certaines plateformes).
- Les politiques d'exécution de C++17 (
seq,par,par_unseq) ajoutent du parallélisme aux algorithmes standard avec un minimum de modifications du code std::reduceest le remplaçant destd::accumulateadapté au parallélisme — votre opération doit être associative et commutative- La loi d'Amdahl limite l'accélération : la partie séquentielle de votre code devient le goulot d'étranglement
- Les algorithmes parallèles ont un coût — ils ne sont intéressants que pour des jeux de données suffisamment grands ou un travail coûteux par élément
- Assurez-vous toujours que les callables passés aux algorithmes parallèles sont exempts de data races
- Les pools de threads réutilisent un ensemble fixe de threads pour éviter le coût de création de threads pour de nombreuses petites tâches
Quiz — Testez vos connaissances
(15 XP)1. Pourquoi `std::accumulate` ne peut-il pas être utilisé avec des politiques d'exécution ?
2. Quelle contrainte `std::execution::par_unseq` impose-t-il au callable ?
3. Selon la loi d'Amdahl, quelle est l'accélération maximale si 20 % d'un programme est séquentiel ?