Université de Sherbrooke, développement du jeu vidéo, CSP

Vous trouverez ici quelques documents et quelques liens pouvant, je l'espère, vous être utiles.

Les documents qui vous sont fournis ici le sont pour vous rendre service.

Je travaille très fort sur chacun de mes cours. Veuillez ne pas vendre (ou donner) les documents que je vous offre ici à qui que ce soit sans mon consentement. Si des abus surviennent, je vais cesser de rendre ce matériel disponible à toutes et à tous.

Si ces documents vous rendent service, faites-le moi savoir. Mon adresse de courriel est disponible à travers la page où on trouve mon horaire.

Vous trouverez sur ce site :

Documents sous forme électronique

Cliquez sur cette cible pour le plan de cours, sous forme électronique.

Contenu des séances

Ce qui suit détaille le contenu des séances du cours INF709.

Index des séances théoriques
S00 S01 S02 S03 S04 S05 S06 S07 S08 S09
Séance Contenu

S00 – mercredi 18 janvier 9 h-12 h

Au menu :

Ce cours abordera en priorité l'API pleinement portable de threading et de synchronisation que propose le langage C++ depuis C++ 11, incluant certains de ses raffinements plus récents.

Notez que nous adapterons le plan de match habituel au fait que nous avons, à la demande de la classe, fait un survol rapide de ces questions à la session précédente. Ainsi, nous procéderons par exercices plutôt que par des démonstrations au cours de cette séance.

Étape 0 : écrivons un programme qui (a) lit le contenu d'un fichier texte contenant du code source C++ (vous n'avez pas à le valider), (b) remplace certains caractères (plus précisément : &, < et >) par des métacaractères HTML (respectivement : &amp;, &lt; et &gt;), (c) colorie les mots clés C++ (on procédera de manière naïve ici) en utilisant des balises <span>, et (d) produit en sortie un fichier portant le même nom que le fichier d'origine mais avec extension .html (donc z.cpp en entrée donnera z.cpp.html en sortie). Le fichier en sortie doit représenter une version correctement indentée du fichier en entrée (nous utiliserons des balises <pre>).

Après cette étape, nous avons :

#include <iostream>
/* if */
#include <string>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <utility>
#include <cctype>
using namespace std;

string lire_fichier(const string &nom) {
   ifstream in{ nom };
   return { istreambuf_iterator<char>{ in }, istreambuf_iterator<char>{} };
}

// & --> &amp;
// < --> &lt;
// > --> &gt;

string remplacer_metacaracteres(const string &source) {
   static const pair<char, string> rempl[]{
      { '&', "&amp;"s },
      { '<', "&lt;"s },
      { '>', "&gt;"s }
   };
   string dest;
   for (char c : source) {
      if (auto pos = find_if(begin(rempl), end(rempl), [c](auto &&p) {
         return p.first == c;
      }); pos != end(rempl)) {
         dest += pos->second;
      } else {
         dest += c;
      }
   }
   return dest;
}

bool peut_debuter_identifiant(char c) {
   return isalpha(c) || c == '_';
}
bool peut_poursuivre_identifiant(char c) {
   return isalnum(c) || c == '_';
}

string COLORIER(string s) {
   return R"(<span style="color:fuchsia">)"s + s + "</span>"s;
}

string colorier_mots_cles(const string &source) {
   static const string mots[]{
      "const"s, "if"s, "for"s, "return"s, "void"s
   };
   bool est_identifiant = false;
   string dest;
   string id;
   for (auto c : source) {
      if (!est_identifiant && peut_debuter_identifiant(c)) {
         est_identifiant = true;
         id += c;
      } else if (est_identifiant) {
         if (peut_poursuivre_identifiant(c)) {
            id += c;
         } else {
            est_identifiant = false;
            if (find(begin(mots), end(mots), id) != end(mots))
               dest += COLORIER(id);
            else
               dest += id;
            dest += c;
            id = {};
         }
      } else {
         dest += c;
      }
   }
   // si id n'est pas vide, un petit effort encore (voir 60-63...)
   return dest;
}

void ecrire_fichier(const string &nom, const string &texte) {
   ofstream out{ nom };
   out << R"(<html>
  <head>
  </head>
  <body>
    <pre>)"
      << texte
      << R"(</pre>
  </body>
</html>)";
}

int main() {
   string s = lire_fichier("z.cpp");
   s = remplacer_metacaracteres(s);
   s = colorier_mots_cles(s);
   ecrire_fichier("z.cpp.html", s);
}

Étape 1 : transformons ce programme en un programme qui réalise ces transformations sur plusieurs fichiers, séquentiellement. Nous utiliserons pour ce faire un main() acceptant des paramètres.

Étape 2 : transformons ce programme en un pipeline tel que les étapes de traitement sont faites en parallèle : pendant qu'un fil d'exécution lit le fichier , un autre fait le remplacement des métacaractères sur le fichier , un autre fait la coloration sur le fichier et un autre encore fait l'écriture sur disque du fichier .

Après cette étape, nous avons :

#include <iostream>
/* if */
#include <string>
#include <fstream>
#include <algorithm>
#include <iterator>
#include <utility>
#include <cctype>
#include <vector>
#include <mutex>
#include <thread>
#include <atomic>
using namespace std;


template <class T>
   class zone_transit {
      vector<T> data;
      mutex m;
   public:
      void ajouter(const T &val) { // bof
         lock_guard _{ m };
         data.push_back(val);
      }
      template <class It>
         void ajouter(It debut, It fin) {
            lock_guard _{ m };
            for_each(debut, fin, [&](auto &&val) {
               data.push_back(val);
            });
         }
      vector<T> extraire() {
         lock_guard _{ m };
         vector<T> temp = std::move(data);
         data.clear();
         return temp;
      }
   };




string lire_fichier(const string &nom) {
   ifstream in{ nom };
   return { istreambuf_iterator<char>{ in }, istreambuf_iterator<char>{} };
}

// & --> &amp;
// < --> &lt;
// > --> &gt;

string remplacer_metacaracteres(const string &source) {
   static const pair<char, string> rempl[]{
      { '&', "&amp;"s },
      { '<', "&lt;"s },
      { '>', "&gt;"s }
   };
   string dest;
   for (char c : source) {
      if (auto pos = find_if(begin(rempl), end(rempl), [c](auto &&p) {
         return p.first == c;
      }); pos != end(rempl)) {
         dest += pos->second;
      } else {
         dest += c;
      }
   }
   return dest;
}

bool peut_debuter_identifiant(char c) {
   return isalpha(c) || c == '_';
}
bool peut_poursuivre_identifiant(char c) {
   return isalnum(c) || c == '_';
}

string COLORIER(string s) {
   return R"(<span style="color:fuchsia">)"s + s + "</span>"s;
}

string colorier_mots_cles(const string &source) {
   static const string mots[]{
      "const"s, "if"s, "for"s, "return"s, "void"s
   };
   bool est_identifiant = false;
   string dest;
   string id;
   for (auto c : source) {
      if (!est_identifiant && peut_debuter_identifiant(c)) {
         est_identifiant = true;
         id += c;
      } else if (est_identifiant) {
         if (peut_poursuivre_identifiant(c)) {
            id += c;
         } else {
            est_identifiant = false;
            if (find(begin(mots), end(mots), id) != end(mots))
               dest += COLORIER(id);
            else
               dest += id;
            dest += c;
            id = {};
         }
      } else {
         dest += c;
      }
   }
   // si id n'est pas vide, un petit effort encore (voir 60-63...)
   return dest;
}

void ecrire_fichier(const string &nom, const string &texte) {
   ofstream out{ nom };
   out << R"(<html>
  <head>
  </head>
  <body>
    <pre>)"
      << texte
      << R"(</pre>
  </body>
</html>)";
}

struct donnees {
   string nom_fichier;
   string texte;
};

