Quelques raccourcis :

420KH2 – Systèmes temps réel (STR)

Ceci est un petit site de support pour le cours 420-KH2-LG – Systèmes temps réel. Notez que plusieurs liens divers sont mis à votre disposition; parmi ceux-ci, soyez particulièrement attentives et attentifs à ceux portant :

Documents sous forme électronique

Cliquez sur cette cible pour le plan de cours, sous forme électronique

Détail des séances en classe

Index des séances théoriques
T00 T01 T02 T03 T04 T05 T06 T07 T08 T09 T10 T11 T12 T13 T14
Date Séance Contenu

22 janvier

L00

Au menu :

À titre de petit bonbon, s'ajoutera un mot sur les sympathiques et Ô combien expressives expressions λ.

Les cours T00 et L00 se déborderont un peu l'un sur l'autre, question de nous permettre de démarrer la session...

24 janvier

T00

Pour vous pratiquer, prenez le code suivant :

#include <iostream>
#include <algorithm>
#include <string>
#include <locale>
using namespace std;
void rendre_majuscule(string &s, const locale &loc) {
   for(string::size_type i = 0; i < s.size(); ++i)
      s[i] = toupper(s[i], loc);
}
int main() {
   enum { NMOTS = 10 };
   string mots[NMOTS];
   for (int i = 0; i < NMOTS; ++i)
      cin >> mots[i];
   const auto &loc = locale{""}; // la culture sur cet ordinateur
   for(int i = 0; i < NMOTS; ++i)
      rendre_majuscule(mots[i], loc);
   for(int i = 0; i < NMOTS; ++i)
      cout << mots[i] << endl;
}

Et modifiez-le pour qu'il :

  • Utilise un std::vector<std::string> plutôt qu'un tableau de std::string
  • Lise autant de mots que l'usager ait choisi d'en entrer. Dans vos tests, vous pourrez provoquer une erreur de lecture à la console en appuyant CTRL+Z quand vous aurez décidé que vous en avez assez. Un mot est ici une séquence de caractères délimitée à la fin par au moins un « blanc » (espace, tabulation, saut de ligne, etc.)
  • Transforme chacun des mots en son équivalent en majuscules, cette fois à l'aide d'un std::for_each() et d'un foncteur. Le constructeur du foncteur vous permettra de capturer le std::locale utilisé comme second paramètre à std::toupper()
  • Affichera chacun des mots sur une ligne distincte à l'aide de std::for_each() et d'un foncteur Afficher, inspiré de celui proposé en classe à la séance T00

Si le coeur vous en dit, essayez de faire la même chose avec des expressions λ, mais conservez une copie de sauvegarde de la version utilisant des foncteurs pour fins de discussion en classe.

Solution avec foncteurs :

#include <iostream>
#include <algorithm>
#include <string>
#include <locale>
#include <vector>
void rendre_majuscule(std::string &s, const std::locale &loc)
{
   using std::string;
   using std::toupper;
   for(string::size_type i = 0; i < s.size(); ++i)
      s[i] = toupper(s[i], loc);
}
class Afficher
{
   std::ostream &os_;
public:
   Afficher(std::ostream &os)
      : os_(os)
   {
   }
   void operator()(const std::string &s)
      { os_ << s << std::endl; }
};
class RendreMajuscule
{
   const std::locale &loc_;
public:
   RendreMajuscule(const std::locale &loc)
      : loc_(loc)
   {
   }
   void operator()(std::string &s)
      { rendre_majuscule(s, loc_); }
};
int main()
{
   using std::cin;
   using std::cout;
   using std::endl;
   using std::locale;
   using std::string;
   using std::vector;
   using std::for_each;
   vector<string> mots;
   for (string mot; cin >> mot; mots.push_back(mot))
      ;
   const locale &loc = locale(""); // la culture sur cet ordinateur
   for_each(mots.begin(), mots.end(), RendreMajuscule(loc));
   for_each(mots.begin(), mots.end(), Afficher(cout));
}

