Université de Sherbrooke, régulier et DGL, STR

Vous trouverez ici quelques documents et quelques liens pouvant, je l'espère, vous être utiles. Vous pouvez aussi consulter, parmi les liens divers mis à votre disposition, ceux portant sur les STR, ceux portant sur la multiprogrammation et ceux portant sur l'optimisation.

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 sur la page où on trouve mon horaire.

Petit menu

IFT611/IFT729 INF749

Plan de cours

Plan de cours

Consignes quant au projet de session

Consignes quant au projet de session

Pour IFT611/IFT729, cours s'adressant aux étudiant(e)s de 2e cycle et de fin de 1er cycle, les frais d'impression de notes de cours ne sont pas facturés a priori. Je ne peux pas livrer ces notes de cours en format électronique, pour des raisons contractuelles.

Une procédure suivra pour celles et ceux qui souhaitent obtenir ces documents.

Au moment d'écrire ces lignes, ces notes de cours comprennent :

  • STR – Volume 00, v. 1,05, 77 pages, qui met en place terminologie et vocabulaire, et qui donne des exemples de code prenant en charge des tâches morcelables
  • STR – Volume 01, v. 1,985, 67 pages, qui discute brièvement de conteneurs, d'itérateurs, de tests de « performances », de mythes et de saisies du temps d'exécution
  • STR – Volume 02, v. 3,2, 323 pages, qui discute de multiprogrammation et de synchronisation
  • STR – Volume 03, v. 1,98, 177 pages, qui discute de micro-optimisation et de métaprogrammation

La demande va comme suit :

Qui Volume 00 Volume 01 Volume 02 Volume 03
         
         
         
         
         
         
         
         
         
         
         

 

Pour INF749, cours s'adressant aux étudiant(e)s de 2e cycle, les frais d'impression de notes de cours sont facturés a priori et vous seront livrés dans des cartables en classe.

 

Si vous cherchez des idées de projets, vous trouverez ici quelques exemples des projets qui ont été faits dans ce cours au fil du temps (liste non-exhaustive)

Sur ce site, vous trouverez :

Il arrive que j'aie en classe des étudiant(e)s qui ont déjà suivi des cours avec moi où l'on trouvait un besoin de multiprogrammation ou de programmation générique. Malheureusement, faute de préalables, je ne peux pas supposer que tous et toutes ont les bases nécessaires pour escamoter ces concepts, alors j'implore votre tolérance, surtout pour les deux ou trois premières séances, si vous rencontrez des éléments de matière qui sont, pour vous, du déjà vu.

À propos des séances en classe

Index des séances théoriques
IFT611/IFT729 S00 S01 S02 S03 S04 S05 S06 S07 S08 S09 S10 S11 S12 S13  
INF749 S00 S01 S02 S03 S04 S05 S06 S07 S08 S09 S10 S11 S12 S13 S14

Pendant les premières séances, nous examinerons surtout des concepts et techniques de base, qui seront réinvestis dans les exemples et les illustrations concrètes que proposera le professeur. Ce sont donc des séances plus près de la (saine) programmation au sens large que des STR de manière spécifique; j'espère que vous saurez voir les concepts propres aux STR même si la praxis sera présente dans notre discours.

D'autres approches sont possibles pour un cours de STR, évidemment, mais le choix pédagogique fait par votre chic prof de discuter à la fois de théorie et de pratique demande de mettre sur pied quelques bases au préalable. Je vous remercie de votre tolérance (et, si vous avez apprécié, alors tant mieux!).

Séance IFT611/IFT729 Contenu IFT611/IFT729 Séance INF749 Contenu INF749
S00 IFT611/IFT729, 9 janvier

Au menu :

  • Mise en place d'éléments de vocabulaire
  • Discussion sur la distinction importante entre programmes en temps réel et programmes rapides, du moins dans le cas des STR stricts, et sur les nuances dans le discours quant à la question même de l'idée de temps réel, qui porte plusieurs sens, affectant différemment les gens en fonction de leur domaine d'expertise et de leur milieu de travail. Le tout dans le but de situer les un(e)s et les autres quant au contenu du cours et quant au projet de session qui vous est proposé
  • Présentation du cours et des approches choisies pour y traiter des sujets qui nous y tiennent à coeur
  • Bref tableau de façons de faire que nous utiliserons dans les exemples proposés en classe et dans les notes de cours. Ceci inclut des exemples utilisant entre autres des foncteurs, de la généricité par des templates, un algorithme standard (for_each()) et, pour le plaisir, une λ-expressions
  • Bref comparatif de programmes bloquant et non-bloquant
  • Bref comparatif de programmes avec tâche s'exécutant à rythme régulier et à rythme constant

Petit complément : j'ai rédigé un petit comparatif de « performances » pour certaines opérations types applicables à un tableau brut, alloué dynamiquement, et à un vecteur standard. Je ne l'ai pas indiqué en classe encore, mais il s'avère que, lorsqu'il est bien utilisé, le vecteur est presque toujours aussi rapide – ou plus rapide! – que son substrat, le tableau brut, parce que le code sous-jacent est extrêmement sophistiqué et parce que nous, programmeurs de tous les jours, ne prenons pas chaque fois le soin de manipuler nos tableaux comme le font en tout temps les concepteurs du vecteur standard.

Le dire, bien sûr, c'est une chose, mais le démontrer, c'est mieux, alors l'exemple vous attend ici si vous êtes intéressé(e).

Dans les notes de cours, vous trouverez de la matière en lien avec cette séance dans STR – Volume 00 (vocabulaire, donc les pages ≈5..35).

