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 – mardi 16 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: é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: 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: 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() {
         using std::swap;
         vector<T> temp;
         lock_guard _{ m };
         swap(data, temp);
         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 19 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 – mardi 23 janvier 9 h-12 h

Au menu :

  • Q00

Exemple « fait main » de faux-partage.

En détail :

#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>
#include <execution>
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";

   auto [r3, dt3] = test([&carte] {
      return count_if(execution::par, begin(carte), end(carte), est_pas_fin);
   });
   cout << "Algo par. " << thread::hardware_concurrency() << " coeurs) :\n\t"
      << r3 << " pas fins (" << static_cast<double>(r3) * 100 / carte.size()
      << ") en " << duration_cast<milliseconds>(dt3) << "\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 26 janvier 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; }

//
// vous pouvez faire mieux que ce qui suit en utilisant
// <cstdint>, ou encore en choissant les fonctions
// de normalisation et de dénormalisation sur la base de
// la taille des types quand il s'agit d'entiers
//
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

S04 – vendredi 2 février 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.

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

S05 – vendredi 8 mars 9 h-12 h

Au menu :

 

N'oubliez pas de remettre L00

S06 – vendredi 15 mars 9 h-12 h

 

S07 – vendredi 22 mars 9 h-12 h

 

Le vendredi 29 mars est jour férié.

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

S08 – vendredi 19 avril 9 h-12 h

 

S09 vendredi 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 S05), alors que le second devra être livré vers la fin de la session (ne dépassez pas le 13 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 au plus tard le 13 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 !