Une solution avec expressions λ serait la suivante. Notez qu'il est possible que Visual Studio 2010 plante à la compilation avec ce code, car il a parfois de la difficulté à gérer les λ; cependant, le code est correct – testez-le avec un compilateur plus récent, comme par exemple celui livré avec Visual Studio 2012 ou une version récente de g++ ou de Clang :

#include <iostream>
#include <algorithm>
#include <string>
#include <locale>
#include <vector>
void rendre_majuscule(std::string &s, const std::locale &loc)
{
   using std::string;
   using std::toupper;
   for(string::size_type i = 0; i < s.size(); ++i)
      s[i] = toupper(s[i], loc);
}
int main()
{
   using std::cin;
   using std::cout;
   using std::endl;
   using std::locale;
   using std::string;
   using std::vector;
   using std::for_each;
   vector<string> mots;
   for (string mot; cin >> mot; mots.push_back(mot))
      ;
   const locale &loc = locale(""); // la culture sur cet ordinateur
   for_each(mots.begin(), mots.end(), [&](string &s) {
      rendre_majuscule(s, loc);
   });
   for_each(mots.begin(), mots.end(), [&](const string &s) {
      cout << s << endl;
   });
}

Autre exercice pertinent : modifiez la fonction rendre_majuscule() pour qu'elle opère sur des itérateurs plutôt que sur des indices.

Solution possible :

void rendre_majuscule(std::string &s, const std::locale &loc) {
   using namespace std;
   for(string::iterator i = s.begin(); i != s.end(); ++i)
      *i = toupper(*i, loc);
}

Autre solution possible (vive auto) :

void rendre_majuscule(std::string &s, const std::locale &loc) {
   using namespace std;
   for(auto i = s.begin(); i != s.end(); ++i)
      *i = toupper(*i, loc);
}

Autre solution possible, si vous incluez <iterator> :

void rendre_majuscule(std::string &s, const std::locale &loc) {
   using namespace std;
   for(auto i = begin(s); i != end(s); ++i)
      *i = toupper(*i, loc);
}

Pour pratiquer un peu, vous êtes invité(e)s à faire les exercices suivants. N'utilisez pas les algorithmes de l'en-tête <algorithm> pour arriver à vos fins (nous voulons nous pratiquer, après tout) :

  • Écrivez un algorithme nommé inverser_elements() qui prend en paramètre une séquence à demi ouverte et inverse l'ordre de ses éléments. Montrez par un programme de test que votre fonction opère correctement sur un tableau de std::string, un vecteur de int et une liste de double, et ce, que le nombre d'éléments soit nul, un, pair ou impair
  • Écrivez un algorithme nommé compter_occurrences() qui prend en paramètre une séquence à demi ouverte et une instance d'un type T donné, qu'on peut comparer à l'aide de == avec les éléments de la séquence, et qui retourne le nombre d'occurrences de cette instance dans la séquence. Montrez par un programme de test que votre fonction opère correctement sur un tableau de std::string, un vecteur de int et une liste de char, et ce, que le nombre d'éléments soit nul, un ou plus, que la valeur recherchée soit dans la séquence ou non. Notez que je n'ai pas demandé d'utiliser une liste de double dans ce cas-ci... Comprenez-vous pourquoi?
  • Écrivez un algorithme nommé compter_si() qui prend en paramètre une séquence à demi ouverte et un prédicat (un prédicat est une opération booléenne) applicable à chaque élément de la séquence, et qui retourne le nombre d'instances dans la séquence pour lesquelles le prédicat s'avère vrai. Montrez par un programme de test que votre fonction opère correctement sur un tableau de std::string, un vecteur de int et une liste de double, et ce, que le nombre d'éléments soit nul, un ou plus, qu'il y ait ou non des instances pour lesquelles le prédicat est vrai. Écrivez au moins deux prédicats distincts (un foncteur et une fonction)

