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

Vendredi 12 janvier AM

S00

Au menu :

• Bases de multiprogrammation
• Synchronisation sécurisée

Notez que nous examinons dans ce cours des techniques portables vers plusieurs plateformes et plusieurs compilateurs, mais que C++ 11 offre maintenant une API pleinement portable de threading et de synchronisation. Vous en verrez un exemple ici, et je vous montrerai comment en implémenter les bases vous-mêmes si vous le souhaitez.

Cela dit, il est possible (pour ne pas dire probable) que cette API ne soit pas 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.

Dans les notes de cours :

• Pour l'essentiel, ce qui a été couvert aujourd'hui apparaît dans CPA – Volume 01, pp. ≈9-41

Vendredi 19 janvier AM

S01

Au menu :

• Outils de synchronisation portables
• Outils de synchronisation propres à la plateforme (outils systèmes, outils locaux au processus)
• std::mutex
• std::lock_guard
• std::unique_lock
• std::lock() (il existe aussi un std::try_lock())
• les variables conditionnelles
• Les futures, les promesses et la fonction std::async()
• Le type monitor<T>
• Utiliser des mutex intelligemment : l'exemple d'une zone de transit synchronisée
• Objets volatiles

Dans les notes de cours :

• Les objets volatiles sont expliqués dans CPA – Volume 01, pp. ≈99-123
• Un tableau résumant les impacts du mot volatile apparaît dans CPA – Volume 01, p. 117
• À propos de l'atomicité, voir Atomicite.pdf (document qui demande à être retravaillé, mais c'est mieux que rien)

template <class T, class F, class ... Args>
   auto async(F f, Args && ... args) -> decltype(f(std::forward<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;
   }

#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 tester(F f, Args &&... args) {
   auto pre = high_resolution_clock::now();
   auto res = f(std::forward<Args>(args)...);
   auto post = high_resolution_clock::now();
   return make_pair(res, post - pre);
}

enum class Case : unsigned char {
   Vide, Heros, Mur, Vilain, Bibitte
};

int main() {
   locale::global(locale{ "" });
   enum { LARGEUR = 25'000, HAUTEUR = 25'000 };
   vector<Case> carte(LARGEUR * HAUTEUR, Case::Vide);
   random_device rd;
   mt19937 prng{ rd() };
   uniform_int_distribution<int> d100{ 1,100 }, d4{ 1,4 };
   auto temps_init = tester([&] {
      generate(begin(carte), end(carte), [&] {
         return d100(prng) <= 85 ? Case::Vide :
            static_cast<Case>(d4(prng));
      });
      return 0;
   });
   cout << "Initialisation complétée en "
        << duration_cast<milliseconds>(temps_init.second).count()
        << " ms." << endl;
   cout << "Nb pas gentils (séquentiel) : ";
   auto seq = tester([&] {
      return count_if(begin(carte), end(carte), [](Case c) {
         return c == Case::Bibitte || c == Case::Vilain;
      });
   });
   cout << seq.first << " obtenu en "
        << duration_cast<milliseconds>(seq.second).count()
        << " ms." << endl;
   //
   // Ok, on y va...
   //
   cout << "Nb pas gentils (parallèle) : ";
   auto para = tester([&] {
      auto ncoeurs = thread::hardware_concurrency();
      const auto taille_bloc = carte.size() / ncoeurs;
      vector<future<int>> v;
      for (decltype(ncoeurs) i = 0; i != ncoeurs - 1; ++i)
         v.emplace_back(async([deb = begin(carte) + i * taille_bloc,
            fin = begin(carte) + (i + 1) * taille_bloc]{
            return count_if(deb, fin, [](Case c) {
               return c == Case::Bibitte || c == Case::Vilain;
            });
         }));
      auto n = count_if(begin(carte) + (ncoeurs - 1) * taille_bloc,
         end(carte), [](Case c) {
         return c == Case::Bibitte || c == Case::Vilain;
      });
      return accumulate(begin(v), end(v), n, [](int so_far, future<int> &f) {
         return so_far + f.get();
      });
   });
   cout << para.first << " obtenu en "
        << duration_cast<milliseconds>(para.second).count()
        << " ms." << endl;
}

