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 INF749

Plan de cours

Plan de cours

Consignes quant au projet de session

Consignes quant au projet de session

Si vous cherchez l'inspiration, 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 :

En lien avec les notes de cours

Pour INF749, cours s'adressant aux étudiant(e)s de 2e cycle, les frais de production de notes de cours sont facturés a priori et celles-ci vous seront rendues disponibles directement.

Pour IFT611, les informations pour obtenir les documents vous ont été transmises par courriel.

Note d'ordre général

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 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 Contenu IFT611 Séance INF749 Contenu INF749
S00 IFT611, 7 janvier

Le mots de la semaine : introduction, vocabulaire et bases. On s'entend sur quelques termes et façons de faire qui nous suivront toute la session

Au menu :

  • Présentation du plan de cours
  • Présentation du projet de session
  • Présentation in absentia de mon chic auxiliaire
  • 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 λ-expression
  • 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.

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 jetez un coup d'oeil à ../../Sources/comparatif_vecteur_tableau.html si vous êtes intéressé(e).

De même, si vous êtes curieuse / curieux de comparer la vitesse à l'exécution d'une fonction et d'un foncteur à tâche équivalente, voir ../../Sources/Comparaison-Fonctions-Foncteurs.html

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, 8 janvier

Le mots de la semaine : introduction, vocabulaire et bases. On s'entend sur quelques termes et façons de faire qui nous suivront toute la session

Au menu :

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.

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 jetez un coup d'oeil à ../../Sources/comparatif_vecteur_tableau.html si vous êtes intéressé(e).

De même, si vous êtes curieuse / curieux de comparer la vitesse à l'exécution d'une fonction et d'un foncteur à tâche équivalente, voir ../../Sources/Comparaison-Fonctions-Foncteurs.html

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, 14 janvier

Note importante : puisque nous semblons manquer de place dans notre local d'origine, le cours se donnera désormais au D3-2037. Un gros merci aux gens de la Faculté qui ont réagi rapidement!

Le mots de la semaine : saines pratiques et hygiène de programmation. On établit des façons de faire, et on examine les nuances entre copie (complexité typiquement linéaire, temps souvent indéterministe) et mouvement (complexité typiquement constante, temps souvent déterministe), tout en introduisant quelques idiomes fort utiles.

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 d'un programme, suit :

#include <cstddef> // pour std::size_t
#include <algorithm>

class Tableau {
public:
   using value_type = int;
   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 begin();
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return end();
   }
   Tableau() = default;
   Tableau(size_type n, const_reference 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;
   }
   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 = std::exchange(autre.elems, nullptr);
      nelems = std::exchange(autre.nelems, 0);
      cap = std::exchange(autre.cap, 0);
      return *this;
   }
   //
   // nous n'avons pas fait ce qui suit en classe, mais
   // nous le ferons à la prochaine séance
   //
   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];
      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);
   }
};


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

template <class F, class ... Args>
   auto tester(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return make_pair(res, post - pre);
   }

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

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

int main() {
   enum { N = 10'000'000 };
   vector<double> v(N);
   iota(begin(v), end(v), 1.0);
   auto [r0,dt0] = tester([v]() mutable {
      v = f(v);
      return v.back();
   });
   auto [r1,dt1] = tester([v]() mutable {
      g(v);
      return v.back();
   });
   auto [r2,dt2] = tester([v]() mutable {
      v = f(std::move(v));
      return v.back();
   });
   cout << "v = f(v)            : " << duration_cast<microseconds>(dt0).count()
        << " us." << endl;
   cout << "g(v)                : " << duration_cast<microseconds>(dt1).count()
        << " us." << endl;
   cout << "v = f(std::move(v)) : " << duration_cast<microseconds>(dt2).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, 15 janvier

Le mots de la semaine : saines pratiques et hygiène de programmation. On établit des façons de faire, et on examine les nuances entre copie (complexité typiquement linéaire, temps souvent indéterministe) et mouvement (complexité typiquement constante, temps souvent déterministe), tout en introduisant quelques idiomes fort utiles.

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 d'un programme, suit :

#include <cstddef> // pour std::size_t (vous avez préféré int)
#include <algorithm>

class Tableau {
public:
   using value_type = int;
   using size_type = std::size_t; // vous avez préféré int
   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 begin();
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return end();
   }
   Tableau() = default;
   Tableau(size_type n, const_reference 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;
   }
   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;
   }
   //
   // nous n'avons pas fait ce qui suit en classe, mais
   // nous le ferons à la prochaine séance
   //
   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];
      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);
   }
};


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