Par la suite (ne trichez pas!), essayez de voir si ces algorithmes sont codés dans <algorithm> (respectivement sous les noms reverse(), count() et count_if(), tous dans l'espace nommé std), et comparez vos implémentations avec celles que vous y trouverez.

Cet exercice étant formatif, un solutionnaire vous sera proposé sous peu.

Cet exercice étant formatif, un solutionnaire a été mis à votre disposition sur Solutions-L00.html.

Pour réaliser les exercices proposés ici, il vous faudra utiliser entre autres les types std::vector et std::list, que vous trouverez dans les en-têtes standards <vector> et <list> respectivement :

  • Le type vector représente une sorte de tableau dynamique, très efficace pour accéder à un élément particulier ou pour ajouter ou enlever un élément à la fin, mais moins efficace pour insérer ou retirer des éléments à d'autres positions.
  • Le type list représente une liste doublement chaînée; les opérations sur elle sont en général plus lentes que sur vector, mais les opérations d'insertion et de suppression à un endroit autre qu'à la toute fin y sont beaucoup plus rapides.

Pour en savoir plus sur les conteneurs standards et sur les algorithmes standards, jetez un coup d'oeil à cet article.

29 janvier

L01

Au menu :

Le TP00 est à remettre au plus tard à la fin de la séance L03.

Petite note importante : puisque la DLL qui alimentera votre programme de données est compilée en 32 bits (configuration x86), il sera important que votre code client – votre programme – soit aussi compilé en 32 bits.

31 janvier

T01

Au menu :

  • Q00
  • Travail sur le TP00
    • si vous avez des questions sur le design de votre programme (en apparence simple, mais plein de subtilités amusantes), n'hésitez pas à les poser!

5 février

L02

Au menu :

7 février

T02

Au menu :

J'ai fait une démonstration des coûts du faux-partage (attention : compilez en 64 bits dû à la taille du vecteur). Le code suit :

#include <mutex>
#include <thread>
#include <vector>
#include <iostream>
#include <chrono>
#include <locale>
#include <future>
#include <random>
#include <algorithm>
#include <numeric>
using namespace std;
using namespace std::chrono;

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

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

12 février

L03

Au menu :

Le TP00 doit être remis au plus tard à la fin de cette séance.

14 février

T03

Au menu :

Le tableau générique auquel nous sommes arrivés (version avec gestion manuelle de la mémoire) va comme suit :

#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;
   }
};

Pour le tableau générique auquel nous sommes arrivés, avec prise en charge de la mémoire à travers un pointeur intelligent :

#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;
      elems = std::move(p);
   }
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;
};

J'ai ensuite présenté (sommairement) les traits, sur lesquels nous reviendrons éventuellement, à partir de std::numeric_limits et à partir de std::iterator_traits, en montrant comment il est possible d'implémenter la fonction std::distance :

#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{}
      );
   }

C'est bien sûr une implémentation possible (il en existe d'autres).

Bonne Saint-Valentin.

C'est aujourd'hui la date limite pour annuler un cours, mais j'espère sincèrement que nous poursuivrons la session ensemble!

