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.

Cet exemple est directement inspiré d'une présentation de Scott Meyers : https://www.youtube.com/watch?v=WDIkqP4JbkE (les diapositives sont disponibles sur http://www.aristeia.com/TalkNotes/ACCU2011_CPUCaches.pdf si vous êtes intéressé(e)s)

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

Le code implémentant cet exemple suit.

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'000*5'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'000*5'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'000*10'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'000*5'000 éléments est pratiquement résolu de manière instantanée sur une architecture matérielle contemporaine
  • Un std::vector<int> de 10'000*10'000 éléments, avec faux partage
  • Un std::vector<int> de 10'000*10'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'000*10'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'000*5'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), M*N);
   }());
   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, M*N>{});
   }());
   faire_test(test_1{}, 1, "simili_tableau<int>", [] {
      enum { M = 10'000, N = 10'000 };
      return init_source(simili_tableau<int, M*N>{});
   }());
}

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, M*N>{});
   }, test_0{ nthr }, "Test 0, simili_tableau<int>");
   test<NTESTS>([]() {
      enum { M = 10'000, N = 10'000 };
      return init_source(simili_tableau<int, M*N>{});
   }, 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();
}

Discussion

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

Lectures complémentaires

Quelques liens suivent pour enrichir le propos.


Valid XHTML 1.0 Transitional

CSS Valide !