template <class F, class ... Args>
   auto tester(F f, Args &&... args) {
      auto pre = high_resolution_clock::now();
      auto res = f(std::forward<Args>(args)...);
      auto post = high_resolution_clock::now();
      return make_pair(res, post - pre);
   }

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

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

int main() {
   enum { N = 10'000'000 };
   vector<double> v(N);
   iota(begin(v), end(v), 1.0);
   auto [r0,dt0] = tester([v]() mutable {
      v = f(v);
      return v.back();
   });
   auto [r1,dt1] = tester([v]() mutable {
      g(v);
      return v.back();
   });
   auto [r2,dt2] = tester([v]() mutable {
      v = f(std::move(v));
      return v.back();
   });
   cout << "v = f(v)            : " << duration_cast<microseconds>(dt0).count()
        << " us." << endl;
   cout << "g(v)                : " << duration_cast<microseconds>(dt1).count()
        << " us." << endl;
   cout << "v = f(std::move(v)) : " << duration_cast<microseconds>(dt2).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, 21 janvier

Le mots de la semaine : sélection à coût nul d'algorithmes. Premier contact avec les traits et leurs applications.

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()
  • Petite parenthèse distrayante avec assez_proches()
  • L'exemple amusant d'un trait est_convertible

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

J'ai utilisé, en plus du tag dispatching, deux approches sophistiquées pour réaliser une sélection statique (à coût nul) d'algorithme :

  • Une reposant sur l'étrange manoeuvre qu'est enable_if
  • Une autre reposant sur la tout aussi efficace (mais sans doute plus... digeste) if constexpr

Pour la version avec tag dispatching :

#include <iterator>
using namespace std; // bof
//
// j'ai appelé la fonction distance_ pour éviter les
// conflits de nom avec std::distance
//
template <class It>
   auto distance_(It debut, It fin, forward_iterator_tag) {
      typename iterator_traits<It>::difference_type n{};
      for(; debut != fin; ++debut)
         ++n;
      return n;
   }
template <class It>
   auto distance_(It debut, It fin, random_access_iterator_tag) {
      return fin - debut;
   }
template <class It>
   auto distance_(It debut, It fin) {
      return distance_(
         debut, fin, typename iterator_traits<It>::iterator_category{}
      );
   }

Je vous épargne la version avec enable_if, qui est un peu pénible ici.

Pour la version avec if constexpr :

#include <iterator>
#include <type_traits>
using namespace std; // bof
//
// j'ai appelé la fonction distance_ pour éviter les
// conflits de nom avec std::distance
//
template <class It>
   auto distance_(It debut, It fin) {
      using categ = typename iterator_traits<It>::iterator_category;
      if constexpr(is_same_v<categ, random_access_iterator_tag>)
         return fin - debut;
      else if constexpr(is_convertible_v<categ, forward_iterator_tag>) {
         typename iterator_traits<It>::difference_type n{};
         for(; debut != fin; ++debut)
            ++n;
         return n;
      }
      else
         static_assert(false);

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, 22 janvier

Le mots de la semaine : sélection à coût nul d'algorithmes. Premier contact avec les traits et leurs applications.

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()
  • Petite parenthèse distrayante avec assez_proches()
  • Je ne l'ai pas exploré en classe, mais vous pouvez examiner l'exemple amusant d'un trait est_convertible

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

J'ai utilisé, en plus du tag dispatching, deux approches sophistiquées pour réaliser une sélection statique (à coût nul) d'algorithme :

  • Une reposant sur l'étrange manoeuvre qu'est enable_if
  • Une autre reposant sur la tout aussi efficace (mais sans doute plus... digeste) if constexpr

Pour la version avec tag dispatching :

#include <iterator>
using namespace std; // bof
//
// j'ai appelé la fonction distance_ pour éviter les
// conflits de nom avec std::distance
//
template <class It>
   auto distance_(It debut, It fin, forward_iterator_tag) {
      typename iterator_traits<It>::difference_type n{};
      for(; debut != fin; ++debut)
         ++n;
      return n;
   }
template <class It>
   auto distance_(It debut, It fin, random_access_iterator_tag) {
      return fin - debut;
   }
template <class It>
   auto distance_(It debut, It fin) {
      return distance_(
         debut, fin, typename iterator_traits<It>::iterator_category{}
      );
   }

Je vous épargne la version avec enable_if, qui est un peu pénible ici.

Pour la version avec if constexpr :

#include <iterator>
#include <type_traits>
using namespace std; // bof
//
// j'ai appelé la fonction distance_ pour éviter les
// conflits de nom avec std::distance
//
template <class It>
   auto distance_(It debut, It fin) {
      using categ = typename iterator_traits<It>::iterator_category;
      if constexpr(is_same_v<categ, random_access_iterator_tag>)
         return fin - debut;
      else if constexpr(is_convertible_v<categ, forward_iterator_tag>) {
         typename iterator_traits<It>::difference_type n{};
         for(; debut != fin; ++debut)
            ++n;
         return n;
      }
      else
         static_assert(false);

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, 28 janvier

Le mots de la semaine : sélection à coût nul d'algorithmes et résilience. Notre exploration des traits et de leurs applications se poursuit; nous revenons sur le tableau d'entiers pour en faire un tableau générique, et nous examinons les conséquences de ce geste sur la résilience de notre code.

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 begin();
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return end();
   }
   Tableau() = default;
   //
   // Notez que le constructeur ci-dessous peut bénéficier
   // du recours à enable_if pour éviter certaines ambiguïtés
   //
   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;
      }
   }
   //
   // Notez que le constructeur ci-dessous peut bénéficier
   // du recours à enable_if pour éviter certaines ambiguïtés
   //
   Tableau(size_type n, const_reference 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;
      }
   }
   //
   // Notez que le constructeur ci-dessous peut bénéficier
   // du recours à enable_if pour éviter certaines ambiguïtés
   //
   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 = std::exchange(autre.elems, nullptr);
      nelems = std::exchange(autre.nelems, 0);
      cap = std::exchange(autre.cap, 0);
      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.

