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 16 janvier 9 h-12 h

Au menu :

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.

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.

S01 – vendredi 25 janvier 1er février 9 h-12 h

Au menu, une petite activité :

  • Écrivez un programme 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 <future>
#include <chrono>
#include <vector>
#include <algorithm>
#include <random>
#include <numeric>
#include <iostream>
using namespace std;
using namespace std::chrono;
enum class Case : char {
   Vide, Heros, Vilain, Bestiole, Mur
};
int main() {
   enum {
      MAP_HEIGHT = 25'000,
      MAP_WIDTH = MAP_HEIGHT,
      MAP_SIZE = MAP_HEIGHT * MAP_WIDTH
   };
   // créer la carte
   cout << "Creation de la carte (total de " << MAP_SIZE << " cases vides)" << endl;
   vector<Case> map{ MAP_SIZE, Case::Vide };
   {
      auto avant = system_clock::now();
      enum { PROB_NON_VIDE = 15 };
      cout << "Initialisation de la carte; environ " << PROB_NON_VIDE << "% de cases non-vides" << endl;
      uniform_int_distribution<int> d100{ 1, 100 };
      uniform_int_distribution<int> d4{ 1, 4 };
      mt19937 prng{ random_device{}() };
      generate(begin(map), end(map), [&] {
         return d100(prng) <= PROB_NON_VIDE ? static_cast<Case>(d4(prng)) : Case::Vide;
      });
      auto apres = system_clock::now();
      cout << "Temps requis pour creer la carte : " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
   }
   // lancer l'analyse
   {
      cout << "Detection du nombre de threads materiels... " << flush;
      auto nthreads = thread::hardware_concurrency();
      cout << nthreads << " trouves" << endl;
      const auto span_size = MAP_SIZE / nthreads;
      cout << "Traitement parallele de blocs de " << span_size << " cases" << endl;
      auto avant = system_clock::now();
      vector<future<unsigned int>> v;
      v.reserve(nthreads - 1);
      for (decltype(nthreads) i = 0; i < nthreads - 1; ++i)
         v.emplace_back(async([&, i] {
            auto pos_debut = i * span_size;
            auto pos_fin = pos_debut + span_size;
            return count_if(begin(map) + pos_debut, begin(map) + pos_fin, [](const Case &c) {
               return c == Case::Vilain || c == Case::Bestiole;
            });
         }));
      auto pos_debut = (nthreads - 1) * span_size;
      auto pos_fin = map.size();
      auto nb_pas_fins = count_if(begin(map) + pos_debut, begin(map) + pos_fin, [](const Case &c) {
         return c == Case::Vilain || c == Case::Bestiole;
      });
      cout << "Collecte des resultats..." << flush;
      nb_pas_fins = accumulate(begin(v), end(v), nb_pas_fins,
         [](unsigned int so_far, future<unsigned int> &f) {
            return so_far + f.get();
         }
      );
      auto apres = system_clock::now();
      cout << " complete en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
      cout << "Nb de pas fins: " << nb_pas_fins << endl;
   }
   {
      cout << "Traitement sequentiel de " << map.size() << " cases..." << flush;
      auto avant = system_clock::now();
      auto nb_pas_fins = count_if(begin(map), end(map), [](const Case &c) {
         return c == Case::Vilain || c == Case::Bestiole;
      });
      auto apres = system_clock::now();
      cout << " complete en " << duration_cast<milliseconds>(apres - avant).count() << " ms." << endl;
      cout << "Nb de pas fins: " << nb_pas_fins << endl;
   }
}

