Faux partage

Le faux partage, ou False Sharing, est un obstacle à l'échelonnabilité résultant du fait que, dans un ordinateur à plusieurs coeurs ou à plusieurs processeurs, il peut arriver que la Cache d'un coeur contienne des données qui peuvent être modifiées par un autre processeur ou par un autre coeur.

Les données sont lues en antémémoire par petits blocs qu'on nomme des Cache Lines; le faux partage résulte d'une modification à une Cache Line forçant sa mise à jour dans les antémémoires d'autres coeurs ou d'autres processeurs, ce qui entraîne un ralentissement inutile et très coûteux.

Pour illustrer la situation, voici un exemple que j'ai construit pour mes étudiant(e)s. L'exemple utilise des mécanismes de C++ 17, mais ces mécanismes ne sont pas nécessaires au propos (ils font simplement du code plus agréable à écrire, à lire, et – dans certains cas – plus rapides à exécuter).

Vue aérienne

Cette illustration fait une tâche simple, soit compter le nombre d'entiers impairs dans un conteneur. J'utilise plusieurs conteneurs, chacun avec ses propres caractéristiques en termes d'accès à la mémoire, mais l'idée générale est la même dans chaque cas.

Cette comptabilité est faite en parallèle, avec un nombre paramétrable de fils d'exécution. Ainsi, il est possible d'examiner les gains – ou pas! – en termes de vitesse d'exécution selon la quantité de parallélisme impliquée.

Enfin, les calculs sont faits à l'aide de deux tests : test_0, dans lequel un faux partage survient, et test_1 qui, à l'aide d'une très légère modification par rapport à test_0, élimine le faux partage et accélère la majorité des cas de tests. La raison pour laquelle certains tests ne sont pas accélérés sera expliquée plus en détail ci-dessous.