N'oubliez pas de remettre L00

S03 INF749, 29 janvier

Le mots de la semaine : sélection à coût nul d'algorithmes et résilience. Notre exploration des traits et de leurs applications se poursuit; nous revenons sur le tableau d'entiers pour en faire un tableau générique, et nous examinons les conséquences de ce geste sur la résilience de notre code.

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 begin();
   }
   iterator end() noexcept {
      return begin() + size();
   }
   const_iterator end() const noexcept {
      return begin() + size();
   }
   const_iterator cend() const noexcept {
      return end();
   }
   Tableau() = default;
   //
   // Notez que le constructeur ci-dessous peut bénéficier
   // du recours à enable_if pour éviter certaines ambiguïtés
   //
   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;
      }
   }
   //
   // Notez que le constructeur ci-dessous peut bénéficier
   // du recours à enable_if pour éviter certaines ambiguïtés
   //
   Tableau(size_type n, const_reference 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;
      }
   }
   //
   // Notez que le constructeur ci-dessous peut bénéficier
   // du recours à enable_if pour éviter certaines ambiguïtés
   //
   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 = std::exchange(autre.elems, nullptr);
      nelems = std::exchange(autre.nelems, 0);
      cap = std::exchange(autre.cap, 0);
      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.

N'oubliez pas de remettre L00

S04 IFT611, 4 février

Le mots de la semaine : gestion déterministe des ressources. Dans les STR, traditionnellement, l'allocation de ressources (mémoire et autres) tend à être relégué au rang des opérations indéterministes en temps, à juste titre, donc devant être réalisées a priori, n'étant pas à propos pour les tronçons assujettis à des contraintes TR. Cependant, lorsque nous connaissons le contexte, il est parfois possible de faire de petits miracles.

Au menu :

  • Q02
  • Retour sur Q02, avec une brève discussion des options que cette question soulève
  • Discussion sommaire sur les pointeurs intelligents (voir smart_ptr.pdf pour la présentation électronique sur le sujet)

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 = unique_ptr<T>{ 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)
S04 INF749, 5 février

Le mots de la semaine : gestion déterministe des ressources. Dans les STR, traditionnellement, l'allocation de ressources (mémoire et autres) tend à être relégué au rang des opérations indéterministes en temps, à juste titre, donc devant être réalisées a priori, n'étant pas à propos pour les tronçons assujettis à des contraintes TR. Cependant, lorsque nous connaissons le contexte, il est parfois possible de faire de petits miracles.

Au menu :

  • Q02
  • Retour sur Q02, avec une brève discussion des options que cette question soulève
  • Discussion sommaire sur les pointeurs intelligents (voir smart_ptr.pdf pour la présentation électronique sur le sujet)

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 = unique_ptr<T>{ 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)
S05 IFT611, 11 février

Au menu :