Pour vous distraire en mon absence, et pour ne pas perdre la main d'ici la semaine prochaine, voici une petite activité :

  • Exercice formatif. Seul ou par équipe de deux, décrivez une classe file_circulaire représentant une file circulaire de int dont la capacité est fixée à la construction
  • Votre classe doit au minimum offrir les services suivants (vous pouvez faire plus si vous le jugez pertinent) :
    • un constructeur par défaut, créant une file vide d'une capacité par défaut (disons 1024)
    • un constructeur paramétrique, acceptant une capacité en paramètre et créant une file vide ayant cette capacité
    • une méthode size() retournant le nombre d'éléments qui s'y trouvent
    • une méthode capacity() retournant sa capacité
    • une méthode empty() retournant true seulement si elle est vide
    • une méthode full() retournant true seulement si elle est pleine
    • une méthode add() permettant d'ajouter un élément dans la file au point d'insertion courant
    • une méthode remove() permettant d'enlever un élément de la file au point de consommation courant
    • une méthode peek() retournant l'élément qui sera retiré lors du prochain appel à remove()
  • Dans le design de votre classe, cherchez à être le plus efficaces possibles, en termes de temps et d'espace. Prenez aussi soin de réfléchir aux questions suivantes :
    • les choix d'implémentation que vous avez faits sont-ils pertinents? Auriez-vous pu faire mieux? Il est normal de faire des choix, qui favorisent certaines opérations plutôt que d'autres, mais il est sain de se demander si nos choix furent les meilleurs dans les circonstances
    • les types des méthodes et de leurs paramètres sont-ils bien choisis?
    • l'interface de la classe est-elle cohérente (noms, ordre des paramètres, façons de faire, etc.)?
    • quel devrait être le comportement de la méthode add() si la file est pleine?
    • quel devrait être le comportement de remove() si la file est vide?
    • quel devrait être le comportement de peek() si la file est vide?
    • si nous souhaitions partager cette file entre deux threads (un producteur, un consommateur), votre implémentation serait-elle appropriée?
  • Si vous en avez le temps : êtes-vous en mesure de transformer votre file_circulaire de int en file_circulaire<T>? Quelles sont les conséquences de cette transformation?

19 février

L04

Je serai hors du pays pour la rencontre du WG21 à Kona. Si vous le souhaitez, vous pouvez suivre mes aventures sur ../../../Sujets/Orthogonal/wg21-2019-Kona.html

21 février

T04

Je serai hors du pays pour la rencontre du WG21 à Kona. Si vous le souhaitez, vous pouvez suivre mes aventures sur ../../../Sujets/Orthogonal/wg21-2019-Kona.html

26 février

L05

Au menu :

  • 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
  • Début d'un examen des mécanismes de gestion de la mémoire tels que new, delete, new[] et delete[]
  • Nous n'examinerons pas que ceux-ci, alors préparez-vous à une aventure étrange dans la programmation près du matériel

Les cas de surcharge de new, new[], delete et delete[] examinés aujourd'hui incluent :

void *operator new(size_t); // p.ex.: X * p = new X(3, "J'aime mon prof");
void *operator new[](size_t); // p.ex.: X * q = new X[20];
void operator delete(void *); // p.ex.: delete p;
void operator delete[](void *); // p.ex.: delete [] q;

Ce sont les versions « de base », fonctions globales. Quand on remplace ça, ça a un impact sur presque tout alors faut y aller avec prudence.

Nous n'avons pas terminé de couvrir le sujet... 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!

28 février

T05

Au menu :

5 mars

Journée de mise à niveau (cours suspendus)

7 mars

Journée de mise à niveau (cours suspendus).

12 mars

L06

Au menu :

Un code de test possible serait le suivant (à adapter en fonction des noms et des pratiques de gestion d'erreurs que vous aurez choisi d'utiliser) :

