C++17 en détail : algorithmes parallèles

Avec C++11/14, nous avons finalement obtenu la gestion des fils d’exécution dans la bibliothèque standard. Vous pouvez désormais créer un objet std::thread plutôt qu’être tributaires de bibliothèques tierces ou de l’API d’un système. De plus, les traitements asynchrones sont également possibles grâce à future.

Par exemple, en 2014, j’ai écrit au sujet de l’utilisation de tâches asynchrones dans cet article : Tasks with std::future and std::async.

L’utilisation de fils d’exécution multiples est un aspect majeur du C++ moderne. Au sein du comité de standardisation de C++, il existe un groupe « SG1, Concurrence » dédié, chargé d’apporter de nouvelles fonctionnalités au standard.

Qu’y a-t-il en préparation ?

• Coroutines.
• Pointeurs intelligents atomiques.
• Mémoire transactionnelle.
• Barrières.
• Blocs de tâches.
• Parallélisme.
• Calcul.
• Exécuteurs.
• Prise en charge de modèles de programmation hétérogènes.
• Peut-être encore d’autres choses ?

Et pourquoi souhaitons-nous introduire toutes ces fonctionnalités ?

Sean Parent a donné une conférence célèbre à propos d’une concurrence améliorée. Il s’agit d’une intervention dans le cadre de CppNow 2012, et en voici une version récente de 2016, extraite de code::dive 2016.

En utilisant uniquement la version de base de C++ et de la bibliothèque standard, savez-vous quelle proportion de la puissance de calcul d’une machine de bureau typique vous pouvez mettre à profit ? 50 % ? 100 % ? 10 % ?

Dans sa conférence, Sean expliquait que nous pouvions habituellement en utiliser seulement environ 0,25 % avec du code C++ monofil, peut-être quelques pourcents en ajoutant la gestion du multifil de C++11/14.

Alors, où est passé le reste de la puissance de calcul ?

Bien sûr, quelques API tierces vous offrent l’accès à la GPU et à la vectorisation : par exemple, il existe les bibliothèques vectorisées CUDA, OpenCL, OpenGL, etc. Il est même probable que votre compilateur tente de vectoriser automatiquement une partie de votre code. Toutefois, nous aimerions que ce genre de prise en charge provienne directement de la bibliothèque standard. Du code mutualisé pourrait ainsi servir sur plusieurs plateformes.

Avec C++11/14, nous avons de nombreuses fonctionnalités de bas niveau, mais il est toutefois difficile de les utiliser efficacement : il faut développer des abstractions. Idéalement, le code devrait automatiquement être rendu parallèle avec, bien entendu, quelques directives de la part du développeur.

C++17 va un peu plus loin dans ce sens et nous permet d’utiliser plus de puissance de calcul : il déverrouille les fonctionnalités de vectorisation et parallélisation automatiques pour les algorithmes de la bibliothèque standard.

Bien sûr, tout ne peut pas être rendu parallèle : il faut aussi composer avec la loi d’Amdahl. Du coup, toujours utiliser 100 % de la puissance de la machine (ou 110 %, avec le boost de la CPU) n’est qu’une possibilité théorique. Toutefois, mieux vaut s’échiner à cela qu’écrire du code monofil.

Ce billet est le septième de la série au sujet des fonctionnalités de C++17.

Voici ce qui est prévu pour cette série :

1. Correctifs et dépréciation ;
2. Clarification du langage ;
3. Les templates  ;
4. Les attributs ;
5. Simplification ;
6. Modifications de la bibliothèque —Le système de fichiers ;
7. Modifications de la bibliothèque — STL parallélisé (le présent billet) ;
8. Modifications de la bibliothèque—Utilitaires ;
9. Conclusion, bonus — avec un e-book gratuit ! :)

Simple rappel : tout d’abord, si vous voulez vous plonger par vous-mêmes dans le standard, vous pouvez en lire la dernière version ici :

N4659, 2017-03-21, Draft, Standard for Programming Language C++, tiré de isocpp.org.

Vous pouvez également récupérer ma liste de descriptions brèves de chaque fonctionnalité de C++17. C’est une référence qui tient en une page :

Téléchargez un exemplaire gratuit de mon antisèche C++17 !

Liens :

• prise en charge par les compilateurs : C++ compiler support ;
• liste officielle des nouveautés : P0636r0: Changes between C++14 and C++17 DIS ;
• une conférence de Bryce Lelbach : C++Now 2017: C++17 Features ;
• mon billet central sur les fonctionnalités de C++17 : C++17 Features ;
• Jason Turner : C++ Weekly channel, où il a abordé la plupart voire toutes les fonctionnalités de C++17.

Et les livres :

• C++17 STL Cookbook par Jacek Galowicz ;
• Modern C++ Programming Cookbook par Marius Bancila.