#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 tester(F f, Args &&... args) {
   auto pre = high_resolution_clock::now();
   auto res = f(std::forward<Args>(args)...);
   auto post = high_resolution_clock::now();
   return make_pair(res, post - pre);
}

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

Mardi 23 janvier PM

S02

Au menu :

• Q00
• Les sockets de type flux :
  • exploration brève du modèle de programmation
  • examen rapide des distinctions entre le modèle BSD de base, qui est universel, et certaines implémentations OO construites par-dessus
  • réflexion sur les limites de ce qui peut être transigé entre deux homologues situés dans des espaces adressables distincts
  • réflexion aussi sur les distinctions structurelles entre les architectures matérielles, en particulier en ce qui a trait à la structure interne des entiers

Dans les notes de cours :

• Les sockets de type flux sont décrits dans CPA – Volume 02, pp. ≈6-36

Vendredi 26 janvier AM

S03

Au menu, activité pratique :

• En équipe de deux personnes, implémentez un système client/ serveur où le serveur peut gérer plusieurs clients de manière concurrente
• Le client devra envoyer au serveur un nom de fichier (vous devez supporter à la fois les fichiers « texte » et « binaires »). Le nom peut inclure un chemin (p. ex. : "c:\machin\truc\yo man.jpeg" ou "../projet.sln"), et les répertoires relatifs seront considérés sur la base du répertoire de travail du serveur
• Le serveur devra consommer ce nom, puis transférer le contenu du fichier en question au client
• Le client devra consommer le contenu du fichier, et écrire ce fichier dans son propre répertoire de travail (excluant le chemin s'il y a lieu)
• On doit pouvoir vérifier que le fichier reçu et écrit sur le poste du client est identique au fichier d'origine (ça peut être aussi simple que de l'ouvrir )
• Présentez à votre chic prof le code source du client et du serveur pour rétroaction sur le code (on peut faire cela en classe si vous le souhaitez)

Je serai avec vous, en soutien. L'idée ici est de s'assurer que vous êtes en mesure de bien gérer plusieurs séances concurrentes de transfert de fichiers, que vous gérez adéquatement les ressources associées à ces transactions, et que vous êtes familiarisés avec les sockets de type flux.

Mardi 30 janvier PM

S04

Au menu :

• Q01
• Les sockets de type datagramme :
  • comparaison avec les sockets de type flux
  • différences protocolaires
  • combiner struct et union (les union étiquetés)
  • portabilité des données
• Considérations de sérialisation (texte)

#define NOMINMAX // car windows.h, inclus « par la bande », et 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));
}

Dans les notes de cours :

• Les sockets de type datagramme sont décrits dans CPA – Volume 02, pp. ≈61-70
• La sérialisation est discutée en détail dans CPA – Volume 03, pp. ≈10-46

Vendredi 2 février AM

S05

Au menu :

• Considérations de sérialisation (brute)
• Petit contact avec enable_if
• Q02 et Q03 (oui, oui!)
  • les consignes sont disponibles ici : CPA--Q02-Q03.pdf
• Rappel de considérations d'alignement en mémoire
• Présentation des impacts de l'antémémoire (de la Cache) sur l'exécution des programmes, à partir de diapositives de Scott Meyers
  • voir https://www.youtube.com/watch?v=WDIkqP4JbkE pour une présentation par Scott Meyers lui-même, qui a depuis pris sa retraite, et
  • voir http://www.aristeia.com/TalkNotes/ACCU2011_CPUCaches.pdf pour les diapos

Mardi 6 février PM

S06

Au menu :

• Q04
• 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

Mardi 20 février PM

S07

Au menu :

• Implémenter un pointeur intelligent « maison » avec sémantique de duplication (clonage pour les clonables, copie pour les autres)
• Sémantiques d'accès :
  • sémantique de responsabilité unique
  • sémantique de duplication
  • sémantique de référence
  • etc.
• D'autres pointeurs intelligents, simples et utiles :
  • non_null_ptr<T>
  • observer_ptr<T>