#include "file_circulaire.h"
#include <cassert>
#include <algorithm>
#include <iostream>
using namespace std;
int main() {
   file_circulaire ze_file;
   assert(ze_file.empty());
   assert(ze_file.capacity() == file_circulaire::DEFAULT_CAPACITY);
   assert(ze_file.size() == 0);
   int vals[] { 2, 3, 5, 7, 11 };
   for (auto n : vals) ze_file.add(n);
   assert(!ze_file.empty());
   assert(ze_file.capacity() == file_circulaire::DEFAULT_CAPACITY);
   assert(ze_file.size() == end(vals) - begin(vals));
   ze_file = file_circulaire{ 10 };
   for (int i = 0; i < 9; ++i)
      ze_file.add(i + 1);
   assert(!ze_file.empty());
   assert(ze_file.capacity() == 10);
   assert(ze_file.size() == 9);
   try {
      ze_file.add(10);
      cerr << "Ajout dans une file pleine (pas suppose se produire)\n";
   } catch (capacity_overflow &) {
      cout << "file pleine (correct)" << endl;
   }
   while (!ze_file.empty()) {
      cout << ze_file.peek() << endl;
      ze_file.remove();
   }
   try {
      ze_file.peek();
      cerr << "Lecture dans une file vide (pas suppose se produire)\n";
   }  catch (capacity_underflow &) {
      cout << "file vide (correct)" << endl;
   }
   try {
      ze_file.remove();
      cerr << "Suppression dans une file vide (pas suppose se produire)\n";
   } catch (capacity_underflow &) {
      cout << "file vide (correct)" << endl;
   }
}

Avec mon implémentation, j'obtiens ceci :

file pleine (correct)
1
2
3
4
5
6
7
8
9
file vide (correct)
file vide (correct)

Mon implémentation personnelle ressemble à :

#ifndef FILE_CIRCULAIRE_H
#define FILE_CIRCULAIRE_H
#include <vector>
class capacity_overflow {};
class capacity_underflow {};
class file_circulaire {
public:
   using value_type = int;
   using reference = value_type&;
   using const_reference = const value_type&;
private:
   using container_type = std::vector<value_type>;
   container_type buf;
public:
   using size_type = container_type::size_type;
private:
   size_type prod_pt {},
             cons_pt {};
   static size_type next(size_type n, const container_type &c) {
      return (n + 1) % c.size();
   }
public:
   enum : size_type { DEFAULT_CAPACITY = 1024 };
   file_circulaire(size_type cap = DEFAULT_CAPACITY) : buf(cap, value_type{}) {
   }
   size_type size() const noexcept {
      return cons_pt <= prod_pt ? prod_pt - cons_pt : prod_pt + capacity() - cons_pt;
   }
   size_type capacity() const noexcept {
      return buf.capacity();
   }
   bool empty() const noexcept {
      return cons_pt == prod_pt;
   }
   bool full() const noexcept {
      return next(prod_pt, buf) == cons_pt;
   }
   void add(const_reference val) {
      if (full()) throw capacity_overflow{};
      buf[prod_pt] = val;
      prod_pt = next(prod_pt, buf);
   }
   void add(value_type &&val) {
      if (full()) throw capacity_overflow{};
      buf[prod_pt] = std::move(val);
      prod_pt = next(prod_pt, buf);
   }
   void remove() {
      if (empty()) throw capacity_underflow{};
      cons_pt = next(cons_pt, buf);
   }
   reference peek() {
      if (empty()) throw capacity_underflow{};
      return buf[cons_pt];
   }
   const_reference peek() const {
      if (empty()) throw capacity_underflow{};
      return buf[cons_pt];
   }
};
#endif
#include <new>
#include <functional>
#include <vector>
#include <random>
#include <chrono>
#include <numeric>
#include <algorithm>
#include <iostream>
#include <utility>
#include <memory>
#include <cassert>
#include <numeric>
#include <bitset>
using namespace std;
using namespace std::chrono;

namespace kh2 {
   namespace v0 {
      //
      // version archi naïve, qui ne respecte pas les consignes,
      // écrite juste pour que le code de test compile
      //
      class GestionnaireBlocs {
      public:
         GestionnaireBlocs() = default;
         GestionnaireBlocs(const GestionnaireBlocs&) = delete;
         GestionnaireBlocs& operator=(const GestionnaireBlocs&) = delete;
         void * allouer(size_t n) {
            return ::operator new(n); // délègue au new standard
         }
         void liberer(void *p) {
            ::operator delete(p); // délègue au delete standard
         }
         //
         // pour afficher les statistiques
         //
         friend ostream& operator<<(ostream &os, const GestionnaireBlocs &) {
            return os << "Version 0";
         }
      };
   }
}