À présent, parlons des algorithmes parallélisés !

J’ai déjà évoqué le raisonnement qui justifie que nous désirions tant « d’outils » pour la parallélisation et les calculs, dans la bibliothèque standard.

Voici la spécification technique décrivant ce qui a été intégré au standard : P0024R2.

La nouvelle fonctionnalité semble étonnamment rudimentaire, du point de vue de l’utilisateur. Vous avez simplement un nouveau paramètre qui peut être passé à la plupart des algorithmes standard : ce nouveau paramètre est la politique d’exécution.

std::algorithm_name(policy, /* normal args... */);

J’entrerai dans les détails plus tard, mais l’idée de base est que vous appelez un algorithme et que, après cela, vous spécifiez de quelle manière il peut être exécuté, c’est-à-dire s’il peut être parallélisé, éventuellement vectorisé ou juste sérialisé.

Cette indication est nécessaire, car le compilateur ne peut pas tout déduire du code (pas encore, en tout cas). Seuls nous, en tant qu’auteurs du code, savons s’il y a de quelconques effets de bord, des possibilités de courses critiques, des interblocages, ou même si la parallélisation n’aurait pas de sens (par exemple lorsqu’il s’agit de traiter un petit nombre d’éléments).

V-A. Mise en œuvre actuelle▲

Le paramètre de politique d’exécution indique à l’algorithme comment il devrait s’exécuter. Nous avons les options suivantes :

• sequenced_policy : type de politique d’exécution, utilisé comme un type unique, pour sélectionner une surcharge de l’algorithme parallèle et demander à ce que son exécution ne puisse pas être parallélisée.

  • L’objet global correspondant est std::execution::seq.

• parallel_policy — type de politique d’exécution, utilisé comme un type unique, pour sélectionner une surcharge de l’algorithme parallèle et indiquer que son exécution peut être parallélisée.

  • L’objet global correspondant est std::execution::par.

• parallel_unsequenced_policy — type de politique d’exécution, utilisé comme un type unique, pour sélectionner une surcharge de l’algorithme parallèle et indiquer que son exécution peut être parallélisée et vectorisée.

  • L’objet global correspondant est std::execution::par_unseq.

Notez que ce sont des types uniques, avec les objets globaux correspondants. Il ne s’agit pas d’une simple énumération.

L’exécution séquentielle semble évidente, mais quelle est la différence entre par et par_unseq ?

J’aime bien l’exemple ci-dessous, de la conférence de Bryce Adelstein.

Si nous avons un code tel que celui-ci :

double mul(double x,double y) {
    return x * y;
}
std::transform(
    // séquence d’entrée de « gauche »
    x.begin(), x.end(),
    y.begin(), // séquence d’entrée de « droite »
    z.begin(), // séquence de sortie
    mul);

Les opérations séquentielles qui seront exécutées le seront avec les instructions suivantes :

load x[i]
load y[i]
mul
store into z[i]

Avec la politique d’exécution par, l’intégralité de l’opération mul() pour un élément i donné sera exécutée sur un seul fil, les opérations ne seront pas entrelacées. Un autre i peut toutefois être traité par un fil différent.

Lorsque mul() est en par_unseq, chaque opération peut être traitée par un fil différent, avec une possibilité d’entrelacement. En pratique, cela peut se vectoriser comme suit :

load x[i... i+3]
load y[i...i+3]
mul // quatre éléments à la fois
store into z[i...i+3]

De plus, chacune des invocations ainsi vectorisées pourrait être traitée par un fil distinct.

Avec par_unseq, les invocations de fonctions peuvent être entrelacées. L’utilisation de code vectorisé non protégé n’est donc pas permise : ni mutex, ni allocation de mémoire…
Pour plus de détails là-dessus, consultez cette page : @cppreference.

En outre, la construction actuelle vous permet d’introduire des politiques d’exécution non standard, si bien que des fournisseurs de compilateurs ou de bibliothèques pourraient offrir leurs propres extensions.

Voyons à présent quels algorithmes ont été mis à jour pour prendre en charge le nouveau paramètre de politique d’exécution.

Pour la plupart, les algorithmes de la bibliothèque standard (ceux qui traitent des conteneurs ou des ensembles) savent prendre en charge la politique d’exécution.

Qu’est-ce que cela inclut ?

• adjacent_difference, adjacent_find
• all_of, any_of, none_of
• copy
• count
• equal
• fill
• find
• generate
• includes
• inner_product
• inplace_merge, merge
• is_heap, is_partitioned, is_sorted
• lexicographical_compare
• min_element, minmax_element
• mismatch
• move
• nth_element
• partial_sort, partial_sort_copy
• partition
• remove et ses variantes
• replace et ses variantes
• reverse et rotate
• search
• set_difference, set_intersection, set_union, set_symmetric_difference
• sort
• stable_partition
• swap_ranges
• transform
• unique