L'exemple avec détection de fuites est disponible sur ../../../Sources/Detection-Fuites.html, mais prenez soin d'aller jusqu'en bas de la page vers laquelle mène ce lien pour ne pas oublier de détails importants!

S05 INF749, 12 février

Au menu :

  • Q03
  • Premiers pas dans la gestion intelligente de la mémoire (suite) :
    • spécialisation des services de C++ :
      • 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

L'exemple avec détection de fuites est disponible sur ../../../Sources/Detection-Fuites.html, mais prenez soin d'aller jusqu'en bas de la page vers laquelle mène ce lien pour ne pas oublier de détails importants!

S06 IFT611, 18 février

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

S06 INF749, 19 février

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

S07 IFT611, 25 février

Au menu :

  • Q04
  • 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
  • Retour sur Q02 et introduction de constexpr
  • Introduction aux templates variadiques
  • Fold Expressions

Semaine des intras. Si vous l'acceptez, nous tiendrons une séance (humaine!) cette semaine malgré tout, pour éviter de vous surcharger plus tard dans la session

S07 INF749, 26 février

Au menu :

  • Q04
  • 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
  • Retour sur Q02 et introduction de constexpr
  • Premiers pas dans la gestion intelligente de la mémoire (suite) :
4 mars

Relâche au campus principal. Reposez-vous un peu, vous en avez sûrement besoin!

S08 INF749, 5 mars

Au menu :

S08 IFT611, 11 mars

Au menu :

  • Q05
  • Parenthèse sur les union, particulièrement les union étiquetés
  • Parenthèse sur std::launder()
  • Références de relais et Perfect Forwarding
  • 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())
S09 INF749, 12 mars

Pour des raisons logistiques (petit groupe avec absents ponctuels), nous avons collectivement convenu de ne pas tenir de séance in vivo ce soir.

Je vous ai par contre invités à visionner https://www.youtube.com/watch?v=DILRZvxIGMI par le toujours pertinent Dan Saks d'ici la séance S10

S09 IFT611, 18 mars

Au menu :

Le cours devra terminer un peu plus tôt qu'à l'habitude car votre chic prof doit faire un peu de promotion pour le tout aussi chic DDJV, un programme de 2e cycle offert par le campus Longueuil de votre non-moins chic Alma Mater 

S10 INF749, 19 mars

Au menu :

  • Parenthèse sur les union, particulièrement les union étiquetés
  • Parenthèse sur std::launder()
  • Références de relais et Perfect Forwarding
  • 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())
S10 IFT611, 25 mars

Au menu :

Si vous souhaitez présenter votre projet de session lors des séances S11, S12 ou S13, écrivez un courriel à votre chic prof indiquant :

  • La date que vous préféreriez utiliser (les cases horaires seront attribuées sur la base « premier arrivé, premier servi »)
  • Les noms des équipières et des équipiers impliqué(e)s dans la présentation
  • Une courte phrase descriptive pour que votre présentation soit annoncée sur le présent site

Je vous rappelle que cette courte présentation (≈15 minutes, en polarisant les efforts vers ce qui touche notre cours, en plus de questions), si vous choisissez de la faire, comptera pour un minitest supplémentaire 

S11 INF749, 26 mars

Au menu :

S11 IFT611, 1er avril

Au menu :

S12 INF749, 2 avril

Au menu :

 

S12 IFT611, 8 avril

Le verglas a ruiné cette séance...

S13 INF749, 9 avril

Le verglas a ruiné cette séance...

S13 IFT611, 15 avril, à 18 h

Séance hors-normes (chut!). Au menu : présentations de :

  • Samuel Proulx et Jessica Gosselin, à propos de la stabilisation d'une application serveur temps réel distribuée
  • Nathan Painchaud et Jérémie Bigras-Dunberry, qui présenteront leur simulateur de trafic en Rust. Ils ont développé un serveur d'entrées / sorties non-bloquantes pour ne pas ralentir le moteur de la simulation
  • Daniel-Junior Dubé, qui...

Pour le reste :

S14 INF749, 16 avril

Au menu :

Pour le reste :

Aussi, s'il reste du temps (ha!) :

Suite à la séance, vous aurez droit à un chouette examen final en format maison (Take Home), dû aux circonstances exceptionnelles de cette fin de session verglacée

 

22 avril

Lundi de Pâques, congé universitaire

 

 

S14 IFT611, vendredi 26 avril

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

 

 

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 :


Valid XHTML 1.0 Transitional

CSS Valide !