using kh2::v0::GestionnaireBlocs;

void * operator new(size_t n, GestionnaireBlocs &gb) {
   return gb.allouer(n);
}
void operator delete(void *p, GestionnaireBlocs &gb) {
   return gb.liberer(p);
}

template <int N>
struct moton {
   char _[N] {};
};

template <int N>
pair<void*, function<void(void*)>> creer_moton(GestionnaireBlocs &gb) {
   return {
      new (gb) moton<N>,
      [&gb](void *p) {
         static_cast<moton<N>*>(p)->~moton<N>();
         gb.liberer(p);
      }
   };
}

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

int main() {
   GestionnaireBlocs gb;
   int tres_petits = 0;
   int petits = 0;
   int pas_gros = 0;
   int autres = 0;
   vector<function<pair<void*, function<void(void*)>>(GestionnaireBlocs&)>> ges = {
      [&](GestionnaireBlocs &gb) {
         ++tres_petits;
         return creer_moton<1>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++tres_petits;
         return creer_moton<2>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++tres_petits;
         return creer_moton<4>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++tres_petits;
         return creer_moton<7>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++tres_petits;
         return creer_moton<8>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++tres_petits;
         return creer_moton<31>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++tres_petits;
         return creer_moton<32>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++petits;
         return creer_moton<33>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++petits;
         return creer_moton<50>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++petits;
         return creer_moton<63>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++petits;
         return creer_moton<64>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++pas_gros;
         return creer_moton<65>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++pas_gros;
         return creer_moton<127>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++pas_gros;
         return creer_moton<128>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++autres;
         return creer_moton<129>(gb);
      },
      [&](GestionnaireBlocs &gb) {
         ++autres;
         return creer_moton<200>(gb);
      }
   };
   enum { N = 1'000'000, NTESTS = 100 };
   vector<void *> ptrs;
   vector<function<void(void*)>> deleters;
   ptrs.reserve(N);
   deleters.reserve(N);
   // random_device rd;
   mt19937 prng{ 0 /* rd() */ };
   uniform_int_distribution<decltype(ges.size())> de{ 0, ges.size() - 1 };
   vector<high_resolution_clock::duration> temps_par_test;
   for (auto t = 0; t != NTESTS; ++t) {
      auto [r, dt] = test([&] {
         for (int i = 0; i != N; ++i) {
            auto pos = de(prng);
            auto [ptr, del] = ges[pos](gb);
            ptrs.push_back(ptr);
            deleters.push_back(del);
         }
         for (vector<void*>::size_type i = 0; i != ptrs.size(); ++i) {
            deleters[i](ptrs[i]);
         }
         return 0;
      });
      ptrs.clear();
      deleters.clear();
      temps_par_test.emplace_back(dt);
      cout << '.' << flush;
   }
   auto temps_total = accumulate(
      begin(temps_par_test), end(temps_par_test), high_resolution_clock::duration{}
   );
   if (tres_petits + petits + pas_gros + autres != N * NTESTS)
      cerr << "Erreur suspecte de calcul (ceci ne devrait pas s'afficher)\n";
   cout << "\n\nNombre de tests : " << NTESTS
        << "\nNombre d'allocations par test : " << N
        << "\nNombre de [0,32] bytes) : " << tres_petits
        << "\nNombre de (32,64] bytes : " << petits
        << "\nNombre de (64,128] bytes : " << pas_gros
        << "\nNombre de (128+ bytes : " << autres
        << "\nTemps ecoule (total) : " << duration_cast<milliseconds>(temps_total).count() << " ms."
        << "\nTemps ecoule (moyen par test) : "
        << static_cast<double>(duration_cast<milliseconds>(temps_total).count()) / NTESTS << " ms." << endl;
   cout << gb << endl;
}