Vous trouverez deux blocs de tests : un bloc interactif (que j'utilise en classe, pour prédire les résultats en collaboration avec mes étudiant(e)s) et un bloc non-interactif. Le propos est le même dans les deux cas.

Implémentation

Discussion

Quelques remarques rapides. Présumant que vous ayez mis le code de test à l'épreuve :

Exemple en C#

Un exemple connexe (mais simplifié) en C# peut être exprimé assez simplement aussi. Pour une version avec faux-partage :

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;

public class Program
{
   static (T, long) Tester<T>(Func<T> f)
   {
      var sw = new Stopwatch();
      sw.Start();
      T rés = f();
      sw.Stop();
      return (rés, sw.ElapsedMilliseconds);
   }
   static T Cumuler<T, C>(C coll, Func<T, T, T> cumul, T init) where C : IEnumerable<T>
   {
      foreach (var elem in coll)
         init = cumul(init, elem);
      return init;
   }
   // suppose tab.Length >>> nthrs pour simplicité
   static int CompterImpairs(short[] tab, int nthrs)
   {
      Thread[] th = new Thread[nthrs];
      int[] nbImpairs = new int[nthrs];
      int tailleBloc = tab.Length / nthrs;
      for (int i = 0; i < th.Length - 1; ++i)
      {
         var début = i * tailleBloc;
         var fin = (i + 1) * tailleBloc;
         var indice = i;
         th[i] = new Thread(() =>
         {
            for (int j = début; j != fin; ++j)
               if (tab[j] % 2 != 0)
                  ++nbImpairs[indice];
         });
      }
      // partie résiduelle (des fois, ça n'arrive pas juste)
      th[th.Length - 1] = new Thread(() =>
      {
         for (int j = (th.Length - 1) * tailleBloc;
              j != tab.Length; ++j)
            if (tab[j] % 2 != 0)
               ++nbImpairs[th.Length - 1];
      });
      foreach (var thr in th) thr.Start();
      foreach (var thr in th) thr.Join();
      return Cumuler(nbImpairs, (x, y) => x + y, 0);
   }
   static short[] CréerTableau(int taille)
   {
      short[] tab = new short[taille];
      for (int i = 0; i != tab.Length; ++i)
         tab[i] = (short)(i * 2 + 1); // des impairs
      return tab;
   }
   public static void Main()
   {
      const int NB_THR_MAX = 10;
      var tab = CréerTableau(25_000 * 25_000);
      Console.WriteLine("Version avec faux-partage...");
      for (int i = 1; i <= NB_THR_MAX; ++i)
      {
         var (rés, dt) = Tester(() => CompterImpairs(tab, i));
         Console.WriteLine($"\tNb fils : {i} ; {rés} impairs en {dt} ms");
      }
   }
}

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Threading;

public class Program
{
   static (T, long) Tester<T>(Func<T> f)
   {
      var sw = new Stopwatch();
      sw.Start();
      T rés = f();
      sw.Stop();
      return (rés, sw.ElapsedMilliseconds);
   }
   static T Cumuler<T, C>(C coll, Func<T, T, T> cumul, T init) where C : IEnumerable<T>
   {
      foreach (var elem in coll)
         init = cumul(init, elem);
      return init;
   }
   // suppose tab.Length >>> nthrs pour simplicité
   static int CompterImpairs(short[] tab, int nthrs)
   {
      Thread[] th = new Thread[nthrs];
      int[] nbImpairs = new int[nthrs];
      int tailleBloc = tab.Length / nthrs;
      for (int i = 0; i < th.Length - 1; ++i)
      {
         var début = i * tailleBloc;
         var fin = (i + 1) * tailleBloc;
         var indice = i;
         th[i] = new Thread(() =>
         {
            int n = 0;
            for (int j = début; j != fin; ++j)
               if (tab[j] % 2 != 0)
                  ++n;
            nbImpairs[indice] = n;
         });
      }
      // partie résiduelle (des fois, ça n'arrive pas juste)
      th[th.Length - 1] = new Thread(() =>
      {
         int n = 0;
         for (int j = (th.Length - 1) * tailleBloc;
              j != tab.Length; ++j)
            if (tab[j] % 2 != 0)
               ++n;
         nbImpairs[th.Length - 1] = n;
      });
      foreach (var thr in th) thr.Start();
      foreach (var thr in th) thr.Join();
      return Cumuler(nbImpairs, (x, y) => x + y, 0);
   }
   static short[] CréerTableau(int taille)
   {
      short[] tab = new short[taille];
      for (int i = 0; i != tab.Length; ++i)
         tab[i] = (short)(i * 2 + 1); // des impairs
      return tab;
   }
   public static void Main()
   {
      const int NB_THR_MAX = 10;
      var tab = CréerTableau(25_000 * 25_000);
      Console.WriteLine("Version sans faux-partage...");
      for (int i = 1; i <= NB_THR_MAX; ++i)
      {
         var (rés, dt) = Tester(() => CompterImpairs(tab, i));
         Console.WriteLine($"\tNb fils : {i} ; {rés} impairs en {dt} ms");
      }
   }
}

L'exemple reposera strictement sur des outils standards. J'ai utilisé des using namespace globaux au fichier alléger l'écriture, même si ce n'est pas exactement la pratique la plus élégante qui soit.	`#include <iostream> #include <memory> #include <chrono> #include <thread> #include <vector> #include <deque> #include <list> #include <algorithm> #include <numeric> #include <string> using namespace std; using namespace std::chrono;`
Pour éviter les critiques de gens qui pensent que les conteneurs standards sont lents (soupir!), j'ai codé un petit « conteneur » qui ne fait absolument rien d'autre qu'entreposer un tableau allouée dynamiquement (mais sans capacité de redimensionnement) et d'en gérer automatiquement la mémoire. Cette classe, nommée simili_tableau<T,N>, sera comparée aux conteneurs standards utilisés lors des tests, un peu plus bas.	`template <class T, int N> struct simili_tableau { unique_ptr<T[]> p; simili_tableau() : p{ new T[N] } { } simili_tableau(simili_tableau&&) = default; simili_tableau& operator=(simili_tableau&&) = default; T* begin() { return &p[0]; } T* end() { return begin() + size(); } const T* begin() const { return &p[0]; } const T* end() const { return begin() + size(); } size_t size() const { return N; } T& operator[](int n) { return p[n]; } const T& operator[](int n) const { return p[n]; } };`
Pour alléger le code de nos tests, j'ai écrit des fonctions pour construire et initialiser les conteneurs qui seront testés : La fonction creer_reserver(obj,n) servira pour les conteneurs qui supportent l'allocation en bloc de la mémoire destinée à entreposer leurs objets – dans notre cas, elle servira à construire des vector<T> avec une capacité suffisante pour entreposer n instances de T La fonction init_source(src,n) qui insèrera les n premiers entiers impairs dans src, et La fonction init_source(src) pour le cas où src est un simili_tableau<T,N> car ce « conteneur » ne supporte pas l'opération push_back() Note que, bien que j'aie pris soin d'intialiser efficacement les conteneurs, le temps d'initialisation ne sera pas comptabilisé par les tests qui suivent.	`template <class T> auto creer_reserver(T obj, int n) { obj.reserve(n); return obj; } template <class T> auto init_source(T src, int n) { for (int i = 0; i != n; ++i) src.push_back(2 * i + 1); return src; } template <class T, int N> auto init_source(simili_tableau<T,N> src) { for (int i = 0; i != N; ++i) src[i] = 2 * i + 1; return src; }`
Le test nommé test_0 est modélisé par un foncteur applicable à un conteneur de type C non-modifiable nommé vals, et a pour rôle de compter les entiers impairs dans vals à l'aide de n fils d'exécution. La valeur de n est paramétrable à la construction du test_0, mais correspond par défaut au nombre estimé de coeurs à notre disposition, tel que retourné par thread::hardware_concurrency(). La stratégie générale est de lancer n-1 fils d'exécution concurrents, chacun opérant sur environ vals.size()/n éléments. Les vals.size()/n éléments résiduels sont traités par le fil d'exécution initial. Un vector<int> nommé impairs permet à chaque fil d'exécution i d'entreposer dans impairs[i] le nombre d'impairs qu'il aura calculé Le faux partage tient au fait que, bien qu'aucune condition de course ne survienne dans ce programme, les différents éléments du vecteur impairs se trouvent placés de manière contiguë en mémoire, et partagent donc leurs Cache Lines. Conséquemment, chaque écriture dans impairs[i] risque de forcer un rafraîchissement de la Cache Line d'autres fils d'exécution (tout particulièrement le fil i-1 et le fil i+1 si ceux-ci existent), ce qui entraîne de multiples interférences entre fils d'exécution et ralentit celle-ci de manière difficile à prévoir a priori.	struct test_0 { unsigned int n = thread::hardware_concurrency(); test_0() = default; test_0(unsigned int n) : n{ n } { } template <class C> int operator()(const C &vals) { vector<size_t> impairs(n); vector<thread> v; auto stride = vals.size() / n; auto p = begin(vals); for (decltype(n) i = 0; i < n - 1; ++i) { v.emplace_back(thread{ [i, beg = p, end = next(p, stride), &impairs]() { for (auto it = beg; it != end; ++it) if (it % 2 != 0) ++impairs[i]; // <-- ICI } }); advance(p, stride); } for (; p != end(vals); ++p) if (p % 2 != 0) ++impairs[n - 1]; // <-- ICI for (auto &th : v) th.join(); return accumulate(begin(impairs), end(impairs), 0); } };
La résolution du faux partage dans test_1 tient au recours à une variable locale, nimpairs, sur laquelle la comptabilité est faite tout au long du test, pour ne mener qu'à une seule écriture dans impairs[i] à la toute fin. Ce petit changement, à lui seul, entraîne des gains de vitesse et de prévisibilité significatifs. Pour le reste, test_1 est identique à test_0.	// // // struct test_1 { unsigned int n = thread::hardware_concurrency(); test_1() = default; test_1(unsigned int n) : n{ n } { } template <class C> int operator()(const C &vals) { vector<size_t> impairs(n); vector<thread> v; auto stride = vals.size() / n; auto p = begin(vals); for (decltype(n) i = 0; i < n - 1; ++i) { v.emplace_back(thread{ [i, beg = p, end = next(p, stride), &impairs]() { int nimpairs = 0; for (auto it = beg; it != end; ++it) if (it % 2 != 0) ++nimpairs; // <-- ICI impairs[i] = nimpairs; // <-- ICI } }); advance(p, stride); } int nimpairs = 0; for (; p != end(vals); ++p) if (p % 2 != 0) ++nimpairs; // <-- ICI impairs[n - 1] = nimpairs; // <-- ICI for (auto &th : v) th.join(); return accumulate(begin(impairs), end(impairs), 0); } };
Le code utilisé pour tester le temps d'exécution des tests qui suivent tient à la fonction tester() proposé à droite. Vous trouverez plus d'informations à son sujet dans ../AuSecours/Mesurer-le-temps.html, mais l'idée est de saisir le temps avant et après exécution de f(args), et de retourner une paire comprenant le résultat de f(args) et le temps écoulé.	`template <class F, class ... Args> auto tester(F f, Args && ...args) { auto avant = high_resolution_clock::now(); auto n = f(std::forward<Args>(args)...); auto apres = high_resolution_clock::now(); return make_pair(n, apres - avant); }`
La fonction attendre() est ... triviale. Elle sert dans les tests interactifs pour bloquer l'exécution avant de procéder à un test, tout simplement.	`void attendre() { cout << "..."; string s; getline(cin, s); }`
La fonction tests_interactifs() réalise une série de tests, avec ou sans faux partage, et avec divers conteneurs de diverses tailles, attendant avant chaque test que l'usager soit prêt (ce qui est utile en pour les démonstrations en classe). Les tests réalisés le sont sur : Une std::list<int> de 5'0005'000 éléments, avec faux partage. Pour une std::list<int>, il est difficile de faire des tests sur un plus grand nombre d'éléments car chaque noeud de la liste occupe un surcroît d'espace en mémoire pour entreposer les pointeur sur les noeuds prédécesseur et successeur Un std::deque<int> de 5'0005'000 éléments, avec faux partage. Ceci permet un comparatif de vitesse avec une std::list<int> ayant le même nombre d'éléments Un std::deque<int> de 10'00010'000 éléments, avec faux partage. Ceci se rapproche de ce qu'on peut demander à un std::vector<int> pour qui un test sur 5'0005'000 éléments est pratiquement résolu de manière instantanée sur une architecture matérielle contemporaine Un std::vector<int> de 10'00010'000 éléments, avec faux partage Un std::vector<int> de 10'00010'000 éléments, sans faux partage. Ceci devrait permettre de constater l'impact du faux partage (en comparaison avec le test précédent) Un std::deque<int> de 10'00010'000 éléments, sans faux partage. Ceci est instructif, à la fois pour l'impact du faux partage (en comparaison avec un test antérieur) et pour l'impact de choisir un std::deque<T> plutôt qu'un std::vector<T> Une std::list<int> de 5'0005'000 éléments, sans faux partage. Vous remarquerez probablement, si vous réalisez les tests vous-même, que l'impact du faux partage (présence ou absence) ne se fera pas vraiment sentir ici, chaque accès à un noeud provoquant un Cache Miss de toute manière Enfin, simili_tableau<int,10'000*10'000> avec faux partage, puis sans faux partage. Ceci montre à nouveau l'impact du faux partage... et fait apprécier l'efficacité redoutable d'un std::vector<T> J'ai utilisé des IIFE dans ces tests. Voir ../Divers--cplusplus/Lambda-expressions.html pour plus de détails.	void tests_interactifs() { auto faire_test = [](auto tst, int no, const char nom, auto vals) { cout << "Test " << no << ", " << nom << "\n\ttaille " << vals.size(); attendre(); auto[n, dt] = tester(tst, vals); cout << "\n\t" << n << " impairs trouves en " << duration_cast<milliseconds>(dt).count() << " ms\n" << endl; }; faire_test(test_0{}, 0, "list<int>", [M = 5'000, N = 5'000] { return init_source(list<int>{}, M N); }()); faire_test(test_0{}, 0, "deque<int>", [M = 5'000, N = 5'000] { return init_source(deque<int>{}, M * N); }()); faire_test(test_0{}, 0, "deque<int>", [M = 10'000, N = 10'000] { return init_source(deque<int>{}, M * N); }()); faire_test(test_0{}, 0, "vector<int>", [M = 10'000, N = 10'000] { return init_source(creer_reserver(vector<int>{}, M * N), MN); }()); faire_test(test_1{}, 1, "vector<int>", [M = 10'000, N = 10'000] { return init_source(creer_reserver(vector<int>{}, M N), M * N); }()); faire_test(test_1{}, 1, "deque<int>", [M = 10'000, N = 10'000] { return init_source(deque<int>{}, M * N); }()); faire_test(test_1{}, 1, "list<int>", [M = 5'000, N = 5'000] { return init_source(list<int>{}, M * N); }()); faire_test(test_0{}, 0, "simili_tableau<int>", [] { enum { M = 10'000, N = 10'000 }; return init_source(simili_tableau<int, MN>{}); }()); faire_test(test_1{}, 1, "simili_tableau<int>", [] { enum { M = 10'000, N = 10'000 }; return init_source(simili_tableau<int, MN>{}); }()); }
Pour les tests non-manuels, j'utilise une fonction test<NTESTS>(cr,te,nom) qui encapsule l'accumulation de NTESTS tests te sur les données générées par cr, et utilise nom pour fins d'affichage.	`template <int NTESTS, class CR, class TE> void test(CR cr, TE te, const string &nom) { auto vals = cr(); clog << nom << "\n\ttaille " << vals.size(); high_resolution_clock::duration temps_total = {}; for (int i = 0; i < NTESTS; ++i) { auto res = tester(te, vals); temps_total += res.second; } clog << "\n\tTemps moyen sur " << NTESTS << " tests : " << duration_cast<milliseconds>(temps_total).count() / static_cast<double>(NTESTS) << " ms\n" << endl; }`
Les tests non-interactifs font, en quelque sorte, la même chose que les tests interactifs, mais à l'aide de nthr fils d'exécution. En pratique, nthr variera de 1 à thread::hardware_concurrency() (voir plus bas). Chaque test sera fait NTESTS fois.	void tests_blocs(unsigned int nthr) { enum { NTESTS = 10 }; test<NTESTS>([M = 5'000, N = 5'000]() { return init_source(list<int>{}, M * N); }, test_0{ nthr }, "Test 0, list<int>"); test<NTESTS>([M = 5'000, N = 5'000]() { return init_source(deque<int>{}, M * N); }, test_0{ nthr }, "Test 0, deque<int>"); test<NTESTS>([M = 10'000, N = 10'000]() { return init_source(deque<int>{}, M * N); }, test_0{ nthr }, "Test 0, deque<int>"); test<NTESTS>([M = 10'000, N = 10'000]() { return init_source(creer_reserver(vector<int>{}, M * N), M * N); }, test_0{ nthr }, "Test 0, vector<int>"); test<NTESTS>([M = 10'000, N = 10'000]() { return init_source(creer_reserver(vector<int>{}, M * N), M * N); }, test_1{ nthr }, "Test 1, vector<int>"); test<NTESTS>([M = 10'000, N = 10'000]() { return init_source(deque<int>{}, M * N); }, test_1{ nthr }, "Test 1, deque<int>"); test<NTESTS>([M = 5'000, N = 5'000]() { return init_source(list<int>{}, M * N); }, test_1{ nthr }, "Test 1, list<int>"); test<NTESTS>([]() { enum { M = 10'000, N = 10'000 }; return init_source(simili_tableau<int, MN>{}); }, test_0{ nthr }, "Test 0, simili_tableau<int>"); test<NTESTS>([]() { enum { M = 10'000, N = 10'000 }; return init_source(simili_tableau<int, MN>{}); }, test_1{ nthr }, "Test 1, simili_tableau<int>"); }
La fonction tests_blocs() appelle tests_blocs(i) pour un nombre i de fils d'exécution variable.	`// // // void tests_blocs() { auto hwc = thread::hardware_concurrency(); auto n = hwc * 2; for (decltype(hwc) i = 1; i <= n; ++i) { clog << "\n*** Avec " << i << " thread(s) (h/w concurrency: " << hwc << ") ***\n"; tests_blocs(i); } }`
Enfin, main() fait à la fois les tests interactifs et les tests non-interactifs.	`int main() { cout << string(75, '-') << "\nTests interactifs\n" << string(75, '-') << endl; tests_interactifs(); cout << string(75, '-') << "\nTests en bloc\n" << string(75, '-') << endl; tests_blocs(); }`

Faux partage

Vue aérienne

Implémentation

Discussion

Exemple en C#

Lectures complémentaires