• Effacement de types, à travers la classe peu_importe (bref retour, et technique alternative)
• Survol de std::variant et de std::visit()
  • pour ce type, nous nous sommes limités à de l'utilisation, n'allant pas jusqu'à l'implémentation

Vendredi 23 février AM

S08

Au menu :

• Q05
• Pointeur sur n'importe quoi, à travers une classe any_ptr
• Discussion sur les délégués : comment les implémenter, à quoi ça sert, ce genre de truc. Votre chic prof a écrit un petit exemple simple, et un autre qui n'a pas recours à l'allocation dynamique de mémoire, mais rend hommage à Patrick Boutot qui en a fait un art et a développé la pédagogie de la chose
• Un type maybe<T>

template <class R, class A>
   class delegue {
      struct Appelable {
         virtual R appeler(A) const = 0;
         virtual ~Appelable() = default;
         virtual Appelable *cloner() const = 0;
      };
      Appelable *p;
      struct PtrFonction : Appelable {
         R(*pf)(A);
         PtrFonction(R(*pf)(A)) noexcept : pf{ pf } {
         }
         R appeler(A arg)  const override{
            return pf(arg);
         }
         PtrFonction *cloner() const override {
            return new PtrFonction{ *this };
         }
      };
      template <class T>
         struct PtrMethode : Appelable {
            R(T::*pm)(A) const;
            T obj;
            PtrMethode(T obj, R(T::*pm)(A) const) : obj{ obj }, pm{ pm } {
            }
            R appeler(A arg) const override {
               return (obj.*pm)(arg);
            }
            PtrMethode *cloner() const override {
               return new PtrMethode{ *this };
            }
         };
      template <class F>
         struct Foncteur : Appelable {
            F obj;
            Foncteur(F obj) : obj{ obj } {
            }
            R appeler(A arg) const override {
               return obj(arg);
            }
            Foncteur *cloner() const override {
               return new Foncteur{ *this };
            }
         };
   public:
      delegue() noexcept : p{} {
      }
      bool empty() const noexcept {
         return !p;
      }
      delegue(R(*pf)(A)) : p{ new PtrFonction{ pf } } {
      }
      template <class T>
         delegue(T obj, R(T::*pm)(A) const) : p{ new PtrMethode<T>{ obj, pm } } {
         }
      template <class F>
         delegue(F f) : p{ new Foncteur<F>{ f } } {
         }
      ~delegue() {
         delete p;
      }
      delegue(const delegue &autre) : p{ autre.p ? autre.p->cloner() : nullptr } {
      }
      void swap(delegue &autre) {
         using std::swap;
         swap(p, autre.p);
      }
      delegue& operator=(const delegue &autre) {
         delegue{ autre }.swap(*this);
         return *this;
      }
      R operator()(A arg) const {
         return p->appeler(arg);
      }
   };

int f(double x) {
   return static_cast<int>(x);
}
struct F {
   int operator()(double x) const {
      return static_cast<int>(x * 2);
   }
};
struct Obj {
   int meth(double x) const {
      return static_cast<int>(-x);
   }
};

#include <iostream>
using namespace std;
int main() {
   delegue<int, double> del = f;
   cout << del(3.5) << endl; // 3
   del = F{};
   cout << del(3.5) << endl; // 7
   Obj obj;
   del = delegue<int, double>{ obj, &Obj::meth };
   cout << del(3.5) << endl; // -3
}

Mardi 27 février PM

S09

Au menu :

• Q06
• Comprendre le type std::tuple
• Facettes
• 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>
struct Texture {
   const char *getTextureName() const noexcept {
      return "Je suis un nom de texture";
   }
};
struct TextureManager {
   Texture getTexture() const noexcept {
      return {};
   }
};
struct Sound {
   const char *getFileName() const noexcept {
      return "SomeSound.wav";
   }
};
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

Mardi 6 mars PM

S10

Au menu :

• Q07
• Diverses techniques d'optimisation, incluant la tristement (!) célèbre Duff's Device
• Quelques considérations architecturales globales, dont :
  • un regroupement de threads