14 mars

T06

Au menu :

Bon jour de π!

19 mars

L07

Au menu : je vais devoir m'absenter pour raisons personnelles. Votre petit devoir en mon absence est de regarder et de savourer cette excellente présentation de Sean Parent qu'est C++ Seasoning, en 2013 : https://www.youtube.com/watch?v=qH6sSOr-yk8 (pour les diapos : https://sean-parent.stlab.cc/presentations/2013-09-11-cpp-seasoning/cpp-seasoning.pdf)

21 mars

T07

Vous étiez en grève aujourd'hui, alors la planification de la session a été décalée d'une séance, incluant la remise du TP01

26 mars

L08

Au menu :

  • Q03
  • Q04
  • Travail sur le TP01

Pour celles et ceux intéressé(e)s par des présentations qui font réfléchir, j'ai suggéré Embracing Algorithms par Dave Abrahams : https://developer.apple.com/videos/play/wwdc2018/223/ et Fastware par Andrei Alexandrescu : https://www.youtube.com/watch?v=o4-CwDo2zpg (deux genres complètement différents)

28 mars

T08

Au menu :

Nouvelle importante hier : Yoshua Bengio a remporté le Turing Award de 2018! Immenses bravos!

2 avril

L09

Au menu :

4 avril

T09

Au menu :

9 avril

L10

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

11 avril

T10

Au menu :

  • Travail sur le TP02

16 avril

T11

Au menu :

Prudence : ce mardi est un fait un jeudi (ne vous trompez pas!)

18 avril

s/o

Journée pédagogiques (cours suspendus)

23 avril

L11

Au menu :

  • Techniques Diviser pour règner
    • comparatif d'un tri_bulles() et de d'un tri_fusion()
    • algorithmes Cache-Oblivious
  • Présentation de la PFI
  • Travail sur la PFI

Au cours des prochaines séances, vous travaillerez sur la PFI et j'ajouterai des bribes de matière (et des minitests!) ici et là pour le plaisir.

Pour référence future, le code de comparaison des stratégies de tri suit :

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

template <class It>
   void tri_bulles(It debut, It fin) { // piache O(n * n) == O(n^2)
      for (; debut != fin; ++debut) // O(n)
         for (auto p = next(debut); p != fin; ++p) // O(n)
            if (*p < *debut)
               swap(*p, *debut);
   }

template <class It>
   void tri_fusion(It debut, It fin) { // O(n * log_2 n)
      constexpr int seuil = 100; // arbitraire; mieux vaut mesurer
      auto n = distance(debut, fin);
      if (n < seuil)
         tri_bulles(debut, fin);
      else {
          auto milieu = next(debut, n / 2);
          tri_fusion(debut, milieu);
          tri_fusion(milieu, fin);
          inplace_merge(debut, milieu, fin); // O(n)
      }
   }

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