Par la suite :

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 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 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] = tester([&] {
      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]  = tester([&] {
      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] = tester([&] {
      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 1er février 9 h-12 h 13 h-16 h

Au menu :

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 », 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 :

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

S03 – mercredi 6 février 9 h-12 h

Au menu :

  • 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

Si le temps le permet :

N'oubliez pas de remettre Q00/Q01 au plus tard à 23 h 59 ce soir, en respectant les consignes!

Les semaines du 11, du 18 et du 25 février, notre cours fait relâche. Bon travail sur votre projet, les amis!

Notez que la semaine du 18 février en particulier, je serai à la rencontre du WG21 à Kona. Vous pouvez suivre mes aventures sur ../../Sujets/Orthogonal/wg21-2019-Kona.html

S04 – mercredi 6 mars 9 h-12 h

Au menu :

  • Q02
  • Q03
  • Rapport (informel) de voyage
    • acceptés (les gros morceaux)
    • (acceptés auparavant)
      • span
      • concepts
      • ranges
      • operator<=>()
      • consteval
      • is_constant_evaluated()
      • constexpr union
      • constexpr try... catch
      • constexpr dynamic_cast
    • (pas encore accepté, mais probablement à Cologne)
      • for...
      • std::format()
      • allocation constexpr
      • vector constexpr (enjeu multiniveau)
      • constexpr dans <cmath>
      • constinit
      • using enum
      • création implicite d'objets à bas niveau
  • Effacement de types (suite), à travers la classe peu_importe (bref retour, et technique alternative)
  • 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

Le plan de cours prévoyait une remise de L00... mais je ne vous ai pas encore donné les consignes, alors je vous reviens à ce sujet.

S05 – vendredi 15 mars 9 h-12 h

Au menu :

  • Un type maybe<T>
    • parenthèse sur std::launder()
  • 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
  • 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

S06 – vendredi 22 mars 9 h-12 h

Au menu :

S07 – mercredi 27 mars 9 h-12 h

Au menu :

  • Q04
  • Q05
  • AoS ou SoA
    • ce que ça signifie
    • conséquences
  • SSO et SOO
    • ce que ça signifie
    • implémentations possibles
    • discussion des enjeux
  • Algorithmes Cache-Oblivious (survol)
  • Algorithmes Data-Invariant (survol)
  • Bitfields (survol)

Grosse nouvelle pour nous ce matin : Yoshua Bengio vient de remporter le Turing Award de 2018! Immenses bravos!

Les semaines du 5, du 12 et du 19 avril, notre cours fait relâche. Bon travail sur votre projet, les amis!

S08 – mercredi 24 avril 9 h-12 h

Votre chic prof a été totalement distrait et a oublié cette séance. C'est ma faute! Pour cette raison, la séance S09 sera une séance de cours régulière, et l'examen final se fera à la maison plutôt qu'en classe.

Je suis sincèrement désolé!

S09 – vendredi 3 mai 13 h-16 h

Au menu :

  • Priorité à vos questions
  • Pour le reste, des tas de petits trucs :
    • profiter de CTAD (152-168; 184-191)
    • une boucle for avec plusieurs variables
    • if (incluant if constexpr) et switch en tant que portée
    • noexcept et signatures (239)
    • élision de copies (240-242)
    • allocation suralignée (243-245)
    • ordre d'évaluation des expressions (246-254)
    • template <auto> (255-258)
    • λ constexpr (259-262)
    • capture par valeur de *this (263-265)
    • void_t (315-317)
    • verrous partagés (319)
    • scoped_lock (320-322)
    • make_from_tuple() (323)
    • mini trucs (333+), en particulier 350-351 (cache et synchro), 365 (clamp(), éventuellement midpoint() et lerp())

Un chic examen final vous attend... à faire à la maison!

Remise de L01

Évidemment, faire L01 sans avoir les consignes au préalable est... ardu. J'ai écrit les consignes (que vous trouverez plus bas), et la date de remise ira après la présentation de votre projet.

   

Consignes des livrables

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

Livrable 00

L'idée de ce cours (et de son prédécesseur direct) est de servir de soutien aux autres cours; évidemment, certaines des techniques vues dans l'un ou l'autre de ces cours peut ne pas convenir à votre production de la session, mais il demeure que nous devons réfléchir, expérimenter, progresser... pour nous améliorer.

Pour cette raison, sur une base individuelle (note : cela signifie que, pour une équipe donnée, je m'attends à des techniques distinctes pour chaque participante et chaque participant), votre livrable 00 consistera en :

Livrable 01

Pour avoir l'esprit tranquille en cette première incarnation du cours INF709, et considérant le moment tardif (!) où ceci a été écrit, nous y irons pour quelque chose de léger : j'aimerais que vus produisiez, sur une base individuelle, un post-mortem sur L00, à savoir :

Ceci devrait ne prendre que quelques pages tout au plus, et vous permettra de faire un bref bilan de votre session sur le plan de la programmation. Vous pouvez me le remettre le 20 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 !