Truc important : bien que je ne l'aie pas mentionné explicitement pendant la séance, ce cours mettra l'accent sur plusieurs facettes de la conception et du développement de STR, dont :

  • Le respect en tout temps des contraintes fixées a priori.. Nous en avons discuté quelque peu en classe (itérer à rythme régulier ou constant, s'exécuter de manière brève, démarrer immédiatement – faible latence)
  • La résilience. Un STR étant fréquemment un système dont dépend l'intégrité des gens et du matériel, sa résilience tend à être une caractéristique plus que souhaitable
  • La concision. étant souvent destinés à opérer des systèmes embarqués ou à s'exécuter sur du matériel plus... humble, mais aux caractéristiques d'exécution plus prévisibles que ne le sont celles du matériel très sophistiqué mis à notre disposition aujourd'hui, il n'est pas rare qu'un STR doive occuper un espace réduit en mémoire

Ne vous étonnez donc pas de voir ces thématiques apparaître de manière récurrente dans notre discours.

S00 INF749, 10 janvier

Notez que c'est aujourd'hui l'anniversaire de Donald E. Knuth

Au menu :

  • Mise en place d'éléments de vocabulaire
  • Discussion sur la distinction importante entre programmes en temps réel et programmes rapides, du moins dans le cas des STR stricts, et sur les nuances dans le discours quant à la question même de l'idée de temps réel, qui porte plusieurs sens, affectant différemment les gens en fonction de leur domaine d'expertise et de leur milieu de travail. Le tout dans le but de situer les un(e)s et les autres quant au contenu du cours et quant au projet de session qui vous est proposé
  • Présentation du cours et des approches choisies pour y traiter des sujets qui nous y tiennent à coeur
  • Bref tableau de façons de faire que nous utiliserons dans les exemples proposés en classe et dans les notes de cours. Ceci inclut des exemples utilisant entre autres des foncteurs, de la généricité par des templates, un algorithme standard (for_each()) et, pour le plaisir, une λ-expressions
  • Bref comparatif de programmes bloquant et non-bloquant
  • Bref comparatif de programmes avec tâche s'exécutant à rythme régulier et à rythme constant

Petit complément : j'ai rédigé un petit comparatif de « performances » pour certaines opérations types applicables à un tableau brut, alloué dynamiquement, et à un vecteur standard. Je ne l'ai pas indiqué en classe encore, mais il s'avère que, lorsqu'il est bien utilisé, le vecteur est presque toujours aussi rapide – ou plus rapide! – que son substrat, le tableau brut, parce que le code sous-jacent est extrêmement sophistiqué et parce que nous, programmeurs de tous les jours, ne prenons pas chaque fois le soin de manipuler nos tableaux comme le font en tout temps les concepteurs du vecteur standard.

Le dire, bien sûr, c'est une chose, mais le démontrer, c'est mieux, alors l'exemple vous attend ici si vous êtes intéressé(e).

Dans les notes de cours, vous trouverez de la matière en lien avec cette séance dans STR – Volume 00 (vocabulaire, donc les pages ≈5..35).

Truc important : bien que je ne l'aie pas mentionné explicitement pendant la séance, ce cours mettra l'accent sur plusieurs facettes de la conception et du développement de STR, dont :

  • Le respect en tout temps des contraintes fixées a priori.. Nous en avons discuté quelque peu en classe (itérer à rythme régulier ou constant, s'exécuter de manière brève, démarrer immédiatement – faible latence)
  • La résilience. Un STR étant fréquemment un système dont dépend l'intégrité des gens et du matériel, sa résilience tend à être une caractéristique plus que souhaitable
  • La concision. étant souvent destinés à opérer des systèmes embarqués ou à s'exécuter sur du matériel plus... humble, mais aux caractéristiques d'exécution plus prévisibles que ne le sont celles du matériel très sophistiqué mis à notre disposition aujourd'hui, il n'est pas rare qu'un STR doive occuper un espace réduit en mémoire

Ne vous étonnez donc pas de voir ces thématiques apparaître de manière récurrente dans notre discours.

S01 IFT611/IFT729, 16 janvier

Au menu, d'une manière teintée par notre besoin d'avoir une approche appropriée pour le développement de STR :

Mise en place d'un premier conteneur (un tableau d'entiers) implémenté selon les conventions du langage C++, en portant une attention particulière aux considérations de robustesse et d'efficacité, incluant :

  • Quelques types internes et publics
  • Quelques méthodes clés (size(), empty(), capacity())
  • Les accès aux itérateurs (begin() et end(), en déclinaison const et non-const; cbegin() et cend())
  • Quelques constructeurs (défaut, paramétrique, copie, mouvement)
  • L'affectation (de copie, de mouvement)
  • Le destructeur

Munis des idées et techniques mises de l'avant dans cette séance, vous devriez être en mesure de comprendre les exemples dans STR – Volume 01 (voir le code des cas sous étude). Profitez de l'opportunité pour expérimenter avec ces propositions de tests, pour les modifier, pour essayer de comprendre les métriques que vous parviendrez à en tirer, etc.

Le code utilisé pour la classe Tableau, de même que le test qui met en relief l'impact du mouvement sur la vitesse du programme, suit :

#include <cstddef>
#include <algorithm>

class Tableau {
public:
   using value_type = int;
   using size_type = std::size_t;
private:
   value_type *elems;
   size_type nelems,
             cap;
public:
   size_type size() const noexcept {
      return nelems;
   }
   size_type capacity() const noexcept {
      return cap;
   }
   bool empty() const noexcept {
      return !size();
   }
private:
   bool full() const noexcept {
      return size() == capacity();
   }
public:
   using iterator = value_type*;
   using const_iterator = const value_type*;
   iterator begin() noexcept {
      return elems;
   }
   const_iterator begin() const noexcept {
      return elems;
   }
   const_iterator cbegin() const noexcept {
      return elems;
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return begin() + size();
   }
   Tableau() noexcept : elems{}, nelems {}, cap{} {
   }
   Tableau(size_type n, const value_type &init)
      : cap{ n }, nelems{ n }, elems{ new value_type[n] } {
      std::fill(begin(), end(), init);
   }
   Tableau(const Tableau &autre)
      : elems{ new value_type[autre.size()] },
        nelems{ autre.size() }, cap{ autre.size() } {
      std::copy(autre.begin(), autre.end(), begin());
   }
   ~Tableau() {
      delete [] elems;
   }
   void swap(Tableau &autre) noexcept {
      using std::swap;
      swap(elems, autre.elems);
      swap(nelems, autre.nelems);
      swap(cap, autre.cap);
   }
   Tableau& operator=(const Tableau &autre) {
      Tableau{ autre }.swap(*this);
      return *this;
   }
   value_type& operator[](size_type n) noexcept {
      return elems[n];
   }
   const value_type& operator[](size_type n) const noexcept {
      return elems[n];
   }
   void push_back(const value_type &val) {
      if (full()) grow();
      elems[size()] = val;
      ++nelems;
   }
private:
   void grow() {
      const size_type new_cap = capacity()? capacity() * 2 : 42; // hum
      auto p = new value_type[new_cap];
      std::copy(begin(), end(), p);
      delete[]elems;
      cap = new_cap;
      elems = p;
   }
public:
   bool operator==(const Tableau &autre) const noexcept {
      return size() == autre.size() &&
             std::equal(begin(), end(), autre.begin());
   }
   bool operator!=(const Tableau &autre) const noexcept {
      return !(*this == autre);
   }
   Tableau(Tableau &&autre) noexcept
      : elems{ autre.elems }, nelems{ autre.nelems }, cap{ autre.cap } {
      autre.elems = {};
      autre.nelems = {};
      autre.cap = {};
   }
   Tableau& operator=(Tableau &&autre) noexcept {
      delete[] elems;
      elems = autre.elems;
      nelems = autre.nelems;
      cap = autre.cap;
      autre.elems = {};
      autre.nelems = {};
      autre.cap = {};
      return *this;
   }
};


#include <vector>
#include <numeric>
#include <chrono>
#include <iostream>
using namespace std;
using namespace std::chrono;

vector<double> f(vector<double> v) {
   transform(begin(v), end(v), begin(v), [](double x) { return sqrt(x); });
   return v;
}

int main() {
   enum { N = 50'000'000 };
   vector<double> v(N);
   iota(begin(v), end(v), 1.0);
   {
      auto w = v;
      auto pre = high_resolution_clock::now();
      w = f(w);
      auto post = high_resolution_clock::now();
      cout << "Ecoule : " << duration_cast<microseconds>(post - pre).count()
           << " us." << endl;
   }
   {
      auto w = v;
      auto pre = high_resolution_clock::now();
      w = f(std::move(w));
      auto post = high_resolution_clock::now();
      cout << "Ecoule : " << duration_cast<microseconds>(post - pre).count()
           << " us." << endl;
   }
}

Dans les notes de cours, comme mentionné dans le paragraphe précédent, vous trouverez de la matière en lien avec cette séance dans STR – Volume 01.

Complément culturel : même les compilateurs ont des bogues (quoiqu'ils en aient sans doute moins que vous ne le croyez parfois). Pour en savoir plus sur un bogue du compilateur sous-jacent à Visual Studio, décrit (avec sa solution) par Stephan T. Lavavej, voir http://channel9.msdn.com/Series/C9-Lectures-Stephan-T-Lavavej-Core-C- (en particulier la partie de ).

S01 INF749, 17 janvier

Au menu, d'une manière teintée par notre besoin d'avoir une approche appropriée pour le développement de STR :

Mise en place d'un premier conteneur (un tableau d'entiers) implémenté selon les conventions du langage C++, en portant une attention particulière aux considérations de robustesse et d'efficacité, incluant :

  • Quelques types internes et publics
  • Quelques méthodes clés (size(), empty(), capacity())
  • Les accès aux itérateurs (begin() et end(), en déclinaison const et non-const; cbegin() et cend())
  • Quelques constructeurs (défaut, paramétrique, copie, mouvement)
  • L'affectation (de copie, de mouvement)
  • Le destructeur

Munis des idées et techniques mises de l'avant dans cette séance, vous devriez être en mesure de comprendre les exemples dans STR – Volume 01 (voir le code des cas sous étude). Profitez de l'opportunité pour expérimenter avec ces propositions de tests, pour les modifier, pour essayer de comprendre les métriques que vous parviendrez à en tirer, etc.

Le code utilisé pour la classe Tableau, de même que le test qui met en relief l'impact du mouvement sur la vitesse du programme, suit :

#include <cstddef>
#include <algorithm>

class Tableau {
public:
   using value_type = int;
   using size_type = std::size_t;
private:
   value_type *elems;
   size_type nelems,
             cap;
public:
   size_type size() const noexcept {
      return nelems;
   }
   size_type capacity() const noexcept {
      return cap;
   }
   bool empty() const noexcept {
      return !size();
   }
private:
   bool full() const noexcept {
      return size() == capacity();
   }
public:
   using iterator = value_type*;
   using const_iterator = const value_type*;
   iterator begin() noexcept {
      return elems;
   }
   const_iterator begin() const noexcept {
      return elems;
   }
   const_iterator cbegin() const noexcept {
      return elems;
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return begin() + size();
   }
   Tableau() noexcept : elems{}, nelems {}, cap{} {
   }
   Tableau(size_type n, const value_type &init)
      : cap{ n }, nelems{ n }, elems{ new value_type[n] } {
      std::fill(begin(), end(), init);
   }
   Tableau(const Tableau &autre)
      : elems{ new value_type[autre.size()] },
        nelems{ autre.size() }, cap{ autre.size() } {
      std::copy(autre.begin(), autre.end(), begin());
   }
   ~Tableau() {
      delete [] elems;
   }
   void swap(Tableau &autre) noexcept {
      using std::swap;
      swap(elems, autre.elems);
      swap(nelems, autre.nelems);
      swap(cap, autre.cap);
   }
   Tableau& operator=(const Tableau &autre) {
      Tableau{ autre }.swap(*this);
      return *this;
   }
   value_type& operator[](size_type n) noexcept {
      return elems[n];
   }
   const value_type& operator[](size_type n) const noexcept {
      return elems[n];
   }
   void push_back(const value_type &val) {
      if (full()) grow();
      elems[size()] = val;
      ++nelems;
   }
private:
   void grow() {
      const size_type new_cap = capacity()? capacity() * 2 : 42; // hum
      auto p = new value_type[new_cap];
      std::copy(begin(), end(), p);
      delete[]elems;
      cap = new_cap;
      elems = p;
   }
public:
   bool operator==(const Tableau &autre) const noexcept {
      return size() == autre.size() &&
             std::equal(begin(), end(), autre.begin());
   }
   bool operator!=(const Tableau &autre) const noexcept {
      return !(*this == autre);
   }
   Tableau(Tableau &&autre) noexcept
      : elems{ autre.elems }, nelems{ autre.nelems }, cap{ autre.cap } {
      autre.elems = {};
      autre.nelems = {};
      autre.cap = {};
   }
   Tableau& operator=(Tableau &&autre) noexcept {
      delete[] elems;
      elems = autre.elems;
      nelems = autre.nelems;
      cap = autre.cap;
      autre.elems = {};
      autre.nelems = {};
      autre.cap = {};
      return *this;
   }
};


#include <vector>
#include <numeric>
#include <chrono>
#include <iostream>
using namespace std;
using namespace std::chrono;

vector<double> f(vector<double> v) {
   transform(begin(v), end(v), begin(v), [](double x) { return sqrt(x); });
   return v;
}

int main() {
   enum { N = 50'000'000 };
   vector<double> v(N);
   iota(begin(v), end(v), 1.0);
   {
      auto w = v;
      auto pre = high_resolution_clock::now();
      w = f(w);
      auto post = high_resolution_clock::now();
      cout << "Ecoule : " << duration_cast<microseconds>(post - pre).count()
           << " us." << endl;
   }
   {
      auto w = v;
      auto pre = high_resolution_clock::now();
      w = f(std::move(w));
      auto post = high_resolution_clock::now();
      cout << "Ecoule : " << duration_cast<microseconds>(post - pre).count()
           << " us." << endl;
   }
}

Dans les notes de cours, comme mentionné dans le paragraphe précédent, vous trouverez de la matière en lien avec cette séance dans STR – Volume 01.

Complément culturel : même les compilateurs ont des bogues (quoiqu'ils en aient sans doute moins que vous ne le croyez parfois). Pour en savoir plus sur un bogue du compilateur sous-jacent à Visual Studio, décrit (avec sa solution) par Stephan T. Lavavej, voir http://channel9.msdn.com/Series/C9-Lectures-Stephan-T-Lavavej-Core-C- (en particulier la partie de ).

S02 – IFT611/IFT729, 23 janvier

Au menu :

  • Q00
  • Compléter l'implémentation du tableau d'entiers débuté à S01 :
    • méthode push_back() et implémentation d'un algorithme de croissance

Notez que notre examen d'implémentations génériques d'un tableau suivra sous peu; nous avons quelques menus détails à explorer auparavant.

  • Survol rapide des traits
  • Petite excursion dans le monde des itérateurs : catégories, opérations, forces, faiblesses, usages
  • Poursuite de l'examen des itérateurs, en lien avec la fonction distance()
  • L'exemple amusant d'un trait est_convertible
  • Poursuite de l'examen des itérateurs, en lien avec le calcul de la moyenne

La fonction distance() est un cas d'espèce intéressant, tiré du standard lui-même, qui exploite les traits et les catégories pour réaliser une optimisation presque obscène. J'aime bien faire le tour de cette approche, qui peut être appliquée à bien d'autres trucs, avec des gens qui, comme vous, doivent écrire des programmes dont les performances sont sans compromis.

Les plus curieuses et les plus curieux remarqueront que les fonctions advance(), next() et prev() appliquent les mêmes techniques d'optimisation que sa cousine distance().

Dans les notes de cours, vous trouverez de la matière en lien avec cette séance dans STR – Volume 00, annexes 00 et 01, mais vous en trouverez surtout dans les liens ci-dessus.

S02 INF749, 24 janvier

Au menu :

  • Q00
  • Compléter l'implémentation du tableau d'entiers débuté à S01 :
    • méthode push_back() et implémentation d'un algorithme de croissance

Notez que notre examen d'implémentations génériques d'un tableau suivra sous peu; nous avons quelques menus détails à explorer auparavant.

La fonction distance() est un cas d'espèce intéressant, tiré du standard lui-même, qui exploite les traits et les catégories pour réaliser une optimisation presque obscène. J'aime bien faire le tour de cette approche, qui peut être appliquée à bien d'autres trucs, avec des gens qui, comme vous, doivent écrire des programmes dont les performances sont sans compromis.

Les plus curieuses et les plus curieux remarqueront que les fonctions advance(), next() et prev() appliquent les mêmes techniques d'optimisation que sa cousine distance().

Dans les notes de cours, vous trouverez de la matière en lien avec cette séance dans STR – Volume 00, annexes 00 et 01, mais vous en trouverez surtout dans les liens ci-dessus.

S03 – IFT611/IFT729, 30 janvier

Au menu :

Pour le code du tableau générique tel que vu en classe, voici :

#include <cstddef>
#include <algorithm>
#include <initializer_list>
template <class T>
class Tableau {
public:
   using value_type = T;
   using size_type = std::size_t;
   using pointer = value_type*;
   using const_pointer = const value_type*;
   using reference = value_type&;
   using const_reference = const value_type&;
private:
   pointer elems;
   size_type nelems,
      cap;
public:
   size_type size() const noexcept {
      return nelems;
   }
   size_type capacity() const noexcept {
      return cap;
   }
   bool empty() const noexcept {
      return !size();
   }
private:
   bool full() const noexcept {
      return size() == capacity();
   }
public:
   using iterator = pointer;
   using const_iterator = const_pointer;
   iterator begin() noexcept {
      return elems;
   }
   const_iterator begin() const noexcept {
      return elems;
   }
   const_iterator cbegin() const noexcept {
      return elems;
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return begin() + size();
   }
   Tableau() noexcept : elems{}, nelems{}, cap{} {
   }
   Tableau(std::initializer_list<value_type> lst)
      : elems{ new value_type[lst.size()] },
      nelems{ lst.size() }, cap{ lst.size() } {
      try {
         std::copy(lst.begin(), lst.end(), begin());
      } catch(...) {
         delete[] elems;
         throw;
      }
   }
   Tableau(size_type n, const value_type &init)
      : cap{ n }, nelems{ n }, elems{ new value_type[n] } {
      try {
         std::fill(begin(), end(), init);
      } catch(...) {
         delete[] elems;
         throw;
      }
   }
   Tableau(const Tableau &autre)
      : elems{ new value_type[autre.size()] },
      nelems{ autre.size() }, cap{ autre.size() } {
      try {
         std::copy(autre.begin(), autre.end(), begin());
      } catch(...) {
         delete[] elems;
         throw;
      }
   }
   template <class It>
      Tableau(It debut, It fin)
         : nelems{ std::distance(debut, fin) } {
         cap = size();
         elems = new value_type[size()];
         try {
            std::copy(debut, fin, begin());
         } catch(...) {
            delete[] elems;
            throw;
         }
      }
   template <class U>
      Tableau(const Tableau<U> &autre)
         : cap{ autre.size() }, nelems{ autre.size() },
           elems{ new value_type[autre.size()] } {
         try {
            std::copy(autre.begin(), autre.end(), begin());
         } catch(...) {
            delete[] elems;
            throw;
         }
      }
   template <class U>
      Tableau& operator=(const Tableau<U> &autre) {
         Tableau{ autre }.swap(*this);
         return *this;
      }
   ~Tableau() {
      delete[] elems;
   }
   void swap(Tableau &autre) noexcept {
      using std::swap;
      swap(elems, autre.elems);
      swap(nelems, autre.nelems);
      swap(cap, autre.cap);
   }
   Tableau& operator=(const Tableau &autre) {
      Tableau{ autre }.swap(*this);
      return *this;
   }
   reference operator[](size_type n) noexcept {
      return elems[n];
   }
   const_reference operator[](size_type n) const noexcept {
      return elems[n];
   }
   void push_back(const_reference val) {
      if (full()) grow();
      elems[size()] = val;
      ++nelems;
   }
private:
   void grow() {
      const size_type new_cap = capacity() ? capacity() * 2 : 42; // hum
      auto p = new value_type[new_cap];
      try {
         std::copy(begin(), end(), p);
         delete[]elems;
         cap = new_cap;
         elems = p;
      } catch(...) {
         delete [] p;
         throw;
      }
   }
public:
   bool operator==(const Tableau &autre) const  {
      return size() == autre.size() &&
         std::equal(begin(), end(), autre.begin());
   }
   bool operator!=(const Tableau &autre) const  {
      return !(*this == autre);
   }
   Tableau(Tableau &&autre) noexcept
      : elems{ autre.elems }, nelems{ autre.nelems }, cap{ autre.cap } {
      autre.elems = {};
      autre.nelems = {};
      autre.cap = {};
   }
   Tableau& operator=(Tableau &&autre) noexcept {
      delete[] elems;
      elems = autre.elems;
      nelems = autre.nelems;
      cap = autre.cap;
      autre.elems = {};
      autre.nelems = {};
      autre.cap = {};
      return *this;
   }
};

Dans les notes de cours, vous trouverez de la matière en lien avec cette séance dans STR – Volume 00, annexes 00 et 01, mais vous en trouverez surtout dans les liens ci-dessus.

S03 INF749, 31 janvier

Au menu :

Pour le code du tableau générique tel que vu en classe, voici :

#include <cstddef>
#include <algorithm>
#include <initializer_list>
template <class T>
class Tableau {
public:
   using value_type = T;
   using size_type = std::size_t;
   using pointer = value_type*;
   using const_pointer = const value_type*;
   using reference = value_type&;
   using const_reference = const value_type&;
private:
   pointer elems;
   size_type nelems,
      cap;
public:
   size_type size() const noexcept {
      return nelems;
   }
   size_type capacity() const noexcept {
      return cap;
   }
   bool empty() const noexcept {
      return !size();
   }
private:
   bool full() const noexcept {
      return size() == capacity();
   }
public:
   using iterator = pointer;
   using const_iterator = const_pointer;
   iterator begin() noexcept {
      return elems;
   }
   const_iterator begin() const noexcept {
      return elems;
   }
   const_iterator cbegin() const noexcept {
      return elems;
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return begin() + size();
   }
   Tableau() noexcept : elems{}, nelems{}, cap{} {
   }
   Tableau(std::initializer_list<value_type> lst)
      : elems{ new value_type[lst.size()] },
      nelems{ lst.size() }, cap{ lst.size() } {
      try {
         std::copy(lst.begin(), lst.end(), begin());
      } catch(...) {
         delete[] elems;
         throw;
      }
   }
   Tableau(size_type n, const value_type &init)
      : cap{ n }, nelems{ n }, elems{ new value_type[n] } {
      try {
         std::fill(begin(), end(), init);
      } catch(...) {
         delete[] elems;
         throw;
      }
   }
   Tableau(const Tableau &autre)
      : elems{ new value_type[autre.size()] },
      nelems{ autre.size() }, cap{ autre.size() } {
      try {
         std::copy(autre.begin(), autre.end(), begin());
      } catch(...) {
         delete[] elems;
         throw;
      }
   }
   template <class It>
      Tableau(It debut, It fin)
         : nelems{ std::distance(debut, fin) } {
         cap = size();
         elems = new value_type[size()];
         try {
            std::copy(debut, fin, begin());
         } catch(...) {
            delete[] elems;
            throw;
         }
      }
   template <class U>
      Tableau(const Tableau<U> &autre)
         : cap{ autre.size() }, nelems{ autre.size() },
           elems{ new value_type[autre.size()] } {
         try {
            std::copy(autre.begin(), autre.end(), begin());
         } catch(...) {
            delete[] elems;
            throw;
         }
      }
   template <class U>
      Tableau& operator=(const Tableau<U> &autre) {
         Tableau{ autre }.swap(*this);
         return *this;
      }
   ~Tableau() {
      delete[] elems;
   }
   void swap(Tableau &autre) noexcept {
      using std::swap;
      swap(elems, autre.elems);
      swap(nelems, autre.nelems);
      swap(cap, autre.cap);
   }
   Tableau& operator=(const Tableau &autre) {
      Tableau{ autre }.swap(*this);
      return *this;
   }
   reference operator[](size_type n) noexcept {
      return elems[n];
   }
   const_reference operator[](size_type n) const noexcept {
      return elems[n];
   }
   void push_back(const_reference val) {
      if (full()) grow();
      elems[size()] = val;
      ++nelems;
   }
private:
   void grow() {
      const size_type new_cap = capacity() ? capacity() * 2 : 42; // hum
      auto p = new value_type[new_cap];
      try {
         std::copy(begin(), end(), p);
         delete[]elems;
         cap = new_cap;
         elems = p;
      } catch(...) {
         delete [] p;
         throw;
      }
   }
public:
   bool operator==(const Tableau &autre) const  {
      return size() == autre.size() &&
         std::equal(begin(), end(), autre.begin());
   }
   bool operator!=(const Tableau &autre) const  {
      return !(*this == autre);
   }
   Tableau(Tableau &&autre) noexcept
      : elems{ autre.elems }, nelems{ autre.nelems }, cap{ autre.cap } {
      autre.elems = {};
      autre.nelems = {};
      autre.cap = {};
   }
   Tableau& operator=(Tableau &&autre) noexcept {
      delete[] elems;
      elems = autre.elems;
      nelems = autre.nelems;
      cap = autre.cap;
      autre.elems = {};
      autre.nelems = {};
      autre.cap = {};
      return *this;
   }
};

Pour le code (plus simple, tout aussi efficace) que l'on obtient si on ajoute un unique_ptr à notre tableau générique, voici :

#include <cstddef>
#include <algorithm>
#include <initializer_list>
#include <memory>

template <class T>
class Tableau {
public:
   using value_type = T;
   using size_type = std::size_t;
   using pointer = value_type*;
   using const_pointer = const value_type*;
   using reference = value_type&;
   using const_reference = const value_type&;
private:
   std::unique_ptr<value_type[]> elems;
   size_type nelems,
      cap;
public:
   size_type size() const noexcept {
      return nelems;
   }
   size_type capacity() const noexcept {
      return cap;
   }
   bool empty() const noexcept {
      return !size();
   }
private:
   bool full() const noexcept {
      return size() == capacity();
   }
public:
   using iterator = pointer;
   using const_iterator = const_pointer;
   iterator begin() noexcept {
      return elems.get();
   }
   const_iterator begin() const noexcept {
      return elems.get();
   }
   const_iterator cbegin() const noexcept {
      return elems.get();
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return begin() + size();
   }
   Tableau() noexcept : elems{}, nelems{}, cap{} {
   }
   Tableau(std::initializer_list<value_type> lst)
      : elems{ new value_type[lst.size()] },
        nelems{ lst.size() }, cap{ lst.size() } {
      std::copy(lst.begin(), lst.end(), begin());
   }
   Tableau(size_type n, const value_type &init)
      : cap{ n }, nelems{ n }, elems{ new value_type[n] } {
      std::fill(begin(), end(), init);
   }
   Tableau(const Tableau &autre)
      : elems{ new value_type[autre.size()] },
        nelems{ autre.size() }, cap{ autre.size() } {
      std::copy(autre.begin(), autre.end(), begin());
   }
   template <class It>
   Tableau(It debut, It fin)
      : nelems{ std::distance(debut, fin) } {
      cap = size();
      elems = new value_type[size()];
      std::copy(debut, fin, begin());
   }
   template <class U>
   Tableau(const Tableau<U> &autre)
      : cap{ autre.size() }, nelems{ autre.size() },
        elems{ new value_type[autre.size()] } {
      std::copy(autre.begin(), autre.end(), begin());
   }
   template <class U>
   Tableau& operator=(const Tableau<U> &autre) {
      Tableau{ autre }.swap(*this);
      return *this;
   }
   ~Tableau() = default;
   void swap(Tableau &autre) noexcept {
      using std::swap;
      swap(elems, autre.elems);
      swap(nelems, autre.nelems);
      swap(cap, autre.cap);
   }
   Tableau& operator=(const Tableau &autre) {
      Tableau{ autre }.swap(*this);
      return *this;
   }
   reference operator[](size_type n) noexcept {
      return elems[n];
   }
   const_reference operator[](size_type n) const noexcept {
      return elems[n];
   }
   void push_back(const_reference val) {
      if (full()) grow();
      elems[size()] = val;
      ++nelems;
   }
private:
   void grow() {
      using namespace std;
      const size_type new_cap = capacity() ? capacity() * 2 : 42; // hum
      unique_ptr<value_type[]> p{ new value_type[new_cap] };
      copy(begin(), end(), p);
      cap = new_cap;
      swap(p, elems);
   }
public:
   bool operator==(const Tableau &autre) const  {
      return size() == autre.size() &&
         std::equal(begin(), end(), autre.begin());
   }
   bool operator!=(const Tableau &autre) const  {
      return !(*this == autre);
   }
   Tableau(Tableau &&autre) = default;
   Tableau& operator=(Tableau &&autre) = default;
};

Dans les notes de cours, vous trouverez de la matière en lien avec cette séance dans STR – Volume 00, annexes 00 et 01, mais vous en trouverez surtout dans les liens ci-dessus.

S04 IFT611/IFT729, 6 février

Au menu :

Pour le code (plus simple, tout aussi efficace) que l'on obtient si on ajoute un unique_ptr à notre tableau générique, voici :

#include <cstddef>
#include <algorithm>
#include <initializer_list>
#include <memory>

template <class T>
class Tableau {
public:
   using value_type = T;
   using size_type = std::size_t;
   using pointer = value_type*;
   using const_pointer = const value_type*;
   using reference = value_type&;
   using const_reference = const value_type&;
private:
   std::unique_ptr<value_type[]> elems;
   size_type nelems,
      cap;
public:
   size_type size() const noexcept {
      return nelems;
   }
   size_type capacity() const noexcept {
      return cap;
   }
   bool empty() const noexcept {
      return !size();
   }
private:
   bool full() const noexcept {
      return size() == capacity();
   }
public:
   using iterator = pointer;
   using const_iterator = const_pointer;
   iterator begin() noexcept {
      return elems.get();
   }
   const_iterator begin() const noexcept {
      return elems.get();
   }
   const_iterator cbegin() const noexcept {
      return elems.get();
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return begin() + size();
   }
   Tableau() noexcept : elems{}, nelems{}, cap{} {
   }
   Tableau(std::initializer_list<value_type> lst)
      : elems{ new value_type[lst.size()] },
        nelems{ lst.size() }, cap{ lst.size() } {
      std::copy(lst.begin(), lst.end(), begin());
   }
   Tableau(size_type n, const value_type &init)
      : cap{ n }, nelems{ n }, elems{ new value_type[n] } {
      std::fill(begin(), end(), init);
   }
   Tableau(const Tableau &autre)
      : elems{ new value_type[autre.size()] },
        nelems{ autre.size() }, cap{ autre.size() } {
      std::copy(autre.begin(), autre.end(), begin());
   }
   template <class It>
   Tableau(It debut, It fin)
      : nelems{ std::distance(debut, fin) } {
      cap = size();
      elems = new value_type[size()];
      std::copy(debut, fin, begin());
   }
   template <class U>
   Tableau(const Tableau<U> &autre)
      : cap{ autre.size() }, nelems{ autre.size() },
        elems{ new value_type[autre.size()] } {
      std::copy(autre.begin(), autre.end(), begin());
   }
   template <class U>
   Tableau& operator=(const Tableau<U> &autre) {
      Tableau{ autre }.swap(*this);
      return *this;
   }
   ~Tableau() = default;
   void swap(Tableau &autre) noexcept {
      using std::swap;
      swap(elems, autre.elems);
      swap(nelems, autre.nelems);
      swap(cap, autre.cap);
   }
   Tableau& operator=(const Tableau &autre) {
      Tableau{ autre }.swap(*this);
      return *this;
   }
   reference operator[](size_type n) noexcept {
      return elems[n];
   }
   const_reference operator[](size_type n) const noexcept {
      return elems[n];
   }
   void push_back(const_reference val) {
      if (full()) grow();
      elems[size()] = val;
      ++nelems;
   }
private:
   void grow() {
      using namespace std;
      const size_type new_cap = capacity() ? capacity() * 2 : 42; // hum
      unique_ptr<value_type[]> p{ new value_type[new_cap] };
      copy(begin(), end(), p);
      cap = new_cap;
      swap(p, elems);
   }
public:
   bool operator==(const Tableau &autre) const  {
      return size() == autre.size() &&
         std::equal(begin(), end(), autre.begin());
   }
   bool operator!=(const Tableau &autre) const  {
      return !(*this == autre);
   }
   Tableau(Tableau &&autre) = default;
   Tableau& operator=(Tableau &&autre) = default;
};

L'optique poursuivie est :

  • Explorer la question de la résilience des programmes plus en détail
  • Voir comment il est possible de contrôler finement les mécanismes d'allocation (choisir le lieu, la façon, les stratégies, etc.)
  • Montrer comment il est possible d'en arriver à des mécanismes d'allocation dynamique de mémoire qui soient déterministes (quand le contexte s'y prête)

Ajustements de dernière minute

J'ai oublié deux trucs importants ce soir, en me dépêchant pour essayer de vous libérer avant 21 h, soit :

  • De vous distribuer le minitest Q02. Heureusement, ceci est facile à corriger : voici une version PDF, à laquelle vous pourrez répondre cette semaine (sur une base individuelle, cela va de soi!) pour me rapporter une version imprimée et dûment remplie par votre illustre personne : STR--Q02.pdf
  • De vous expliquer ce qui cloche dans le code suivant, à la ligne affublée du commentaire ← ICI :
void* operator new(size_t n) {
   auto p = malloc(n + sizeof(max_align_t)); // laissé en exercice dans le cours
   if (!p) throw bad_alloc{};
   auto q = static_cast<size_t*>(p);
   *q = n; // ← ICI (incorrect)
   Comptable::get().prendre(n);
   return static_cast<max_align_t*>(p) + 1; // aussi laissé en exercice :)
}

En effet, comme mentionné en classe, l'écriture *q = n; est incorrecte en C++ du fait que l'on affecte une valeur dans une zone où il n'existe aucun objet encore. C est plus tolérant que C++ dans de tels cas. En C++, un objet (incluant le plus humble int) est créé, techniquement, par un constructeur.

Heureusement, nous avons vu le new positionnel, ou Placement new, qui permet de créer un objet à un endroit de notre choix. Une écriture correcte serait donc :

void* operator new(size_t n) {
   auto p = malloc(n + sizeof(max_align_t));
   if (!p) throw bad_alloc{};
   auto q = static_cast<size_t*>(p);
   new (static_cast<void*>(q)) size_t{ n }; // ← ICI (correct!)
   Comptable::get().prendre(n);
   return static_cast<max_align_t*>(p) + 1;
}

En pratique, il est peu probable que l'exécution diffère entre le code correct et le code incorrect, mais un optimiseur agressif pourrait supprimer la ligne fautive dans l'exemple incorrect (c'est un comportement indéfini, après tout).

S04 INF749, 7 février

Au menu :

  • Q02
  • Brève discussion de l'importance d'échouer tôt, du moins lorsqu'on échoue :
    • privilégier un plantage à la compilation, avec static_assert, si cela s'avère possible, sinon
    • privilégier un plantage en laboratoire, peut-être avec assert(), si le problème détecté est dynamique et irrécupérable,ou
    • privilégier un plantage en laboratoire, en levant une exception, si le problème détecté est dynamique mais nous semble mener à une situation que le client ne peut ignorer et d'où le code client est susceptible de récupérer; et enfin
    • retourner des codes d'erreur pour les situations problématiques que le client peut ignorer sans que cela n'entraîne de conséquences trop fâcheuses
      • notez que les exceptions sont la manière correcte de signaler un problème dans un constructeur (à moins que la situation ne soit irrécupérable – voir ci-dessus), ceux-ci n'ayant pas de valeur de retour, mais
      • notez aussi que les exceptions ne sont pas du tout convenables dans un destructeur, ceci rendant le programme inutilisable

Notez que les diapositives électroniques utilisées pour décrire (entre autres) les approches au traitement des erreurs dans les cas où les exceptions ne sont pas souhaitées sont disponibles sur Amsterdam-2016-PR-The-Exception-Situation.pdf. Elles sont en anglais; c'est le matériel sous-jacent à une conférence que j'ai donné en novembre 2016 à Amsterdam.

  • Premiers pas dans la gestion intelligente de la mémoire :
    • survol des mécanismes inhérents au langage C (std::malloc() et std::free()) et des implications de leurs signatures respectives
    • spécialisation des services de C++ :
      • de manière globale, avec pour exemple un système primitif de détection de fuites
      • de manière no-throw
      • de manière positionnelle... Ne remplacez pas la spécialisation existante dans ce cas, je vous en prie!
      • avec assistants pour mémoire spécialisée
      • sous forme de méthodes d'instance
    • les arénas, qui permettent de gérer des zones de mémoire choisies
  • Survol de considérations d'alignement en mémoire

L'optique poursuivie est :

  • Explorer la question de la résilience des programmes plus en détail
  • Voir comment il est possible de contrôler finement les mécanismes d'allocation (choisir le lieu, la façon, les stratégies, etc.)
  • Montrer comment il est possible d'en arriver à des mécanismes d'allocation dynamique de mémoire qui soient déterministes (quand le contexte s'y prête)
S05 IFT611/IFT729, 13 février

Au menu :

  • Q03
    • le document vous est cette fois offert sous forme électronique, à faire individuellement mais hors de la classe (pour vous permettre d'utiliser un compilateur et un débogueur dans votre démarche) : STR--Q03.pdf
  • Retour sur Q02 et introduction de constexpr
  • Brève discussion de l'importance d'échouer tôt, du moins lorsqu'on échoue :
    • privilégier un plantage à la compilation, avec static_assert, si cela s'avère possible, sinon
    • privilégier un plantage en laboratoire, peut-être avec assert(), si le problème détecté est dynamique et irrécupérable,ou
    • privilégier un plantage en laboratoire, en levant une exception, si le problème détecté est dynamique mais nous semble mener à une situation que le client ne peut ignorer et d'où le code client est susceptible de récupérer; et enfin
    • retourner des codes d'erreur pour les situations problématiques que le client peut ignorer sans que cela n'entraîne de conséquences trop fâcheuses
      • notez que les exceptions sont la manière correcte de signaler un problème dans un constructeur (à moins que la situation ne soit irrécupérable – voir ci-dessus), ceux-ci n'ayant pas de valeur de retour, mais
      • notez aussi que les exceptions ne sont pas du tout convenables dans un destructeur, ceci rendant le programme inutilisable

Notez que les diapositives électroniques utilisées pour décrire (entre autres) les approches au traitement des erreurs dans les cas où les exceptions ne sont pas souhaitées sont disponibles sur Amsterdam-2016-PR-The-Exception-Situation.pdf. Elles sont en anglais; c'est le matériel sous-jacent à une conférence que j'ai donné en novembre 2016 à Amsterdam

S05 INF749, 14 février

Au menu :

Bonne St-Valentin!

 
S06 IFT611/IFT729, 20 février

C'est la semaine des intras, mais nous tenons une séance de cours au même local que d'habitude car nous aimons tellement notre cours, n'est-ce pas?

Au menu :

 

S06 INF749, 21 février

Tel que je vous l'ai indiqué par courriel, je ne pourrai pas tenir de séance in vivo ce soir, pour cause de maladie dans la famille. Je reproduis cependant ci-dessous les consignes en lien avec la réflexion technique à laquelle je vous convie :

Vous devez consommer des données d'une source ininterruptible (au sens où les données entrent en continu, comme dans le cas d'un courant électrique par exemple) pour les entreposer dans un fichier texte, le tout afin de les afficher avec un chiffrier électronique par la suite (en tirer des graphiques, examiner les courbes et tout le tralala).

Ces données arrivent à rythme constant, p. ex. : un bloc de 1024 double chaque millième de seconde.

L'appareil qui vous livrera les données exposera celles-ci à l'aide des variables et des structures de données suivantes :

enum { TAILLE_BLOC = 1024 };
struct Tampons {
   double data[2][TAILLE_BLOC];
};
//
// variables qui vous sont rendues accessibles, peu importe comment
//
Tampons tampons; // les tampons
short dernier_tampon_rempli; // indice du plus récent tampon rempli (alterne entre 0 et 1)
long long nb_tampons_remplis; // incrémente de manière monotone

La mécanique par laquelle le fournisseur de données procédera sera la suivante :

  • Initialement, dernier_tampon_rempli sera -1, et nb_tampons_remplis sera 0
  • Après une unité de temps (1 ms, disons), tampons[0] sera rempli (1024 double y auront été écrits), après quoi dernier_tampon_rempli deviendra 0 et nb_tampons_remplis deviendra 1
  • Après deux unités de temps (1 ms après la précédente), tampons[1] sera rempli (1024 double y auront été écrits), après quoi dernier_tampon_rempli deviendra 1 et nb_tampons_remplis deviendra 2
  • Après trois unités de temps (1 ms après la précédente), tampons[0] sera rempli (1024 double y auront été écrits, remplaçant ce qui s'y trouvait auparavant), après quoi dernier_tampon_rempli deviendra 0 et nb_tampons_remplis deviendra 3
  • etc.

Votre tâche est de prendre les données du plus récent tampon rempli pour les écrire sur disque, et ce avant que le fournisseur ne les ait écrasées. Vous n'avez pas à écrire sur disque tout de suite, mais vous disposez d'une mémoire finie alors l'option de simplement laisser les données d'accumuler en mémoire vive ne convient pas (il faudra que des écritures sur disque aient lieu au moins de temps en temps pendant l'opération de votre fournisseur de données).

Notez qu'écrire en mémoire (ce que fait le fournisseur) est typiquement plus rapide qu'écrire sur disque (votre tâche, en fin de compte), ce qui fait qu'un thread qui prendrait simplement les données d'un tampon pour les écrire sur disque serait voué à l'échec (il y aurait des pertes de données, le fournisseur étant plus rapide que votre propre code). Il faut aussi savoir que vous ne pouvez pas verrouiller les données entrantes avec un mutex ou d'autres mécanismes du même acabit (le fournisseur ne s'arrêtera pas pour vous attendre)

Ce que votre solution doit exprimer

On souhaite savoir, pour votre solution à ce problème :

  • Quels sont les threads nécessaires et leur rôle (à la limite, le pseudocode de chacun, ou un diagramme exprimant la logique du thread en question). Je vous invite d'ailleurs fortement à être le plus précis possible dans votre écriture (un pseudocode est utile s'il est détaillé), ce qui vous permettra de mieux voir si vous avez compris les enjeux
  • Quelles les structures de données nécessaires. Ici encore, plus vous pourrez m'en dire sur celles-ci et mieux ce sera
  • Quels sont les enjeux de synchronisation (y en a-t-il? Si oui, lesquels?)
  • comment ferez-vous pour détecter l'arrivée de nouvelles données de la part du fournisseur
  • Le cas échéant, comment détecterez-vous une perte de données (un cas où vous n'auriez pas été suffisamment rapides pour consommer ce que le fournisseur vous aura offert)

Bonne réflexion!

27 février

Relâche au campus principal. Reposez-vous un peu, vous en avez sûrement besoin! Je serai à la rencontre du WG21 à Kona; voir ../../Sujets/Orthogonal/wg21-2017-Kona.html si vous voulez suivre mes aventures.

S07 INF749, 28 février

Je serai à la rencontre du WG21 à Kona; voir ../../Sujets/Orthogonal/wg21-2017-Kona.html si vous voulez suivre mes aventures.

S07 IFT611/IFT729, 6 mars

Au menu :

  • Introduction aux problèmes d'entrées/ sorties dans les STR (sujet sur lequel nous reviendrons) :
    • entrées ininterruptibles (TR strict)
    • contrainte d'immédiateté (basse latence)
    • contrainte de brièveté
    • combiner indéterminisme des entrées/ sorties et consommation de données à rythme constant
    • distinguer temps constant et temps constant amorti (quand cela compte)
    • réduire le blocage
  • Examen d'une stratégie interruptible de compression de données, incluant :
    • le concept général de fonction morcelable (une espèce de fonction interruptible_foreach())
S08 INF749, 7 mars

Au menu :

  • Q04
  • Références de relais et Perfect Forwarding
  • Débogage et classe Noisy
  • Introduction aux problèmes d'entrées/ sorties dans les STR (sujet sur lequel nous reviendrons) :
    • entrées ininterruptibles (TR strict)
    • contrainte d'immédiateté (basse latence)
    • contrainte de brièveté
    • combiner indéterminisme des entrées/ sorties et consommation de données à rythme constant
    • distinguer temps constant et temps constant amorti (quand cela compte)
    • réduire le blocage
  • Examen d'une stratégie interruptible de compression de données, incluant :
    • le concept général de fonction morcelable (une espèce de fonction interruptible_foreach())
S08 IFT611/IFT729, 13 mars

Au menu :

S09 INF749, 14 mars

Au menu : cours suspendu pour cause de conditions routières épouvantables.

C'est le jour de π!

S09 IFT611/IFT729, 20 mars

Au menu :

Nous nous dirigeons vers un examen des ordonnanceurs statiques, reposant sur des tâches périodiques connues a priori, de même que de ce que sont les conditions d'« ordonnançabilité ».

Si vous êtes curieuses ou curieux, un projet (pas vraiment nettoyé, mais qui peut être amusant à consulter) est disponible ici. étant donné la nature novatrice et expérimentale de cette chose, je vous invite à me communiquer tous les bogues que vous y trouverez.

Dans les notes de cours, vous trouverez de la matière en lien avec cette séance dans STR – Volume 00, pages ≈37..43 pour les ordonnanceurs TR et dans STR – Volume 04, pages ≈48..58 et ≈158..174 pour les entrées/ sorties, et pages ≈134..157 pour les exécutifs. Pour les techniques d'optimisation, examinez STR – Volume 03, pp. ≈109..119

S10 INF749, 21 mars

Au menu :

S10 IFT611/IFT729, 27 mars

Au menu :

S11 INF749, 28 mars

Au menu :

S11 IFT611/IFT729, 3 avril

Au menu :

S12 INF749, 4 avril

Au menu :

S12 IFT611/IFT729, 10 avril

Au menu :

  • Q09
  • Quelques présentations de projets :
    • présentation du projet de l'équipe composée de Jean-Samuel Aubry-Guzzi et de Marie-Eve Dubé, projet portant sur un lecteur audio pour les jeux de NES, qui ne joue finalement pas d'audio de la NES
    • présentation du projet de l'équipe composée de Pierre-Antoine Deshaies et de Mathieu Le Reste, soit le projet PMCtire – Gestion d'entrepôt en temps réel grâce au RFID
    • présentation du projet de Danny Groleau et Gabriel Gagné, pour qui la phrase clé est « je suis tombé amoureux d'une caméra espion russe »
    • présentation de Jesse Emond, qui souhaite partager son mineur de Bitcoins
  • Visite d'un conférencier surprise vers 10 h 30
S13 INF749, 11 avril

Au menu :

  • Q09
  • Présentations des projets individuels
  • S'il reste du temps, survol d'une technique en vogue, soit celle des non-owning views à partir de string_view (version « maison » d'un outil standard de C++ 17)
17 avril

Lundi de Pâques, congé universitaire

S14 INF749, 18 avril

Chic examen final plein d'amour

S13 IFT611/IFT729, 24 avril

Chic examen final plein d'amour, de 9h à 12h au local D3-2035

   

Code des cas sous étude dans les notes de cours

Les sections qui suivent proposent du code ou des exemples proposés en classe, le tout dans le but de vous permettre d'étudier la chose, de critiquer, de commenter, de questionner et d'expérimenter à loisir. Notez que certains des exemples ci-dessous doivent être retouchés à la lueur de l'avènement du standard C++ 11.

Sources des exemples du document STR – Volume 01
cible

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

cible

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

cible

Cliquez sur cette cible pour obtenir le code du test 0.0

cible

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

cible

Cliquez sur cette cible pour obtenir le code du test 0.1

cible

Cliquez sur cette cible pour obtenir le code du test 1.0

cible

Cliquez sur cette cible pour obtenir le code du test 1.1

cible

Cliquez sur cette cible pour obtenir le code du test 1.2

cible

Cliquez sur cette cible pour obtenir le code du test 1.3

cible

Cliquez sur cette cible pour obtenir le code du test 2.0

cible

Cliquez sur cette cible pour obtenir le code du test 2.1

cible

Cliquez sur cette cible pour obtenir le code du test 2.2

cible

Cliquez sur cette cible pour obtenir le code du test 3.0

En lien avec l'exercice de compression de données

Cliquez sur cette cible pour obtenir le projet bmp00, réalisant une compression RLE sur des bitmaps dans un temps raisonnable. Ce projet n'est pas un STR puisqu'il cherche à réaliser rapidement et correctement une tâche mais n'offre aucune garantie de non-dépassement d'un seuil de temps – il n'y a aucun plafond mesurable dans le temps d'exécution de l'algorithme de compression dans ce programme, donc aucune contrainte de temps dont le respect serait déterministe.

L'idée d'offrir d'abord une version opérationnelle d'un algorithme donné, sans se préoccuper de contraintes TR, est que cette version est en général plus simple que les versions offrant des garanties TR strictes.

Sur le plan pédagogique, cela donne aussi une excuse à votre professeur pour mettre en place des bases conceptuelles clés du code moderne, pour que toutes et tous comprennent ses exemples, sans aller jusqu'à donner un cours général de techniques de programmation contemporaines. J'essaie de mettre en place des bases conceptuelles et techniques communes sans trop me répéter étant donné la nature bigarrée mais techniquement très solide de la clientèle de ce cours.

Cliquez sur cette cible pour obtenir le projet bmp-morcele, réalisant une compression RLE sur des bitmaps dans un temps raisonnable et de manière à ne pas dépasser un certain seuil de tolérance au temps.

Cette version compresse des données RGB brutes selon une approche RLE et peut, contrairement aux deux précédentes, être considérée TR (au sens usuel, pas au sens strict, mais principalement à cause de la plateforme) dans la mesure où le seuil indiquant d'arrêter tiendrait compte du pire cas possible (calculé a priori) pour une séquence de compression RLE donnée. Aller jusque là demanderait toutefois une meilleure connaissance du contexte et obscurcirait quelque peu le propos. Le code du projet est du code de test, montrant qu'il est possible de faire en sorte que l'algorithme de compression s'interrompe « en cours de traitement ».

Quelques suggestions d'exercices pour vous faire la main :

  • ajoutez un traitement arbitraire (que vous pouvez simuler par une attente active basée sur un délai aléatoire) dans la boucle qui invoque la fonction compressant une séquence selon une approche RLE. Présumez que cette boucle doive itérer fois par seconde, donc que chaque itération de la boucle prenne au pire seconde, et faites en sorte que la compression n'utilise que le temps restant (s'il y en a). Le temps accordé à l'algorithme de compression sera donc un seuil variable plutôt que constant;
  • transformez l'algorithme de compression pour qu'il puisse être interrompu pendant une séquence RLE plutôt qu'entre chaque séquence RLE. Cette version sera globalement plus lente que la version proposée par le professeur mais sera plus près d'une version déterministe, donc moins à risque de déborder des contraintes TR imposées par le contexte. Vous voudrez utiliser un foncteur plutôt qu'une fonction pour réaliser cet exercice;
  • l'algorithme qui transforme une séquence de bytes bruts en vecteur de valeurs RGB est lent. Transformez-le de manière à ce qu'il soit interruptible;
  • plus costaud : transformez la fonction qui compresse un bitmap de manière à ce qu'elle soit interruptible. Ceci sera plus facile à réaliser si l'algorithme transformant une séquence de bytes bruts en séquence RGB est lui-même interruptible. Considérez la fonction consommant un bitmap du flux comme était une opération indivisible (ceci vous permettra de vous concentrer sur l'essentiel);
  • pour que les algorithmes soient plus déterministes, utilisez des tableaux bruts ou des vecteurs préalablement dimensionnés comme conteneurs de destination pour les algorithmes de transformation de séquence de bytes en séquence RGB et de compression RLE. Analysez la solution que vous proposez pour montrer en quoi elle est préférable à la version antérieure et en quoi elle est moins intéressante (évitez les banalités, il y a une réelle réflexion à faire ici).

Cliquez sur cette cible pour la description du format bitmap.

Cliquez sur cette cible pour la description de la compression RLE. Pour un peu de pédagogie sur RLE, voir http://hbfs.wordpress.com/2009/04/14/ad-hoc-compression-methods-rle/

En lien avec l'exécutif

Pour un texte sur le concept, voir ../../Sujets/TempsReel/executifs.html

Cliquez sur cette cible pour obtenir les sources d'un projet contenant une ébauche fonctionnelle d'exécutif de simulation. Ce projet a été conçu avec Visual Studio 2017, mais les sources sont essentiellement portables (le fichier source non portable est concis, et je pense que vous n'aurez pas de peine à l'identifier).

Un exécutif est un système monoprogrammé qui, avec discipline et avec soin, permet d'atteindre des performances prévisibles et des comportements se rapprochant de ceux qu'on retrouve dans les systèmes multiprogrammés, mais sans payer le prix associés outils de synchronisation. Rien n'est parfait (la mécanique ne peut être répartie sur plusieurs coeurs qu'au prix d'efforts manuels) mais l'idée peut être stimulante et repose sur des techniques qu'on enseigne peu à dans nos institutions aujourd'hui.

En lien avec les séances sous QNX

Pour une image frappante, je vous invite à comparer le schéma des états d'un processus qu'on trouve sur le Wiki à ce sujet avec celui que met de l'avant QNX (document d'origine). C'est divertissant.

Notez que l'aide en ligne pour QNX est de très bonne qualité, pour ce système en particulier comme pour les STR en général. La racine pour la version la plus récente de cette aide (à ma connaissance, du moins) est http://www.qnx.com/developers/docs/6.5.0/index.jsp

Pour les séances avec QNX, vous trouverez le code source des illustrations à travers les liens suivants (ce ne sont que de petits exemples pour vous démarrer, sans plus) :

Le lien le plus important est sans doute celui offrant de l'aide sur la bibliothèque standard de la platreforme, soit http://www.qnx.com/developers/docs/6.5.0/topic/com.qnx.doc.neutrino_lib_ref/about.html. Pour la messagerie synchrone, portez une attention particulière au trio d'opérations MsgSend(), MsgReceive() et MsgReply().

De la documentation touffue vous est offerte sur les SETR et sur QNX dans la section à cet effet : http://www.qnx.com/developers/docs/6.5.0/topic/com.qnx.doc.neutrino/bookset.html

À propos du développement TR pour processeurs à plusieurs coeurs, la section http://www.qnx.com/developers/docs/6.5.0/topic/com.qnx.doc.multicore_en/bookset.html peut vous intéresser.

En lien avec les entrées/ sorties

Les sources du code de Double-Buffering et du code du serveur d'entrées/ sorties non-bloquantes sont mises à votre disposition. Désolé de ne pas avoir fait une meilleure présentation, le temps m'a manqué.

Petite question analytique

Un appareil de type « photo radar » a pour rôle de détecter le mouvement d'un véhicule dans un espace contrôlé et, si la vitesse de déplacement du véhicule en question dépasse un certain seuil, de provoquer une capture d'image qui sera analysée pour détecter un ensemble de caractéristiques (couleur, marque, symboles sur la plaque d'immatriculation, etc.).

En bref, un capteur physique (le radar) saisit les mouvements d'objets dans un espace et les signale à un module d'analyse de première ligne capable de reconnaître un déplacement suspect et de provoquer une demande de capture d'image de la part d'une caméra à haute définition. Une fois l'image capturée, celle-ci est transmise à un module analytique qui en sortira les principales caractéristiques recherchées, puis les intégrera à une base de données. Ensuite, un module produisant des contraventions en fonction des besoins pourra, de manière automatique, faire son travail.

La question est en trois volets :

Résultats des minitests

Les résultats des minitests distribués au cours de la session vont comme suit. Notez que la moyenne globale indiquée ici tient compte du fait que je ne retiens que les huit meilleurs résultats sur dix. Notez aussi que les présentations en classe sont susceptibles de mener au remplacement d'un minitest moins bien réussi, ce qui fait que les moyennes en fin de compte sera probablement un peu meilleure que celles indiquées ici.

IFT611/IFT729

INF749

QXX

Séance

QXX

Séance

Q00

S02

Q00

S02

Q01

S03

Q01

S03

Q02

S04

Q02

S04

Q03

S05

Q03

S05

Q04

S06

Q04

S06

Q05

S08

Q05

S09

Q06

S09

Q06

S11

Q07

S10

Q07

S11

Q08

S11

Q08

S12

Q09

S12

Q09

S13

 :
 :

Résultats des livrables

Les résultats de l'évaluation des livrables remis au cours de la session vont comme suit. Ici, représente le nombre de projets livrés.

IFT611/IFT729 INF749
LXX Remise à la séance LXX Remise à la séance
L00

S03

L00

S03

L01

S08

L01

S08

L02

S12

L02

S12

 :
 :
 :
 :

Valid XHTML 1.0 Transitional

CSS Valide !