int main() {
   enum { N = 100'000 };
   vector<int> v(N);
   iota(begin(v), end(v), 1); // 1, 2, 3, ..., N
   cout << "iota() : check" << endl;
   random_device rd;
   mt19937 prng{ rd() };
   shuffle(begin(v), end(v), prng);
   cout << "shuffle() : check" << endl;
   auto [r0, dt0] = test([v]() mutable {
      tri_bulles(begin(v), end(v));
      if (!is_sorted(begin(v), end(v)))
         cerr << "Oups! Erreur dans tri_bulles()\n";
      return 0; // bof
   });
   cout << "tri_bulles() : fait en " << duration_cast<milliseconds>(dt0).count() << " ms." << endl;
   auto [r1, dt1] = test([v]() mutable {
      tri_fusion(begin(v), end(v));
      if (!is_sorted(begin(v), end(v)))
         cerr << "Oups! Erreur dans tri_fusion()\n";
      return 0; // bof
   });
   cout << "tri_fusion() : fait en " << duration_cast<milliseconds>(dt1).count() << " ms." << endl;
   auto [r2, dt2] = test([v]() mutable {
      sort(begin(v), end(v));
      if (!is_sorted(begin(v), end(v)))
         cerr << "Oups! Erreur dans sort()\n";
      return 0; // bof
   });
   cout << "sort() : fait en " << duration_cast<milliseconds>(dt1).count() << " ms." << endl;
}

25 avril

T12

Au menu :

  • Je suis en retard dans mes minitests, alors...
    • Q05
    • Q06
    • ... mais vous pourrez les faire à l'aide de votre éditeur de code favori
  • Pour le reste, travail sur la PFI

30 avril

L12

Au menu :

2 mai

T13

Au menu :

7 mai

L13

Au menu :

9 mai

Journée d'examen pour les cours de français de la formation générale (cours suspendus)

14 mai

L14

Au menu, votre demande pour aujourd'hui est :

« Notre proposition pour la dernière séance serait de mêler la communication avec les contraintes TR : TCP lent mais fiable vs UDP rapide mais désordonné (nous n'avons d'ailleurs pas vue autre que TCP durant nos cours de communication, alors qu'en informatique industrielle, généralement, l'on parle aussi d'UDP), etc.) »

On va voir ce qu'on peut faire avec ça. À suivre...

16 mai

T14

Au menu :

Consignes des travaux pratiques

Les consignes des travaux pratiques sont telles qu'indiqué ci-dessous.

Consignes Document d'accompagnement

TP00

420KH2--TP00.pdf (vous utiliserez aussi l'archive TP00--Consommateur.zip comme base de travail)

TP01

420KH2--TP01.pdf (aussi, voir le code de test proposé à la séance L06, que vous pouvez utiliser si tel est votre souhait – aucune obligation de ma part)

TP02

420KH2--TP02.pdf

Pour vous aider :

  • Outil pour convertir de PPM à RLE (à titre comparatif) : ppm_to_rle.exe
  • Outil pour tirer des statistiques d'un fichier RLE (pour aider au débogage) : rlestat.exe

Notez que ppm_to_rle.exe ne fonctionnera pas avec un fichier PPM contenant des commentaires (j'ai été trop lâche...)
TP « bonbon »

420KH2--TP-bonbon.pdf

Consignes de la PFI

Les consignes de la PFI pour la session H2019 sont disponibles sur : KH2-PFI.html

Code de démonstration

Vous trouverez ci-après le code source de divers exemples de vos notes de cours. Il est possible que le code ne soit pas exactement le même que dans les notes de cours puisque j'ai retouché ces dernières récemment (le site Web est un peu en retard côté mises à jour), mais les différences sont cosmétiques.

Sources des exemples du document STR – Volume 01

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

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

Cliquez sur cette cible pour obtenir le code du test 0.0

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

Cliquez sur cette cible pour obtenir le code du test 0.1

Cliquez sur cette cible pour obtenir le code du test 1.0

Cliquez sur cette cible pour obtenir le code du test 1.1

Cliquez sur cette cible pour obtenir le code du test 1.2

Cliquez sur cette cible pour obtenir le code du test 1.3

Cliquez sur cette cible pour obtenir le code du test 2.0

Cliquez sur cette cible pour obtenir le code du test 2.1

Cliquez sur cette cible pour obtenir le code du test 2.2

Cliquez sur cette cible pour obtenir le code du test 3.0

En lien avec la 1re séance sous QNX

Pour la 1re séance sous QNX, vous trouverez le code source des illustrations à travers les liens suivants :

Pour l'aide en ligne de QNX au sens large, je vous invite à consulter le site http://www.qnx.com/developers/docs/6.3.2/neutrino/lib_ref/about.html qui est, somme toute, assez complet. Vous y trouverez un certain nombre de tutoriels pertinents, entre autres :

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/

Valid XHTML 1.0 Transitional

CSS Valide !