int main(int argc, char *argv[]) {
   enum { NETAPES = 4 };
   zone_transit<donnees> zt[NETAPES - 1];
   atomic<bool> fini[NETAPES - 1]{}; // false
   thread etapes[NETAPES]{
      // lecteur
      thread { [&] {
         for (int i = 1; i < argc; ++i) {
            string nom = argv[i];
            string s = lire_fichier(nom);
            zt[0].ajouter({ nom, s });
         }
         fini[0] = true;
      } },
      // remplaceur
      thread { [&] {
         while (!fini[0]) {
            auto data = zt[0].extraire();
            for (auto &&[nom, texte] : data) {
               zt[1].ajouter({ nom, remplacer_metacaracteres(texte) });
            }
         }
         auto data = zt[0].extraire();
         for (auto &&[nom, texte] : data) {
            zt[1].ajouter({ nom, remplacer_metacaracteres(texte) });
         }
         fini[1] = true;
      } },
      // colorieur
      thread { [&] {
         while (!fini[1]) {
            auto data = zt[1].extraire();
            for (auto &&[nom, texte] : data) {
               zt[2].ajouter({ nom, colorier_mots_cles(texte) });
            }
         }
         auto data = zt[1].extraire();
         for (auto &&[nom, texte] : data) {
            zt[2].ajouter({ nom, colorier_mots_cles(texte) });
         }
         fini[2] = true;
      } },
      // scripteur
      thread { [&] {
         while (!fini[2]) {
            auto data = zt[2].extraire();
            for (auto &&[nom, texte] : data) {
               ecrire_fichier(nom + ".html"s, texte);
            }
         }
         auto data = zt[2].extraire();
         for (auto &&[nom, texte] : data) {
            ecrire_fichier(nom + ".html"s, texte);
         }
      } }
   };

   for (auto &th : etapes)
      th.join();
   //for (int i = 1; i < argc; ++i) {
   //   string nom = argv[i];
   //   string s = lire_fichier(nom);
   //   s = remplacer_metacaracteres(s);
   //   s = colorier_mots_cles(s);
   //   ecrire_fichier(nom + ".html"s, s);
   //}
}

Toutefois, parce qu'il est possible (pour ne pas dire probable) que cette API ne soit pas disponible (ou pas entièrement disponible) sur certaines des plateformes que vous rencontrerez dans l'industrie, du moins à court terme. Ainsi, ne vous en faites pas : en examinant des manières de procéder sans cette API, nous ne perdons pas notre temps. Cela vous montrera au passage comment en implémenter les bases vous-mêmes si vous le souhaitez.

Quelques exemples sur des enjeux de synchronisation, utilisant :

Un peu de poésie :

Voici un petit exemple d'implémentation réduite de std::async() à titre illustratif, acceptant une fonction int(*)(int) et un paramètre int puis retournant une future<int>.

