Bref – principes de programmation parallèle

Ce qui suit propose quelques principes de saine programmation parallèle et concurrente. J'y ajouterai ce qui me passe par la tête sur le sujet au fil du temps, alors rien ici n'a la prétention d'être exhaustif.

Localité, foncteurs et cohérence

Premier jet : 29 mai 2012.

Hier, en classe, je discutais d'une technique qui repose a priori sur une connaissance en surface du concept de foncteur, certain d'en avoir déjà parlé (je vieillis!), ce qui n'était pas le cas. Par cette maladresse, je me suis retrouvé en position de montrer en vitesse un concept clé, très utile et qui mérite un traitement à part, mais dans situation où il s'agissait d'une (longue!) parenthèse pour expliquer autre chose. C'est moche et mélangeant.

#include <algorithm>
#include <vector>
#include <iostream>
bool plus_grand_que_5(int n) {
   return n > 5;
}
int main() {
   using namespace std;
   vector<int> v;
   // remplir v... (comme vous le voulez)
   auto pos = find_if(begin(v), end(v), plus_grand_que_5);
   if (pos != end(v))
      cout << "Premier élément de valeur > 5: "
           << *pos << endl;
   else
      cout << "Aucun élément de valeur > 5: " << endl;
}

#include <algorithm>
#include <vector>
#include <iostream>
class PlusGrandQue {
   int seuil;
public:
   PlusGrandQue(int seuil) : seuil{ seuil } {
   }
   bool operator()(int n) const {
      return n > seuil;
   }
};
int main() {
   using namespace std;
   vector<int> v;
   // remplir v... (comme vous le voulez)
   auto pos = find_if(begin(v), end(v), PlusGrandQue{5});
   if (pos != end(v))
      cout << "Premier élément de valeur > 5: "
           << *pos << endl;
   else
      cout << "Aucun élément de valeur > 5: " << endl;
}

#include <algorithm>
#include <vector>
#include <iostream>
int main() {
   using namespace std;
   vector<int> v;
   // remplir v... (comme vous le voulez)
   auto pos = find_if(begin(v), end(v), [](int n) { return n > 5; });
   if (pos != end(v))
      cout << "Premier élément de valeur > 5: "
           << *pos << endl;
   else
      cout << "Aucun élément de valeur > 5: " << endl;
}

Je me permets donc quelques lignes pour exprimer une réflexion sur la localité, le rôle des foncteurs pour en tirer profit au maximum, et la cohérence des systèmes parallèles et concurrents.

Le problème des états globaux et mutables dans les systèmes parallèles et concurrents

Imaginez le pseudocode suivant :

cpt ← 0 // global
fini ← faux // global

f : thread(a_faire : fonction)
   tant que !fini
      a_faire()
      ++cpt

g : fonction nullaire
   // peu importe le traitement, dans la
   // mesure où il se complétera dans un
   // temps fini et où, dans un souci de
   // simplicité, il ne lèvera pas
   // d'exception en cours de route

programme principal
   th0 ← lancer f,g
   th1 ← lancer f,g
   lire une touche
   fini ← vrai
   attendre {th0,th1}
   écrire "Nombre de traitements: ", cpt

J'utilise ici la notation th←lancer fct,par pour indiquer que fct sera exécutée en parallèle et qu'on lui passera les paramètres par. La variable th sera la représentation du thread lancé, sur laquelle nous pourrons ensuite nous mettre en attente..

Maintenant, imaginez qu'on vous demande si le nombre d'appels total à g fait par th0 et th1 correspondra à la fin de l'exécution à la valeur de cpt.

Ici, la réponse est, en général, non (à moins que cpt ne soit un entier atomique).

La raison? Il est possible que th0 et th1 exécutent ++cpt de manière concurrente à l'occasion, une condition de course bien connue, et si cette situation survient ne serait-ce qu'une seule fois, alors la valeur de cpt sera faussée. Ce qui est vilain ici est qu'on pourrait ne vivre cette erreur que lors d'une exécution sur mille, et qu'elle est difficile à dépister pour qui ne comprend pas bien les enjeux – ce qui est le cas de l'immense majorité des programmeuses et des programmeurs.

Le problème ne survient pas pour fini, variable qui n'est modifiée que par un thread – le programme principal – et qui est lue par tous les autres.

Maintenant, examinons cette nouvelle version à peine modifiée du même pseudocode :

fini ← faux // global

f : thread({a_faire : fonction, cpt: ref sur entier})
   tant que !fini
      a_faire()
      ++cpt

g : fonction nullaire
   // peu importe le traitement, dans la
   // mesure où il se complétera dans un
   // temps fini et où, dans un souci de
   // simplicité, il ne lèvera pas
   // d'exception en cours de route

