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 – vendredi 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, et qui croît en richesse avec chaque version du langage, 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 :

  • Lit le contenu d'un fichier texte contenant du code source C++ (vous n'avez pas à le valider)
  • Remplace certains caractères (plus précisément : &, < et >) par des métacaractères HTML (respectivement : &amp;, &lt; et &gt;)
  • Colorie les mots clés C++ (on procédera de manière naïve ici) en utilisant des balises <span>, et
  • 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() {
         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);
   //}
}

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

Au menu :

  • Q00

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)? En fait, 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, tout comme il est possible qu'une entreprise de développement de jeu fasse le choix conscient de préférer passer directement pas les services du système d'exploitation. 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 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

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

Au menu :

  • À venir

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

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

  

S04 – vendredi 27 février 9 h-12 h

  

S05 – mercredi 4 mars 9 h-12 h

  

S06 – vendredi 6 mars 9 h-12 h

  

S07 – mercredi 11 mars 13 h-16 h

  

Les semaines du 16, du 23 et du 30 mars, notre cours fait relâche. Bon travail sur votre projet, les ami(e)s!

S08 – vendredi 10 avril 9 h-12 h

  

S09 – vendredi 17 avril 9 h-12 h

Chic examen final!

Consignes des livrables

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

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 3 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).

Vous pouvez me remettre ce livrable au plus tard à la séance S05 (ce qui nous amène après votre présentation de projet devant public), par courriel à Patrice.Roy@USherbrooke.ca

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 3 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 !