Vendredi 9 mars AM

S11

Mardi 10 avril PM

s/o

Séance déplacée au 12 avril à 18 h 30 pour profiter d'un conférencier spécial

Jeudi 12 avril PM (18 h 30)

S12

Mardi 17 avril PM

S13

Cliquez sur cette cible pour obtenir le code de la chaîne pascal simplifiée

Cliquez sur cette cible pour obtenir le code de la chaîne pascal avec itérateurs

Cliquez sur cette cible pour obtenir le code du test 0.0

Cliquez sur cette cible pour obtenir le code du test 0.0b

Cliquez sur cette cible pour obtenir le code du test 0.1

Cliquez sur cette cible pour obtenir le code du test 1.0

Cliquez sur cette cible pour obtenir le code du test 1.1

Cliquez sur cette cible pour obtenir le code du test 1.2

Cliquez sur cette cible pour obtenir le code du test 1.3

Cliquez sur cette cible pour obtenir le code du test 2.0

Cliquez sur cette cible pour obtenir le code du test 2.1

Cliquez sur cette cible pour obtenir le code du test 2.2

Cliquez sur cette cible pour obtenir le code du test 3.0

Cliquez sur cette cible pour obtenir le code du cas 0

Cliquez sur cette cible pour obtenir le code du cas 1

Cliquez sur cette cible pour obtenir le code du cas 2

Cliquez sur cette cible pour obtenir le code du cas 3

Cliquez sur cette cible pour obtenir le code du cas 4

Cliquez ici pour le projet contenant le code du client multiprogrammé de conversation, format « vanille ».

Cliquez ici pour le projet contenant le code du serveur multiprogrammé conversation « vanille ».

Cliquez ici pour le projet contenant le code du client multiprogrammé de conversation, format « objets autonomes ».

Cliquez ici pour le projet contenant le code du serveur multiprogrammé conversation « objets autonomes ».

Cliquez sur cette cible pour obtenir le code source de la classe pattern_iterator, document CPA – Volume 02 (ou encore cet article).

Cliquez sur cette cible pour obtenir le code à optimiser pour EX00, série 04, document CPA – Volume 03.

Cliquez sur cette cible pour obtenir le code complet de l'automate déterministe à états finis, version 00, tel qu'il apparaît dans le document CPA – Volume 04.

Cliquez sur cette cible pour obtenir le code complet de l'automate déterministe à états finis, version 01, tel qu'il apparaît dans le document CPA – Volume 04.

Cliquez sur cette cible pour obtenir le code complet de l'automate déterministe à états finis, version 02, tel qu'il apparaît dans le document CPA – Volume 04.

Cliquez sur cette cible pour obtenir le code complet de l'automate déterministe à états finis, version 03, tel qu'il apparaît dans le document CPA – Volume 04.

Cliquez sur cette cible pour obtenir le code complet de l'automate déterministe à états finis, version 04, tel qu'il apparaît dans le document CPA – Volume 04.

Cliquez sur cette cible pour obtenir le code complet de l'automate déterministe à états finis, version 05, tel qu'il apparaît dans le document CPA – Volume 04.

Cliquez sur cette cible pour obtenir le code complet de l'automate déterministe à états finis, version 06, tel qu'il apparaît dans le document CPA – Volume 04.

Cliquez sur cette cible pour obtenir le code complet du sélecteur de conversions, tel qu'il apparaît dans le document CPA – Volume 04.

Cliquez sur cette cible pour aller au document portant sur les classes imbriquées.

Cliquez sur cette cible pour aller au document portant sur les templates.

Cliquez sur cette cible pour aller au document portant sur les singletons.

Cliquez sur cette cible pour aller au document portant sur les mutex portables .

Cliquez sur cette cible pour aller au document portant sur les autoverrous.

Cliquez sur cette cible pour aller au document portant sur les objets autonomes.

Cliquez sur cette cible pour aller au document portant sur les méthodes volatiles.

Cliquez sur cette cible pour aller au document portant sur la conversion automatique entre référentiels.