programme principal
   cpt0 ← 0
   cpt1 ← 0
   th0 ← lancer f,{g,cpt0}
   th1 ← lancer f,{g,cpt1}
   lire une touche
   fini ← vrai
   attendre {th0,th1}
   écrire "Nombre de traitements: ", cpt0+cpt1

Ici, j'ai passé au thread un agrégat (un uplet) contenant la fonction que le thread doit appeler à répétition et une référence sur un compteur. Chacun des deux threads incrémente ici parallèlement un compteur distinct de celui de l'autre thread, ce qui élimine tout problème d'incrémentation concurrente. Ce faisant, la valeur affichée en fin de parcours – la somme des deux compteurs – sera exacte.

Visiblement, réduire au strict minimum les accès aux états globaux mutables est un choix gagnant dans un système concurrent ou parallèle. Voilà un constat important.

Des états globaux qui se cachent

Il y a des états globaux et mutables qui se cachent dans notre code sans qu'on n'y pense. Ces états sont souvent des reliquats de la programmation des temps anciens; celle d'il y a plus de vingt ans... et que la majorité des gens pratiquent encore aujourd'hui, par nostalgie peut-être.

Examinez par exemple la fonction std::rand(), de <cstdlib>, dont vous trouverez un exemple d'utilisation dans le programme ci-dessous :

#include <cstdlib>
#include <ctime>
#include <iostream>
#include <algorithm>
int main() {
   using namespace std;
   // initialiser le générateur de nombres pseudo-aléatoires
   srand(static_cast<unsigned int>(time(nullptr)));
   enum { N = 10 };
   int vals[N];
   // remplir vals avec des valeurs pseudo-aléatoires
   generate(begin(vals), end(vals), rand);
   // afficher ces valeurs
   for_each(begin(vals), end(vals), [&](int n) {
      cout << n << ' ';
   });
   cout << endl;
}

Sur le plan technique :

• La fonction srand() initialise le générateur de nombres pseudo-aléatoires de C, qui permet une distribution à peu près uniforme. Si on ne lui fournit pas une valeur initiale « aléatoire », ce générateur démarrera toujours au même point et générera toujours les mêmes valeurs, dans le même ordre, ce qui explique qu'on lui passe typiquement le nombre de secondes depuis l'Epoch (une valeur qui change, manifestement, de seconde en seconde)
• La fonction rand() retourne un entier pseudo-aléatoire entre 0 et RAND_MAX inclusivement
• L'algorithme standard generate(debut,fin,f) applique e = f(); pour chaque élément e dans l'intervalle à demi-ouvert $[debut..fin)$ donc, ici, il remplit le tableau avec des valeurs générées par rand()
• J'ai fait l'affichage avec un for_each() et une λ-expression, mais c'est une manière parmi plusieurs de procéder, sans plus

Ce programme fonctionne très bien, mais comporte un piège pour qui compte s'en inspirer pour fins de « parallélisation ». En effet, pour que la séquence soit pseudo-aléatoire, le générateur de C démarre avec une valeur initiale (le seed, que nous lui fournissons ici avec un appel unique à time(nullptr) en début de parcours), et modifie cette valeur à chaque appel. En termes techniques, rand() se base sur un état global mutable.

Conséquence de ce constat : si deux threads appellent concurremment rand() dans l'exercice de leurs fonctions, la qualité du générateur (déjà pas terrible, mais je vous laisse lire sur le sujet par vous-mêmes si ça vous intéresse) se dégradera – et en pratique, nous avons une vilaine condition de course, qui se cache et n'attend que l'opportunité de nous mordre.

Soyez prévenu(e)s : rand() n'est qu'un exemple parmi plusieurs (on n'a qu'à penser à strtok(), qui permet de découper une chaîne ASCIIZ en jetons grâce à des appels successifs...). De nombreuses fonctions standards de C sont, pour des raisons historiques, Thread-Unsafe, mais il est facile de ne pas y penser et de se faire prendre.

Les foncteurs à la rescousse

Prenons un exemple avec la célèbre fonction strtok(), pour les fins de cette nouvelle illustration. Examinez le programme suivant :

#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
int main() {
   using namespace std;
   string s;
   if (getline(cin, s)) {
      char *p = new char[s.size() + 1];
      copy(begin(s), end(s), p);
      p[s.size()] = 0;
      const char *DELIMS = " \n\t";
      for (auto q = strtok(p, DELIMS); q; q = strtok(nullptr, DELIMS))
         cout << "Mot: " << q << endl;
      delete [] p;
   }
}

Ce petit programme (une dizaine de lignes à peine si on remplace les using, que je mets individuellement, par using namespace std;)...