Voici une version un peu plus complète (je n'ai pas tenu compte des politiques de démarrage comme std::launch::async et std::launch::defer) :

template <class T, class F, class ... Args>
   auto async(F f, Args && ... args) {
      promise<T> ze_promesse;
      future<T> ze_future = ze_promesse.get_future();
      thread th{ [](promise<T>&& p, F f, Args && ... args) {
         try {
            p.set_value(f(std::forward<Args>(args)...));
         } catch (...) {
            p.set_exception(current_exception());
         }
      }, std::move(ze_promesse), f, std::forward<Args>(args)... };
      th.detach();
      return ze_future;
   }

Ceci ne signifie (vraiment!) pas que votre implémentation soit écrite exactement comme ceci, mais c'est l'idée.

Quelques exemples :

  • Synchroniser de manière extrinsèque une opération composite (illustré par la projection à la console de messages cohérents)
  • Subtilités quant à la capture par référence ou par copie d'objets utilisés concurremment par plusieurs fils d'exécution
  • Synchroniser le démarrage de l'exécution de multiples fils d'exécution concurrents

S01 – vendredi 20 janvier 9 h-12 h

Nous poursuivons notre survol des enjeux associés à la programmation parallèle et concurrente, de même qu'aux outils mis à notre disposition pour les confronter :

Que faire si on n'a pas les outils de C++ 11 (ou plus récent)?

Quelques considérations de plus haut niveau :

À titre d'exemple, dans ce qui suit, une instance de Proches doit tenir sur une seule et même Cache Line, alors que dans une instance de Loins, il importe que a et b soient sur des Cache Lines distinctes :

#include <new>
struct Proches {
   int a = 0;
   // ... trucs ici, ou pas ...
   int b = 0;
};
// on exige ce qui suit si on veut qu'un Proches tienne sur une Cache Line
static_assert(sizeof(Proches) <= std::hardware_constructive_interference_size);

struct Loins {
   alignas(std::hardware_destructive_interference_size) int a = 0;
   // ... trucs ici, ou pas ...
   alignas(std::hardware_destructive_interference_size) int b = 0;
};
  • Objets volatiles (attention, sujet « volatile », justement!), si le temps le permet
  • Objets autonomes (histoire avec un revirement surprise!)

J'ai fait une démonstration des coûts du faux-partage (attention : compilez en 64 bits dû à la taille du vecteur). Le code suit :

#include <mutex>
#include <thread>
#include <vector>
#include <iostream>
#include <chrono>
#include <locale>
#include <future>
#include <random>
#include <algorithm>
#include <numeric>
using namespace std;
using namespace std::chrono;

template <class F, class ... Args>
auto test(F f, Args &&... args) {
   auto pre = high_resolution_clock::now();
   auto res = f(std::forward<Args>(args)...);
   auto post = high_resolution_clock::now();
   return pair{ res, post - pre };
}

int main() {
   locale::global(locale{ "" });
   enum { N = 25'000 };
   vector<int> mat(N * N);
   auto taille_bloc = mat.size() / thread::hardware_concurrency();
   iota(begin(mat), end(mat), 1); // approx. la moitié est impaire
   auto [r0, dt0] = test([&] {
      vector<size_t> nimpairs(thread::hardware_concurrency()); // initialisés à zéro
      vector<thread> th;
      for (vector<size_t>::size_type i = 0; i != nimpairs.size(); ++i)
         th.emplace_back([&, i, taille_bloc] {
         for (auto j = i * taille_bloc; j != (i + 1) * taille_bloc; ++j)
            if (mat[j] % 2 != 0)
               nimpairs[i]++;
      });
      for (auto & thr : th) thr.join();
      return accumulate(begin(nimpairs), end(nimpairs), 0);
   });
   cout << "Par. Nb impairs au total : " << r0 << " obtenu en "
        << duration_cast<milliseconds>(dt0).count() << " ms." << endl;
   auto [r1, dt1]  = test([&] {
      size_t nimpairs = 0;
      for (vector<size_t>::size_type j = 0; j != mat.size(); ++j)
         if (mat[j] % 2 != 0)
            nimpairs++;
      return nimpairs;
   });
   cout << "Seq. Nb impairs au total : " << r1 << " obtenu en "
        << duration_cast<milliseconds>(dt1).count() << " ms." << endl;
   auto [r2, dt2] = test([&] {
      vector<size_t> nimpairs(thread::hardware_concurrency()); // initialisés à zéro
      vector<thread> th;
      for (vector<size_t>::size_type i = 0; i != nimpairs.size(); ++i)
         th.emplace_back([&, i, taille_bloc] {
            size_t n = 0;
            for (auto j = i * taille_bloc; j != (i + 1) * taille_bloc; ++j)
               if (mat[j] % 2 != 0)
                  n++;
            nimpairs[i] = n;
         });
      for (auto & thr : th) thr.join();
      return accumulate(begin(nimpairs), end(nimpairs), 0);
   });
   cout << "Par. Nb impairs au total : " << r2 << " obtenu en "
        << duration_cast<milliseconds>(dt2).count() << " ms." << endl;
}

Dans les notes de cours :

S02 – vendredi 27 janvier 9 h-12 h

Au menu :

  • Q00
  • Exemple « fait main » de faux-partage :
#include <thread>
#include <vector>
#include <chrono>
#include <utility>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <numeric>
using namespace std;
using namespace std::chrono;

template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

template <class Pred>
   unsigned long compter_si_seq(const vector<int> &v, Pred pred) {
      return count_if(begin(v), end(v), pred);
   }

template <class Pred>
unsigned long compter_si_par(int nthr, const vector<int> &v, Pred pred) {
   vector<thread> th;
   vector<unsigned long> cumul(nthr);
   const size_t block_size = size(v) / nthr;
   for (int i = 0; i < nthr - 1; ++i) {
      th.emplace_back(thread{ [pred, &cumul, i,
                               b = next(begin(v), i * block_size),
                               e = next(begin(v), (i + 1) * block_size)]() mutable {
         unsigned long somme = 0;
         for (; b != e; ++b)
            if (pred(*b))
               somme++; // cumul[i]++ pour avoir du faux-partage
         cumul[i] = somme;
      } });
   }
   auto b = next(begin(v), (nthr - 1) * block_size),
        e = end(v);
   unsigned long somme = 0;
   for (; b != e; ++b)
      if (pred(*b))
         somme++; // cumul[nthr-1]++ pour avoir du faux-partage
   cumul[nthr - 1] = somme;
   for(auto & thr : th) thr.join();
   return accumulate(begin(cumul), end(cumul), 0UL);
}

int main() {
   enum { N = 100'000'000 };
   vector<int> v(N);
   generate(begin(v), end(v), [n = -1]() mutable { return n += 2; });
   auto est_impair = [](int n) { return n % 2 != 0; };
   auto [r0, dt0] = test([&] { return compter_si_seq(v, est_impair); });
   cout << "Sequentiel :\n\t" << r0 << " impairs en "
        << duration_cast<microseconds>(dt0) << '\n';
   for (int i = 2; i != 16; ++i) {
      auto [r1, dt1] = test([&] { return compter_si_par(i, v, est_impair); });
      cout << "Parallele (" << i << " fils) :\n\t" << r1 << " impairs en "
           << duration_cast<microseconds>(dt1) << '\n';
   }
}

Ensuite, une petite activité :

  • Écrivez un programme 32 bits qui :
    • crée une carte de cases
    • chaque case peut être vide, ou contenir un héros, un vilain, une bestiole ou un mur
    • initialisez la carte de manière aléatoire pour qu'il y ait environ de cases non-vides, et pour que les non-vides soient peuplées de manière uniforme par des héros, vilains, bestioles ou murs
    • ensuite, en séquentiel puis en parallèle, comptez le nombre de « pas fins » au total dans la carte
    • un « pas fin » est soit une bestiole, soit un vilain
  • Cherchez à résoudre ce problème rapidement
    • en termes d’écriture de code
    • en termes de temps d’exécution

Une possible solution à ce problème serait :

#include <thread>
#include <vector>
#include <chrono>
#include <utility>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <cstdint>
#include <numeric>
#include <random>
using namespace std;
using namespace std::chrono;

template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

enum class Case : std::uint16_t {
   vide, heros, vilain, bestiole, mur
};
bool est_pas_fin(Case c) {
   return c == Case::vilain || c == Case::bestiole;
}

int main() {
   enum { N = 25'000 };
   vector<Case> carte;
   carte.resize(N *N); // lent... mais tout est vide
   cout << "Generation de la carte... " << flush;
   auto [r0, dt0] = test([&] {
      mt19937 prng{ random_device{}() };
      uniform_int_distribution<int> d100{ 1, 100 };
      uniform_int_distribution<int> d4{ 1, 4 };
      for (Case &c : carte) {
         if (d100(prng) <= 15) { // 15% de cases non-vides
            c = static_cast<Case>(d4(prng));
         }
      }
      return carte.size();
   });
   cout << r0 << " elements, completee en "
        << duration_cast<milliseconds>(dt0) << '\n';

   auto [r1, dt1] = test([&carte] {
      return count_if(begin(carte), end(carte), est_pas_fin);
   });

   cout << "Sequentiel :\n\t"
        << r1 << " pas fins (" << static_cast<double>(r1) * 100 / carte.size()
        << ") en " << duration_cast<milliseconds>(dt1) << "\n";

   auto [r2, dt2] = test([&] {
      auto nth = thread::hardware_concurrency();
      const size_t block_size = carte.size() / nth;
      vector<size_t> combien(nth); // initialisés à zéro
      vector<thread> fils;
      for (decltype(nth) i = 0; i < nth - 1; ++i) {
         fils.emplace_back([i, &combien,
                            b = next(begin(carte), i * block_size),
                            e = next(begin(carte), (i + 1) * block_size)] {
            combien[i] = count_if(b, e, est_pas_fin);
         });
      }
      combien[nth - 1] = count_if(
         next(begin(carte), (nth - 1) * block_size), end(carte), est_pas_fin
      );
      for (auto &fil : fils) fil.join();
      return accumulate(begin(combien), end(combien), size_t{});
   });

   cout << "Parallele " << thread::hardware_concurrency() << " coeurs) :\n\t"
      << r2 << " pas fins (" << static_cast<double>(r2) * 100 / carte.size()
      << ") en " << duration_cast<milliseconds>(dt2) << "\n";
}

Autre exercice :

  • Écrivez une classe file_circulaire_concurrente<T,N> représentant une file circulaire d'éléments de type T avec une capacité de N éléments (attention : toutes les compagnies de jeu vidéo en ont une, mais on n'a pas réussi à standardiser une telle classe en cinq ans sur WG21; c'est le genre de dossier où on doit faire des choix politiques!)
    • Quels sont les services que vous offrirez?
      • Indice : au minimum, il faudrait un constructeur par défaut, des fonctions push(), pop(), try_push() et try_pop()
    • Comment gérerez-vous les erreurs (p. ex. : insertion dans une file pleine / extraction d'une file vide)?
    • Quelles sont les options de design que l'on peut envisager pour le substrat?
      • Propriétaire d'un substrat alloué automatiquement?
      • Propriétaire d'un substrat alloué dynamiquement?
      • Propriétaire d'un substrat dont les modalités d'allocation dépendent du contexte?
      • Non-propriétaire du substrat? (un adaptateur)
      • Autre?
    • Comment assurerez-vous la synchronisation?
      • Mutex avec verrou exclusif?
      • Mutex permettant une lecture concurrente?
      • Sans mutex?
      • Que synchroniserez-vous exactement?
      • Permettrez-vous un seul consommateur ou plusieurs consommateurs? Un seul producteur ou plusieurs producteurs?

Pour un exemple de code client possible :

// ...
      
template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }

int main() {
   // using owning::non_raw::file_circulaire_concurrente;
   // using owning::raw::file_circulaire_concurrente;
   // file_circulaire_concurrente<int, 10> ze_file; // par exemple
   // using non_owning::non_raw::file_circulaire_concurrente;
   // int buf[10];
   using non_owning::raw::file_circulaire_concurrente;
   alignas(int) char buf[10 * sizeof(int)];
   file_circulaire_concurrente<int, 10> ze_file(buf); // par exemple
   atomic<bool> fini{ false };
   thread producteur{ [&] {
      for (int i = 0; i != 2000;)
         if (ze_file.try_push(i + 1))
            ++i;
         else
            cout << '.' << flush;
      fini = true;
   } };
   thread consommateur{ [&] {
      for (;;)
         if (int n; ze_file.try_pop(n))
            cout << n << ' ';
         else if (fini) {
            for (int n; ze_file.try_pop(n); )
               cout << n << ' ';
            break;
         }
   } };
   producteur.join(); consommateur.join();
}

Une implémentation possible (et naïve!) serait la suivante. Je vous propose quatre décinaisons (que vous pouvez choisir avec les directives using dans main()), toutes incopiables sauf la première :

  • La version owning::non_raw qui utilise un array<T,N> ou un unique_ptr<T[]> en fonction de la taille qu'occupera en mémoire le substrat. C'est la plus simple des quatre : des T par défaut sont construits implicitement, remplacés par les push() ou les try_push() à travers une simple affectation, et implicitement détruits à la fin de la vie utile de la file circulaire
  • La version owning::raw qui utilise un array<char,N*sizeof(T)> ou un unique_ptr<T[]> en fonction de la taille qu'occupera en mémoire le substrat. Elle crée par allocation positionnelle les T à insérer dans de la mémoire brute, et les supprime manuellement en appelant leur destructeur lors d'un pop() ou d'un try_pop()
  • La version non_owning::non_raw qui administre un substrat suppléé par le code client et qui est de type T(&)[N]
  • La version non_owning::raw qui administre un substrat suppléé par le code client et qui est de type char(&)[N*sizeof(T)]

Prenez soin, pour les versions non_owning, de choisir le substrat correctement. Des exemples sont donnés dans les commentaires :

#include <memory>
#include <type_traits>
#include <mutex>
#include <array>
#include <iostream>
#include <atomic>
#include <chrono>
#include <utility>
using namespace std;
using namespace std::chrono;

class file_vide {};
class file_pleine {};

namespace owning {
   namespace non_raw {
      template <class T, int N>
         class file_circulaire_concurrente {
            mutex m;
            static_assert(N > 1); // bof
            struct buffer {
               static auto type() {
                  if constexpr (sizeof(T) * N <= 8096)
                     return array<T, N>{};
                  else
                     return make_unique<T[]>(N);
               }
            };
            using buf_type = decltype(buffer::type());
            buf_type buf = buffer::type();
            int ins_pt = 0;
            int ext_pt = 0;
            static int next(int n) {
               return ++n, n == N ? 0 : n;
            }
            static int prev(int n) {
               return n == 0 ? N - 1 : n - 1;
            }
            bool full() const noexcept {
               return next(ins_pt) == ext_pt;
            }
            bool empty() const noexcept {
               return ins_pt == ext_pt;
            }
         public:
            void push(const T &obj) {
               lock_guard _{ m };
               if (full()) throw file_pleine{};
               buf[ins_pt] = obj;
               ins_pt = next(ins_pt);
            }
            void pop() {
               lock_guard _{ m };
               if (empty()) throw file_vide{};
               ext_pt = next(ext_pt);
            }
            T top() {
               lock_guard _{ m };
               if (empty()) throw file_vide{};
               return buf[ext_pt];
            }
            bool try_push(const T &obj) {
               lock_guard _{ m };
               if (full()) return false;
               buf[ins_pt] = obj;
               ins_pt = next(ins_pt);
               return true;
            }
            bool try_pop(T &obj) {
               lock_guard _{ m };
               if (empty()) return false;
               obj = buf[ext_pt];
               ext_pt = next(ext_pt);
               return true;
            }
         };
   }
   namespace raw {
      template <class T, int N>
         class file_circulaire_concurrente {
            mutex m;
            static_assert(N > 1); // bof
            struct buffer {
               static auto type() {
                  if constexpr (sizeof(T) * N <= 8096)
                     return array<char, sizeof(T) * N>{};
                  else
                     return make_unique<char[]>(sizeof(T) * N);
               }
            };
            using buf_type = decltype(buffer::type());
            auto data() {
               if constexpr (is_same_v<unique_ptr<char[]>, buf_type>)
                  return buf.get();
               else
                  return &buf[0];
            }
            alignas(T) buf_type buf = buffer::type();
            int ins_pt = 0;
            int ext_pt = 0;
            static int next(int n) {
               return ++n, n == N ? 0 : n;
            }
            static int prev(int n) {
               return n == 0 ? N - 1 : n - 1;
            }
            bool full() const noexcept {
               return next(ins_pt) == ext_pt;
            }
            bool empty() const noexcept {
               return ins_pt == ext_pt;
            }
            void *elem_addr(int n) {
               return data() + n * sizeof(T);
            }
            T &elem(int n) {
               return *static_cast<T*>(elem_addr(n));
            }
         public:
            void push(const T &obj) {
               lock_guard _{ m };
               if (full()) throw file_pleine{};
               new(elem_addr(ins_pt)) T(obj);
               ins_pt = next(ins_pt);
            }
            void pop() {
               lock_guard _{ m };
               if (empty()) throw file_vide{};
               elem(ext_pt).~T();
               ext_pt = next(ext_pt);
            }
            T top() {
               lock_guard _{ m };
               if (empty()) throw file_vide{};
               return elem(ext_pt);
            }
            bool try_push(const T &obj) {
               lock_guard _{ m };
               if (full()) return false;
               new(elem_addr(ins_pt)) T(obj);
               ins_pt = next(ins_pt);
               return true;
            }
            bool try_pop(T &obj) {
               lock_guard _{ m };
               if (empty()) return false;
               obj = elem(ext_pt);
               elem(ext_pt).~T();
               ext_pt = next(ext_pt);
               return true;
            }
            file_circulaire_concurrente(const file_circulaire_concurrente &) = delete;
            file_circulaire_concurrente&
               operator=(const file_circulaire_concurrente &) = delete;
            ~file_circulaire_concurrente() {
               for (T _; try_pop(_);)
                  ;
            }
            file_circulaire_concurrente() = default;
         };
   }
}

namespace non_owning {
   namespace non_raw {
      template <class T, int N>
      class file_circulaire_concurrente {
         mutex m;
         static_assert(N > 1); // bof
         T(&buf)[N];
         int ins_pt = 0;
         int ext_pt = 0;
         static int next(int n) {
            return ++n, n == N ? 0 : n;
         }
         static int prev(int n) {
            return n == 0 ? N - 1 : n - 1;
         }
         bool full() const noexcept {
            return next(ins_pt) == ext_pt;
         }
         bool empty() const noexcept {
            return ins_pt == ext_pt;
         }
      public:
         file_circulaire_concurrente(T (&buf)[N]) : buf{ buf } {
         }
         void push(const T &obj) {
            lock_guard _{ m };
            if (full()) throw file_pleine{};
            buf[ins_pt] = obj;
            ins_pt = next(ins_pt);
         }
         void pop() {
            lock_guard _{ m };
            if (empty()) throw file_vide{};
            ext_pt = next(ext_pt);
         }
         T top() {
            lock_guard _{ m };
            if (empty()) throw file_vide{};
            return buf[ext_pt];
         }
         bool try_push(const T &obj) {
            lock_guard _{ m };
            if (full()) return false;
            buf[ins_pt] = obj;
            ins_pt = next(ins_pt);
            return true;
         }
         bool try_pop(T &obj) {
            lock_guard _{ m };
            if (empty()) return false;
            obj = buf[ext_pt];
            ext_pt = next(ext_pt);
            return true;
         }
      };
   }
   namespace raw {
      template <class T, int N>
      class file_circulaire_concurrente {
         mutex m;
         static_assert(N > 1); // bof
         alignas(T) char (&buf)[N * sizeof(T)];
         int ins_pt = 0;
         int ext_pt = 0;
         static int next(int n) {
            return ++n, n == N ? 0 : n;
         }
         static int prev(int n) {
            return n == 0 ? N - 1 : n - 1;
         }
         bool full() const noexcept {
            return next(ins_pt) == ext_pt;
         }
         bool empty() const noexcept {
            return ins_pt == ext_pt;
         }
         void *elem_addr(int n) {
            return buf + n * sizeof(T);
         }
         T &elem(int n) {
            return *static_cast<T *>(elem_addr(n));
         }
      public:
         void push(const T &obj) {
            lock_guard _{ m };
            if (full()) throw file_pleine{};
            new(elem_addr(ins_pt)) T(obj);
            ins_pt = next(ins_pt);
         }
         void pop() {
            lock_guard _{ m };
            if (empty()) throw file_vide{};
            elem(ext_pt).~T();
            ext_pt = next(ext_pt);
         }
         T top() {
            lock_guard _{ m };
            if (empty()) throw file_vide{};
            return elem(ext_pt);
         }
         bool try_push(const T &obj) {
            lock_guard _{ m };
            if (full()) return false;
            new(elem_addr(ins_pt)) T(obj);
            ins_pt = next(ins_pt);
            return true;
         }
         bool try_pop(T &obj) {
            lock_guard _{ m };
            if (empty()) return false;
            obj = elem(ext_pt);
            elem(ext_pt).~T();
            ext_pt = next(ext_pt);
            return true;
         }
         file_circulaire_concurrente(const file_circulaire_concurrente &) = delete;
         file_circulaire_concurrente &
            operator=(const file_circulaire_concurrente &) = delete;
         ~file_circulaire_concurrente() {
            for (T _; try_pop(_);)
               ;
         }
         file_circulaire_concurrente(char(&buf)[N * sizeof(T)]) : buf{ buf } {
         }
      };
   }
}


template <class F, class ... Args>
   auto test(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return pair{ res, post - pre };
   }


int main() {
   // using owning::non_raw::file_circulaire_concurrente;
   // using owning::raw::file_circulaire_concurrente;
   // file_circulaire_concurrente<int, 10> ze_file; // par exemple
   // using non_owning::non_raw::file_circulaire_concurrente;
   // int buf[10];
   using non_owning::raw::file_circulaire_concurrente;
   alignas(int) char buf[10 * sizeof(int)];
   file_circulaire_concurrente<int, 10> ze_file(buf); // par exemple
   atomic<bool> fini{ false };
   thread producteur{ [&] {
      for (int i = 0; i != 2000;)
         if (ze_file.try_push(i + 1))
            ++i;
         else
            cout << '.' << flush;
      fini = true;
   } };
   thread consommateur{ [&] {
      for (;;)
         if (int n; ze_file.try_pop(n))
            cout << n << ' ';
         else if (fini) {
            for (int n; ze_file.try_pop(n); )
               cout << n << ' ';
            break;
         }
   } };
   producteur.join(); consommateur.join();
}

Pouvez-vous faire mieux?

Attendez-vous à deux minitests lors de la prochaine séance 🙂

S03 – vendredi 3 février 9 h-12 h

Au menu :

À titre de rappel, voici un exemple simple de sérialisation brute adaptative :

//
// Idéalement, loger les trois lignes qui suivent, de même que les appels
// à htons() / htonl() / ntohs() / ntohl() dans un .cpp distinct pour isoler
// le code client
//
#define NOMINMAX // car windows.h, inclus « par la bande », est un vilain garnement
#include <winsock2.h>
#pragma comment(lib,"Ws2_32.lib")

#include <iostream>
#include <algorithm>
#include <cassert>
#include <string>
#include <type_traits>
#include <iterator>
using namespace std;

template <class T>
T normaliser(T val) { return val; }

short normaliser(short val) { return htons(val); }
int normaliser(int val) { return htonl(val); }
long normaliser(long val) { return htonl(val); }

template <class T>
   enable_if_t<is_integral<T>::value, char *>
      serialiser_brut(const T &val, char *p) {
      static_assert(is_trivially_copyable_v<T>);
      auto valeur = normaliser(val);
      copy(reinterpret_cast<const char *>(&valeur),
           reinterpret_cast<const char *>(&valeur + 1), p);
      return p + sizeof(T);
   }
template <class T>
   enable_if_t<!is_integral<T>::value, char *>
      serialiser_brut(const T &val, char *p) {
      static_assert(is_trivially_copyable_v<T>);
      copy(reinterpret_cast<const char *>(&val),
           reinterpret_cast<const char *>(&val + 1), p);
      return p + sizeof(T);
   }
int main() {
   float f = 3.14159f;
   long lg = 3L;
   char c = 'A';
   string s = "J'aime mon prof";
   char buf[sizeof(f) + sizeof(lg) + sizeof(c)] = {};
   auto p = begin(buf);
   p = serialiser_brut(f, p);
   p = serialiser_brut(lg, p);
   p = serialiser_brut(c, p);
   // p = serialiser_brut(s, p); // illégal!
   assert(p == end(buf));
}

Si le temps le permet (sinon, ce qui est probable, ça ira à S04) :

Dans les notes de cours :

  • La sérialisation est discutée en détail dans CPA – Volume 03, pp. ≈10-46

Les semaines du 6, du 13 et du 20 février, notre cours fait relâche. Bon travail sur votre projet, les ami(e)s!

S04 – vendredi 3 mars 9 h-12 h

Au menu :

  • Utiliser std::shared_ptr<T>
    • Comparaison avec std::unique_ptr<T>
    • Pourquoi std::make_shared<T>(args...)
    • Partie plus croustillante :
      • Construction d'un pointeur intelligent implémentant une sémantique de partage – sorte de shared_ptr maison – pour voir et comprendre ce que cela implique
        • ça semble court comme menu, mais c'est vraiment rien de simple
  • Implémenter un pointeur intelligent « maison » avec sémantique de duplication (clonage pour les clonables, copie pour les autres)
  • D'autres pointeurs intelligents, simples et utiles :
  • Sémantiques d'accès :
    • sémantique de responsabilité unique (p. ex. : std::unique_ptr<T>)
    • sémantique de partage (p. ex. : std::shared_ptr<T>)
    • sémantique de duplication (p. ex. : notre petit dup_ptr<T>)
    • sémantique de référence (p. ex. : T*, non_null_ptr<T>, observer_ptr<T>, etc.)
    • etc.

N'oubliez pas de remettre L00

S05 – vendredi 10  mercredi 8 mars 9 h-12 h

Au menu :

S06 – vendredi 17 mars 9 h-12 h

Au menu :

  • Petit défi technique : implantons un mécanisme de facettes non-intrusive (au sens où il n'oblige pas les facettes à dériver elles-mêmes de Facette) tel que le programme ci-dessous fonctionne, n'entraîne pas de fuites de ressources, et offre l'affichage attendu. Le code client imposé est :
#include "FacetteServer.h"
#include <iostream>
#include <string_view>
using namespace std::literals;
struct Texture {
   constexpr auto getTextureName() const noexcept {
      return "Je suis un nom de texture"sv;
   }
};
struct TextureManager {
   Texture getTexture() const noexcept {
      return {};
   }
};
struct Sound {
   constexpr auto getFileName() const noexcept {
      return "SomeSound.wav"sv;
   }
};
struct SoundManager {
   Sound getSound() const noexcept {
      return {};
   }
};
int main() {
   using namespace std;
   auto &serveur = FacetteServer::get();
   serveur.installer(TextureManager{});
   serveur.installer(SoundManager{});
   // ...
   cout << utiliser_facette<SoundManager>(serveur).getSound().getFileName() << endl;
   cout << utiliser_facette<TextureManager>(serveur).getTexture().getTextureName() << endl;
}

La sortie attendue est : 

SomeSound.wav
Je suis un nom de texture

Pour un solutionnaire, voir ../../Sujets/Divers--cplusplus/Facettes.html#facettes_non_intrusives

S07 – vendredi 24 mars 9 h-12 h

Au menu :

  • Q06
  • AoS ou SoA
    • ce que ça signifie
    • conséquences
  • SSO et SOO
  • S'il reste du temps : diverses techniques d'optimisation, incluant la tristement (!) célèbre Duff's Device
  • Quelques bribes de métaprogrammation

Le code utilisé pour la métaprogrammation était :

#include <type_traits>
#include <iostream>
using namespace std;

// template <class T, T val> struct integral_constant {
//    using type = T;
//    static constexpr const auto value = val;
//    constexpr auto operator()() const noexcept { return value; }
// };

template <int N> struct int_ : integral_constant<int, N> {};

template <auto V> struct constant_ {
   using type = decltype(V);
   static constexpr auto value = V;
   constexpr auto operator()() const noexcept { return value; }
};

template <class ...> struct type_list;



//template <class TL> struct static_somme;
//template <class T, class ... Q>
//struct static_somme<type_list<T, Q...>>
//   : int_<T::value + static_somme<type_list<Q...>>::value>{
//};
//template <> struct static_somme<type_list<>> : int_<0> {
//};
//
//template <class TL> struct static_produit;
//template <class T, class ... Q>
//struct static_produit<type_list<T, Q...>>
//   : int_<T::value * static_produit<type_list<Q...>>::value> {
//};
//template <> struct static_produit<type_list<>> : int_<1> {
//};

template <class T, class U>
   struct somme_ : int_<T::value + U::value> {};
template <class T, class U>
   struct produit_ : int_<T::value * U::value> {};

template <class TL, template <class, class> class F, class Init>
   struct static_cumul;
template <class T, class ... Q, template <class, class> class F, class Init>
   struct static_cumul<type_list<T, Q...>, F, Init>
      : F<T, static_cumul<type_list<Q...>, F, Init>> {
   };
template <template <class, class> class F, class Init>
   struct static_cumul<type_list<>, F, Init>
      : Init {
   };

template <class TL> using static_somme = static_cumul<TL, somme_, int_<0>>;
template <class TL> using static_produit = static_cumul<TL, produit_, int_<1>>;

template <auto ... > struct value_list;

int main() {
   using prems_v = value_list<2, 3L, 5, 7, 11>;
   using prems = type_list<
      constant_<2>, constant_<3L>, constant_<5>, constant_<7>, constant_<11>
   >;
   static_assert(static_somme<prems>::value == 28);
   static_assert(static_produit<prems>::value == 2310);
}

Pour l'exercice portant sur les facettes non-intrusives, voir ../../Sujets/Divers--cplusplus/Facettes.html#facettes_non_intrusives

Les semaines du 27 mars, du 3 et du 10 avril, notre cours fait relâche. Bon travail sur votre projet, les ami(e)s!

S08 – mercredi 19 avril 9 h-12 h

Au menu :

Sur le plan des demandes spéciales :

Pour s'amuser

  • Un truc expérimental : on s'écrit un « variant des pauvres ».

Étape 0 : on veut juste qu'un programme comme celui-ci compile :

// ...
#include <string>
using namespace std;
int main() {
   [[maybe_unused]] one_of<int, double, string> v;
}

Solution (https://wandbox.org/permlink/Vj64bka37OKW7mbf) :

template <class ... Ts>
class one_of {
};
#include <string>
using namespace std;
int main() {
   [[maybe_unused]] one_of<int, double, string> v;
}

Étape 1 : on veut que notre type one_of<Ts...> puisse entreposer le plus gros des types de Ts...

Solution (https://wandbox.org/permlink/UxdN9wNQYR8anb99) :

#include <algorithm>
#include <cstddef>
template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
};
#include <string>
using namespace std;
int main() {
   using type = one_of<int, double, string>;
   [[maybe_unused]] type v;
   static_assert(sizeof v >= sizeof(string));
   static_assert(alignof(type) == alignof(double)); // alignof(v) illégal en C++20 (discuté pour C++23)
}

Note : y a-t-il une solution moins... manuelle, disons, à ce problème?

 Oui, mais... pas vraiment, en fait :

#include <algorithm>
#include <cstddef>
#include <type_traits>
template <class ... Ts>
class one_of {
   std::aligned_storage_t<std::max({ sizeof(Ts)... })> buf; // mais...
};
#include <string>
using namespace std;

int main() {
   using type = one_of<int, double, string>;
   [[maybe_unused]] type v;
   static_assert(sizeof v >= sizeof(string));
   // static_assert(alignof(type) == alignof(double));
}

En pratique, on s'est aperçus que std::aligned_storage<T> n'est pas vraiment mieux qu'un tampon aligné manuellement, alors ce type est maintenant déprécié. Évitez-le dans du nouveau code.

Étape 2 : comment savoir lequel des types de Ts... est entreposé dans un one_of<Ts...>?

Solution :

#include <algorithm>
#include <cstddef>
#include <type_traits>
template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
   // question de design ici, faut faire un choix :
   // - ou lequel n'est pas initialisé (bris d'encapsulation, objet mal-formé)
   // - ou lequel doit être initialisé par le code client (pas de constructeur
   //   par défaut)
   // - ou lequel a une valeur par défaut, disons 0 (choix du standard, en
   //   conformité avec les union)
   int lequel = 0;
};
#include <string>
using namespace std;
int main() {
   using type = one_of<int, double, string>;
   [[maybe_unused]] type v;
}

Étape 3 : les implémentations choisissent typiquement le type entier utilisé pour la représentation sur la base de sizeof...(Ts) , bien que le type des fonctions exposant cette valeur soit, elle, normée. Ceci permet de réduire la taille d'un variant (ou, du moins, l'impact de l'indice sur cette taille). Comment pourrait-on y arriver?

Implémentation possible (https://wandbox.org/permlink/8rkDKliJ3i13dmFc) :

#include <algorithm>
#include <cstddef>
#include <type_traits>
// j'ai choisi des types signés, mais on aurait pu
// faire d'autres choix
template <class ... Ts>
struct smallest_fitting {
   using type = std::conditional_t<
      (sizeof...(Ts) < 128), char,
      std::conditional_t<
         (sizeof...(Ts) < 32768), short, int
      >
   >;
};
template <class ... Ts>
   using smallest_fitting_t = typename smallest_fitting<Ts...>::type;

template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
   smallest_fitting_t<Ts...> lequel = 0;
};
#include <string>
using namespace std;
int main() {
   using type = one_of<int, double, string>;
   static_assert(is_same_v<smallest_fitting_t<int,double,string>, char>);
   [[maybe_unused]] type v;
}

Autre implémentation possible (https://wandbox.org/permlink/Sh8VqA0fTmVMsWSz) :

#include <algorithm>
#include <cstddef>
#include <type_traits>
// j'ai choisi des types signés, mais on aurait pu
// faire d'autres choix
template <class ... Ts>
consteval auto smallest_fitting() {
   if constexpr(sizeof...(Ts) < 128)
      return char{};
   else if constexpr (sizeof...(Ts) < 32768)
      return short{};
   else
      return int{};
};

template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
   decltype(smallest_fitting<Ts...>()) lequel = 0;
};
#include <string>
using namespace std;
int main() {
   using type = one_of<int, double, string>;
   static_assert(is_same_v<decltype(smallest_fitting<int,double,string>()), char>);
   [[maybe_unused]] type v;
}

Notez que j'ai utilisé consteval (fonction immédiate) de C++ 20 ici... pour vous le présenter; dans ce cas, constexpr aurait aussi fonctionné.

Étape 4 : il y a des coûts au choix de design fait à l'étape précédente. Comment y pallier?

Solution (https://wandbox.org/permlink/QBNyIsb5NXoOkgCR) :

#include <algorithm>
#include <cstddef>
#include <type_traits>
template <class ... Ts>
consteval auto smallest_fitting() {
   if constexpr(sizeof...(Ts) < 128)
      return char{};
   else if constexpr (sizeof...(Ts) < 32768)
      return short{};
   else
      return int{};
};
// solution du standard : offrir un type constructible à coût
// nul pour les cas où on voudrait un objet "par défaut, et
// sans coût" (mettre mono_etat comme premier type). Ici,
// il n'y aurait pas d'impact car le premier type dans le code
// client a un constructeur par défaut trivial, mais si tous
// les types avaient des constructeurs non-triviaux, ce serait
// une autre histoire
class mono_etat {}; // std::monostate pour les variant
template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
   decltype(smallest_fitting<Ts...>()) lequel = 0;
};
#include <iostream>
#include <string>
using namespace std;
int main() {
   using type = one_of<int, double, string>;
   [[maybe_unused]] type v;
}

Étape 5 : l'enjeu devient maintenant de créer l'objet à déposer dans notre one_of<Ts...>, et de ne pas accepter de types qui ne font pas partie de Ts...

Solution (https://wandbox.org/permlink/Od0bmhJSXqI2ds3w) :

#include <algorithm>
#include <cstddef>
#include <type_traits>
#include <utility>
class mono_etat {};

// on aurait pu utiliser std::tuple
template <class...> struct type_list;

template <class> struct first_type;
template <class T, class ...Ts> struct first_type<type_list<T, Ts...>> {
   using type = T;
};
template <class ...Ts> using first_type_t = typename first_type<type_list<Ts...>>::type;

// raccourci
template <auto V> struct constant : std::integral_constant<decltype(V), V> {};

template <class, class> struct tl_indice;

template <class T, class ... Ts>
   struct tl_contains : constant<tl_indice<T, type_list<Ts...>>::value != -1> {
   };

template <class U, class T, class ... Q>
struct tl_indice<U, type_list<T, Q...>>
   : std::conditional_t<
        (tl_contains<U, Q...>::value == -1),
        constant<-1>,
        constant<1 + tl_indice<U, type_list<Q...>>::value>
     > {
};
template <class T, class ... Q>
   struct tl_indice<T, type_list<T, Q...>> : constant<0> {
   };
template <class T>
   struct tl_indice<T, type_list<>> : constant<-1> {
   };


template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
   int lequel = 0;
public:
   template <class T>
      one_of(T && obj) {
         static_assert(tl_contains<T, Ts...>::value);
         new (static_cast<void *>(&buf)) T(std::forward<T>(obj));
         lequel = tl_indice<T, type_list<Ts...>>::value; 
      }
   one_of() : one_of(first_type_t<Ts...>{}) {
   }
};

#include <iostream>
#include <string>
using namespace std;
int main() {
   using type = one_of<int, double, string>;
   type v;
   v = type{ 2 }; // Ok
   v = type{ 2.0 }; // Ok
   v = type{ "2"s }; // Ok
   // v = type{ "2" }; // pas Ok
}

Étape 6 : peut-on tester efficacement si un one_of<Ts...> contient un T à un moment précis?

Solution (https://wandbox.org/permlink/xI0k5BGTlnDCjXWN) :

#include <algorithm>
#include <cstddef>
#include <type_traits>
#include <utility>
class mono_etat {};

// on aurait pu utiliser std::tuple
template <class...> struct type_list;

template <class> struct first_type;
template <class T, class ...Ts> struct first_type<type_list<T, Ts...>> {
   using type = T;
};
template <class ...Ts> using first_type_t = typename first_type<type_list<Ts...>>::type;

// raccourci
template <auto V> struct constant : std::integral_constant<decltype(V), V> {};

template <class, class> struct tl_indice;

template <class T, class ... Ts>
   struct tl_contains : constant<tl_indice<T, type_list<Ts...>>::value != -1> {
   };

template <class U, class T, class ... Q>
struct tl_indice<U, type_list<T, Q...>>
   : std::conditional_t<
        (tl_contains<U, Q...>::value == -1),
        constant<-1>,
        constant<1 + tl_indice<U, type_list<Q...>>::value>
     > {
};
template <class T, class ... Q>
   struct tl_indice<T, type_list<T, Q...>> : constant<0> {
   };
template <class T>
   struct tl_indice<T, type_list<>> : constant<-1> {
   };

template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
   int lequel = 0;
public:
   template <class T>
      one_of(T && obj) {
         static_assert(tl_contains<T, Ts...>::value);
         new (static_cast<void *>(&buf)) T(std::forward<T>(obj));
         lequel = tl_indice<T, type_list<Ts...>>::value;
      }
   one_of() : one_of(first_type_t<Ts...>{}) {
   }
   template <class T>
      bool contient() const { // holds_alternative
         static_assert(tl_contains<T, Ts...>::value);
         return lequel == tl_indice<T, Ts...>::value;
      }
};

#include <iostream>
#include <string>
using namespace std;
int main() {
   using type = one_of<int, double, string>;
   type v;
   v = type{ 2 }; // Ok
   v = type{ 2.0 }; // Ok
   v = type{ "2"s }; // Ok
   // v = type{ "2" }; // pas Ok
}

Étape 7 : le standard fait la même chose avec des fonctions non-membres. Comment le faire nous-mêmes?

Solution (https://wandbox.org/permlink/7MIhfLmK35aYWxzA) :

#include <algorithm>
#include <cstddef>
#include <type_traits>
#include <utility>
class mono_etat {};

// on aurait pu utiliser std::tuple
template <class...> struct type_list;

template <class> struct first_type;
template <class T, class ...Ts> struct first_type<type_list<T, Ts...>> {
   using type = T;
};
template <class ...Ts> using first_type_t = typename first_type<type_list<Ts...>>::type;

// raccourci
template <auto V> struct constant : std::integral_constant<decltype(V), V> {};

template <class, class> struct tl_indice;

template <class T, class ... Ts>
   struct tl_contains : constant<tl_indice<T, type_list<Ts...>>::value != -1> {
   };

template <class U, class T, class ... Q>
struct tl_indice<U, type_list<T, Q...>>
   : std::conditional_t<
        (tl_contains<U, Q...>::value == -1),
        constant<-1>,
        constant<1 + tl_indice<U, type_list<Q...>>::value>
     > {
};
template <class T, class ... Q>
   struct tl_indice<T, type_list<T, Q...>> : constant<0> {
   };
template <class T>
   struct tl_indice<T, type_list<>> : constant<-1> {
   };

template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
   int lequel = 0;
public:
   template <class T>
      one_of(T && obj) {
         static_assert(tl_contains<T, Ts...>::value);
         new (static_cast<void *>(&buf)) T(std::forward<T>(obj));
         lequel = tl_indice<T, type_list<Ts...>>::value;
      }
   one_of() : one_of(first_type_t<Ts...>{}) {
   }
   template <class T, class ... TTs>
      friend bool contient(const one_of<TTs...> &);
};

template <class T, class ... Ts>
bool contient(const one_of<Ts...> &v) {
   static_assert(tl_contains<T, Ts...>::value);
   return v.lequel == tl_indice<T, Ts...>::value;
}

#include <iostream>
#include <string>
using namespace std;
int main() {
   using type = one_of<int, double, string>;
   type v;
   v = type{ 2 }; // Ok
   v = type{ 2.0 }; // Ok
   v = type{ "2"s }; // Ok
   // v = type{ "2" }; // pas Ok
}

L'idée est que variant est, en fait, un protocole, et qu'il est possible d'écrire d'autres types remplissant les conditions de ce protocole. Le recours à des fonctions non-membres ouvre la possibilité de personnaliser cet services de manière à pouvoir en bénéficier dans le contexte de code générique.

Étape 8 : et si on veut une fonction get<N>(oo) comme le fait le standard, pour extraire une valeur d'un certain type à partir d'un indice connu à la compilation?

Solution  https://wandbox.org/permlink/j0pe46a2wR5wIocP) :

#include <algorithm>
#include <cstddef>
#include <type_traits>
#include <utility>
class mono_etat {};

// on aurait pu utiliser std::tuple
template <class...> struct type_list;

template <class> struct first_type;
template <class T, class ...Ts> struct first_type<type_list<T, Ts...>> {
   using type = T;
};
template <class ...Ts> using first_type_t = typename first_type<type_list<Ts...>>::type;

template <class> struct tail_types_helper;
template <class T, class ...Q> struct tail_types_helper<type_list<T, Q...>> {
   using type = type_list<Q...>;
};
template <class T> struct tail_types_helper<type_list<T>> {
   using type = type_list<>;
};

template <class ... Ts>
   using tail_types = typename tail_types_helper<type_list<Ts...>>::type;


// raccourci
template <auto V> struct constant : std::integral_constant<decltype(V), V> {};

template <class, class> struct tl_indice;

template <class T, class ... Ts>
   struct tl_contains : constant<tl_indice<T, type_list<Ts...>>::value != -1> {
   };

template <class U, class T, class ... Q>
struct tl_indice<U, type_list<T, Q...>>
   : std::conditional_t<
        (tl_contains<U, Q...>::value == -1),
        constant<-1>,
        constant<1 + tl_indice<U, type_list<Q...>>::value>
     > {
};
template <class T, class ... Q>
   struct tl_indice<T, type_list<T, Q...>> : constant<0> {
   };
template <class T>
   struct tl_indice<T, type_list<>> : constant<-1> {
   };

template <int, class> struct tl_type_helper;

template <int N, class ... Ts>
   using tl_type = typename tl_type_helper<N, type_list<Ts...>>::type;

template <int N, class ... Ts>
   struct tl_type_helper<N, type_list<Ts...>> {
      // static_assert(N < sizeof...(Q) + 1);
      using type = typename tl_type_helper<N - 1, tail_types<Ts...>>::type;
   };
template <class ...Ts>
   struct tl_type_helper<0, type_list<Ts...>> {
      using type = first_type_t<Ts...>;
   };


template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
   int lequel = 0;
public:
   template <class T>
      one_of(T && obj) {
         static_assert(tl_contains<T, Ts...>::value);
         new (static_cast<void *>(&buf)) T(std::forward<T>(obj));
         lequel = tl_indice<T, type_list<Ts...>>::value;
      }
   one_of() : one_of(first_type_t<Ts...>{}) {
   }
   template <class T, class ... TTs>
      friend bool contient(const one_of<TTs...> &);
   template <int N, class ... TTs>
      friend tl_type<N, TTs...> &get_(one_of<TTs...> &);
   template <int N, class ... TTs>
      friend const tl_type<N, TTs...> &get_(const one_of<TTs...> &);
};

template <class T, class ... Ts>
bool contient(const one_of<Ts...> &v) {
   static_assert(tl_contains<T, Ts...>::value);
   return v.lequel == tl_indice<T, type_list<Ts...>>::value;
}

template <int N, class ... Ts>
   tl_type<N, Ts...> & get_(one_of<Ts...> &v) {
      return *static_cast<tl_type<N, Ts...>*>(static_cast<void *>(&v.buf));
   };
template <int N, class ... Ts>
   const tl_type<N, Ts...> &get_(const one_of<Ts...> &v) {
      return *static_cast<const tl_type<N, Ts...> *>(static_cast<const void *>(&v.buf));
   };

#include <iostream>
#include <string>
#include <cassert>
using namespace std;
int main() {
   using type = one_of<int, double, string>;
   type v;
   v = type{ 2 }; // Ok
   cout << get_<0>(v) << endl;
   v = type{ 3.5 }; // Ok
   cout << get_<1>(v) << endl;
   v = type{ "allo"s }; // Ok
   assert(contient<string>(v));
   // v = type{ "2" }; // pas Ok
   cout << get_<2>(v) << endl;
   // cout << get_<3>(v) << endl; // ne compile pas
}

Étape 9 : et... si on veut une sorte de visit()?

Solution (https://wandbox.org/permlink/Fc5N7hhKzh8OZkig) :

#include <algorithm>
#include <cstddef>
#include <type_traits>
#include <utility>
class mono_etat {};

// on aurait pu utiliser std::tuple
template <class...> struct type_list;

template <class> struct first_type;
template <class T, class ...Ts> struct first_type<type_list<T, Ts...>> {
   using type = T;
};
template <class ...Ts> using first_type_t = typename first_type<type_list<Ts...>>::type;

template <class> struct tail_types_helper;
template <class T, class ...Q> struct tail_types_helper<type_list<T, Q...>> {
   using type = type_list<Q...>;
};
template <class T> struct tail_types_helper<type_list<T>> {
   using type = type_list<>;
};

template <class ... Ts>
   using tail_types = typename tail_types_helper<type_list<Ts...>>::type;


// raccourci
template <auto V> struct constant : std::integral_constant<decltype(V), V> {};

template <class, class> struct tl_indice;

template <class T, class ... Ts>
   struct tl_contains : constant<tl_indice<T, type_list<Ts...>>::value != -1> {
   };

template <class U, class T, class ... Q>
struct tl_indice<U, type_list<T, Q...>>
   : std::conditional_t<
        (tl_contains<U, Q...>::value == -1),
        constant<-1>,
        constant<1 + tl_indice<U, type_list<Q...>>::value>
     > {
};
template <class T, class ... Q>
   struct tl_indice<T, type_list<T, Q...>> : constant<0> {
   };
template <class T>
   struct tl_indice<T, type_list<>> : constant<-1> {
   };

template <int, class> struct tl_type_helper;

template <int N, class ... Ts>
   using tl_type = typename tl_type_helper<N, type_list<Ts...>>::type;

template <int N, class ... Ts>
   struct tl_type_helper<N, type_list<Ts...>> {
      // static_assert(N < sizeof...(Q) + 1);
      using type = typename tl_type_helper<N - 1, tail_types<Ts...>>::type;
   };
template <class ...Ts>
   struct tl_type_helper<0, type_list<Ts...>> {
      using type = first_type_t<Ts...>;
   };

template <class> struct tl_size_helper;
template <class ... Ts> struct tl_size_helper<type_list<Ts...>>
   : constant<sizeof...(Ts)> {
};
template <class TL> constexpr auto tl_size = tl_size_helper<TL>();

template <class ... Ts>
class one_of {
   alignas(std::max({ alignof(Ts)... })) std::byte buf[std::max({ sizeof(Ts)... })];
   int lequel = 0;
public:
   template <class T>
      one_of(T && obj) {
         static_assert(tl_contains<T, Ts...>::value);
         new (static_cast<void *>(&buf)) T(std::forward<T>(obj));
         lequel = tl_indice<T, type_list<Ts...>>::value;
      }
   one_of() : one_of(first_type_t<Ts...>{}) {
   }
   auto index() const {
      return lequel;
   }
   template <class T, class ... TTs>
      friend bool contient(const one_of<TTs...> &);
   template <int N, class ... TTs>
      friend tl_type<N, TTs...> &get_(one_of<TTs...> &);
   template <int N, class ... TTs>
      friend const tl_type<N, TTs...> &get_(const one_of<TTs...> &);
};

template <class T, class ... Ts>
bool contient(const one_of<Ts...> &v) {
   static_assert(tl_contains<T, Ts...>::value);
   return v.lequel == tl_indice<T, type_list<Ts...>>::value;
}

template <int N, class ... Ts>
   tl_type<N, Ts...> & get_(one_of<Ts...> &v) {
      return *static_cast<tl_type<N, Ts...>*>(static_cast<void *>(&v.buf));
   };
template <int N, class ... Ts>
   const tl_type<N, Ts...> &get_(const one_of<Ts...> &v) {
      return *static_cast<const tl_type<N, Ts...> *>(static_cast<const void *>(&v.buf));
   };

template <class>
   struct bloquer_la_compilation : std::false_type {
   };
template <class Raison>
   class Incompilable {
      static_assert(bloquer_la_compilation<Raison>());
   };

template <class R, size_t I>
   struct visit_impl {
      template <class OO, class F>
         static R visit(OO &oo, size_t n, F f) {
            if (n == I - 1)
               return f(get_<I - 1>(oo));
            else
               return visit_impl<R, I - 1>::visit(oo, n, f);
         }
   };
template <class R>
   struct visit_impl<R, 0> {
      template <class OO, class F>
         static R visit(OO &, size_t, F) {
            throw 0; // mieux, erreur à la compilation
         }
   };

template <class F, class... Ts>
   auto visit_at(const one_of<Ts...> &v, size_t n, F f) {
      return visit_impl <decltype(f(get_<0>(v))), sizeof...(Ts) > ::visit(v, n, f);
   }

template <class F, class... Ts>
   auto visit_at(one_of<Ts...> &v, size_t n, F f) {
      return visit_impl<decltype(f(get_<0>(v))), sizeof...(Ts)>::visit(v, n, f);
   }

template <class V, class ...Ts>
   auto visiter(V && viz, const one_of<Ts...> &v) {
      return visit_at(v, v.index(), viz);
   }
template <class V, class ...Ts>
   auto visiter(V &&viz, one_of<Ts...> &v) {
      return visit_at(v, v.index(), viz);
   }

#include <iostream>
#include <string>
#include <cassert>
using namespace std;

struct Viz {
   auto operator()(int) const { return "int"s; }
   auto operator()(double) const { return "double"s; }
   auto operator()(string) const { return "string"s; }
};


int main() {
   using type = one_of<int, double, string>;
   type v;
   v = type{ 2 }; // Ok
   cout << get_<0>(v) << endl;
   cout << visiter(Viz{}, v) << endl;
   v = type{ 3.5 }; // Ok
   cout << get_<1>(v) << endl;
   cout << visiter(Viz{}, v) << endl;
   v = type{ "allo"s }; // Ok
   assert(contient<string>(v));
   // v = type{ "2" }; // pas Ok
   cout << get_<2>(v) << endl;
   // cout << get_<3>(v) << endl; // ne compile pas
   cout << visiter(Viz{}, v) << endl;
}

Il en reste beaucoup à faire (la Sainte-Trinité n'est pas implémentée, par exemple. les opérateurs relationnels non-plus)... Cela dit, j'espère que cela vous donne un aperçu des défis (amusants!) associés à une implémentation, même simpliste, d'un tel type. Pour en savoir plus sur le problème du destructeur d'un std::variant, voir cette présentation d'Andrei Alexandrescu en 2021 : https://www.youtube.com/watch?v=va9I2qivBOA

S09 – mercredi 26 avril 9 h-12 h

Chic examen final!

Consignes des livrables

Les consignes des livrables L00 et L01 suivent (dates de remise incluses).

Ce cours portant sur des concepts de programmation, j'ai décidé de demander de vous non pas un rapport, mais bien un exemple de ce que vous pouvez apporter, en tant que programmeuse ou en tant que programmeur, à votre équipe de développement dans le cadre du projet de session.

Je conserverai un modèle reposant sur deux livrables, comme c'était le cas en INF737. Le premier devra être livré aux alentours de la mi-session (séance S04), alors que le second devra être livré vers la fin de la session (ne dépassez pas le 14 mai s'il vous plaît, pour me permettre de respecter les délais de remise de note).

Livrable 00

Le premier livrable de la session sera un descriptif d'un design que vous comptez mettre en place par vous-même, dans le but soit de contribuer quelque chose de spécial à votre projet, soit de contribuer quelque chose qui vous semble pertinent au moteur de jeu commercial que vous utiliserez dans la session, soit de contribuer à un outil auxiliaire qui aidera votre équipe.

Ce descriptif devra indiquer clairement :

Notez que je suis ouvert à des explorations dans d'autres langages (Python, Lua, C#, etc.), particulièrement pour le développement d'outils tiers, mais si vous souhaitez aller en ce sens, je voudrai que votre produit soit interopérable avec C++ (ceci peut impliquer exposer une API pouvant être consommée par le moteur à l'aide de code C++, par exemple).

Livrable 01

Le second livrable de la session sera le code fini, de même qu'un document succinct expliquant :

J'espère que vous apprécierez l'expérience!

Vous pouvez me remettre ce livrable le 14 mai (ce qui nous amène après votre présentation de projet devant public), par courriel à Patrice.Roy@USherbrooke.ca

Attentes dans le projet de session en lien avec ce cours

À venir...

Les consignes des livrables vont plus en détail; n'hésitez pas à communiquer avec moi si vous souhaitez des clarifications.

Valid XHTML 1.0 Transitional

CSS Valide !