La liste complète se trouve ici : @cppreference.

Un exemple simple :

std::vector<int> v = genLargeVector();
// tri séquentiel standard
std::sort(v.begin(), v.end());
// tri séquentiel explicite
std::sort(std::seq, v.begin(), v.end());
// autoriser l’exécution parallélisée
std::sort(std::par, v.begin(), v.end());
// autoriser également la vectorisation
std::sort(std::par_unseq, v.begin(), v.end());

Quelques-uns des algorithmes existants n’ont pas été « apprêtés » pour la parallélisation, mais, au lieu de cela, nous en avons des versions nouvelles et similaires :

• for_each : similaire à std::for_each mais renvoie void ;
• for_each_n : applique un objet-fonction aux n premiers éléments d’une séquence ;
• reduce : similaire à std::accumulate, mais sans ordre d’exécution ;
• exclusive_scan : similaire à std::partial_sum, exclut l’élément d’entrée numéro i de la somme numéro i ;
• inclusive_scan : similaire à std::partial_sum, inclut l’élément numéro i dans la somme numéro i ;
• transform_reduce : applique un pointeur de fonction, puis réduit sans ordre particulier ;
• transform_exclusive_scan : applique un pointeur de fonction, puis calcule un parcours exclusif ;
• transform_inclusive_scan : applique un pointeur de fonction, puis calcule un parcours inclusif ;

Par exemple, nous pouvons utiliser for_each (ou le nouveau for_each_n) avec une politique d’exécution, mais en supposant que nous ne voulons pas utiliser le type de retour du for_each original.

De plus, il y a un cas intéressant avec reduce : ce nouvel algorithme fournit une version parallélisée de accumulate, mais il est important de connaître la différence.

accumulate renvoie la somme de tous les éléments d’un intervalle (ou le résultat d’une opération binaire qui n’est pas forcément une simple somme).

std::vector<int> v{1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int sum = std::accumulate(v.begin(), v.end(), /*valeur initiale*/0);

L’algorithme est uniquement séquentiel ; pour calculer la somme finale, une version parallélisée procèdera comme si elle utilisait un arbre (calculer la somme des sous-intervalles puis fusionner les résultats : « diviser pour mieux régner »). Une telle méthode peut invoquer la somme (ou l’opération binaire) dans un ordre non déterministe. Ainsi, si binary_op n’est ni associative ni commutative, le comportement est également non déterministe.

Par exemple, nous obtiendrons les mêmes résultats pour accumulate et reduce pour un vecteur d’entiers (en calculant une somme), mais nous pourrions observer une légère différence pour un vecteur de float ou double. Ceci est dû au fait que les opérations sur les nombres à virgule flottante ne sont pas associatives.

Est-ce la fin pour aujourd’hui ?

Le multifil, la concurrence et le parallélisme sont des thèmes très vastes à découvrir et à comprendre. J’espère revenir avec quelques exemples supplémentaires (éventuellement avec quelques mises en œuvre valides pour les compilateurs courants !). Pour l’instant, j’ai donc décrit seulement la partie émergée de l’iceberg.

De ce billet, j’aimerais que vous reteniez que la concurrence et le parallélisme constituent un des domaines clefs du standard de C++ et qu’un travail considérable est mené pour proposer des fonctionnalités supplémentaires.

Avec C++17, nous obtenons des algorithmes qui peuvent être exécutés de manière parallèle ou vectorisée. C’est fantastique, car cela constitue une solide couche d’abstraction. Grâce à cela, créer des applications est bien plus aisé. On pouvait peut-être atteindre un résultat similaire avec C++11 ou 14 ou des API tierces, mais tout est désormais inclus dans le standard.

• Utilisez-vous d’autres bibliothèques parallélisées ? CUDA ? SYCL ? TBB, d’Intel ? Autre chose ?
• Essayez-vous de créer du code reposant sur plusieurs threads ou écrivez-vous la majeure partie de votre code pour un seul thread ?

J’ai listé ci-dessous quelques ressources, articles et conférences pour vous fournir plus de renseignements.

Le document officiel de la spécification : P0024R2.

Le document initial de la spécification technique : PDF: A Parallel Algorithms Library | N3554.

Des articles de ModernesCpp sur la version parallélisée de STL :

• C++17: New Parallel Algorithms of the Standard Template Library ;
• Parallel Algorithm of the Standard Template Library - ModernesCpp.com.

Conférence de Bryce Adelstein au sujet des algorithmes parallélisés. Elle contient de nombreux exemples pour les algorithmes « map/reduce » (transformation/réduction) :

https://www.youtube.com/watch?v=Vck6kzWjY88

Puis la conférence de Sean Parent au sujet de la concurrence améliorée en C++ :

https://www.youtube.com/watch?v=QIHy8pXbneI