• Lit une chaîne de caractères d'une longueur arbitrairement longue à l'entrée standard
• Alloue dynamiquement un tableau de char suffisamment grand pour contenir un équivalent ASCIIZ de cette chaîne (tous les caractères en plus d'un délimiteur nul à la fin)
• Copie dans ce tableau les caractères de la chaîne, le tout suivi d'un délimiteur nul par conformité avec les usages de C
• Détermine que nous souhaitons obtenir des séquences ce caractères séparés par des blancs
• Appelle strtok() une première fois avec le tableau de caractères à découper en jetons, ce qui indique à la fonction que c'est cette chaîne qu'il faut retenir, puis rappelle strtok() avec un pointeur nul par la suite, signalant qu'il lui faut maintenant poursuivre avec la chaîne qu'elle connaît déjà. Chaque jeton consommé est affiché sur la sortie standard. Notez que strtok() retourne un pointeur sur le début du prochain jeton, ou un pointeur nul si la séquence source a été épuisée
• Enfin, la mémoire allouée dynamiquement est libérée explicitement

Ce programme fonctionne bien en mode monoprogrammé, puisqu'on évite alors les problèmes de concurrence. Évidemment, si deux threads sollicitent de manière concurrente les services de strtok(), ils pollueront mutuellement l'état global mutable que tient à jour cette fonction, ce qui provoquera de sévères conditions de course. Nous avons ici un cas patent de fonction qui ne peut pas être utilisée dans une situation de concurence. Pourtant, un thread qui découperait des chaînes de caractères en jetons est une application pleinement légitime!

Examinons maintenant comment nous pourrions écrire un foncteur qui réaliserait une tâche semblable à celle que fait strtok(). Pour fins de simplicité, je proposerai un foncteur qui découpera un texte en jetons sur la base des blancs, comme dans l'exemple de strtok() plus haut, mais le choix du délimiteur n'est pas une contrainte technique (la classe std::string offre une vaste gamme de services pour trouver la prochaine occurrence d'un symbole parmi plusieurs dans une chaîne de caractères, si vous souhaitez implémenter une solution plus complète... Amusez-vous!).

Voici donc un nouvel exemple, basé sur un foncteur mais qui réalise le même traitement que l'exemple précédent, qui était basé sur strtok() :

#include <string>
#include <algorithm>
#include <iostream>
#include <sstream>
class tokenizer {
   std::stringstream sstr;
public:
   tokenizer(const std::string &a_decouper) {
      sstr << a_decouper;
   }
   std::string operator()() {
      using std::string;
      if (!sstr) return {}; // épuisé
      string s;
      sstr >> s;
      return s;
   }
};
int main() {
   using namespace std;
   string s;
   if (getline(cin, s)) {
      tokenizer tok{ s };
      for (auto s = tok(); !s.empty(); s = tok())
         cout << "Mot: " << s << endl;
   }
}

Cette version est essentiellement de la même taille que la précédente. Elle est plus simple :

• Pas de gestion manuelle de mémoire (new[], delete[])
• Pas besoin de copier explicitement la chaîne à découper en jetons dans un tableau brut pour fins de manipulations
• Pas de préoccupations quant au passage d'un pointeur non-nul ou nul selon les besoins à la même fonction (car strtok() offre une interface délicate, vous l'aurez remarqué)
• Pas de risque d'oublier un délimiteur quelque part; etc

Nous utilisons un foncteur, instance de tokenizer. Ce foncteur saisit à la construction le texte à découper, puis retourne le prochain jeton à chaque appel de son opérateur () – une chaîne vide signifie alors que le texte à découper a été épuisé. Je doute qu'au sens du code client, l'utilisation de l'objet tok en en tant que fonction semble plus complexe que celle de la fonction strtok().

À l'interne, chaque instance de notre tokenizer conserve un flux en mémoire (en termes C, l'équivalent serait un char* quiqui serait manipulé par sscanf(), mais ne faites pas ça : nous avons de meilleurs outils et de meilleures pratiques maintenant!) duquel il lit les prochains mots, au sens de l'opérateur >> sursur une std::string (donc jusqu'au prochain blanc). Le flux se teste comme un booléen est sera faux seulement s'il est en erreur, ce qui se produira par exemple lorsqu'il sera épuisé.

La beauté des foncteurs est que chacun peut posséder ses propres états. Ce nouvel exemple se parallélise d'ailleurs très bien : pour découper n chaînes de caractères en jetons de manière parallèle, suffit de lancer $n$ threads (ou l'équivalent) et de laisser chacun utiliser sa propre instance de tokenizer. Bingo!

Voilà pourquoi cette technique est très utile...