Vous oeuvrez sur le projet de jeu Beurk et Orques® qui met en conflit des Orques et des Elfes, et vous souhaitez spécialiser les mécanismes tels que new, new[], delete et delete[] pour tenir compte du fait que, lors de la bataille finale entre le mal et le bien, le nombre maximal d'instances d'Orque en circulation sera connu d'avance (une constante statique).
Un premier jet de ces mécanismes a été développé par vos collègues. Dans ce premier jet, votre implémentation de ces opérateurs est plus rapide que celle du standard. Les hypothèses de travail de ce premier jet sont contraignantes :
Un fichier de configuration accompagne votre projet. Ce fichier vous permet entre autres de compiler votre programme en utilisant les mécanismes standards d'allocation dynamique de mémoire ou encore en utilisant vos versions personnalisées de ces mécanismes.
#ifndef CONFIG_H
#define CONFIG_H
#define ALLOC_MAISON // commentez cette ligne pour utiliser les mecanismes standards
#ifdef ALLOC_MAISON
static constexpr auto CFG_STR = "Utilise les mecanismes maison";
#else
static constexpr auto CFG_STR = "Utilise les mecanismes standards";
#endif
#endifPar souci de simplicité (si vous le souhaitez), vous avez aussi accès à la classe Incopiable (omise ici car évidente à ce stade).
Le programme de test existant va comme suit.
#include "Orque.h"
#include <chrono>
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
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() {
cout << "Test sur " << Orque::NB_MAX << " Orques, " << CFG_STR << endl;
vector<Orque*> orques(Orque::NB_MAX);
auto [r0,dt0] = tester([&orques] {
for (int i = 0; i < Orque::NB_MAX; ++i)
orques[i] = new Orque{ "Orque #" + std::to_string(i + 1), new Guerrier };
return orques.size(); // pour éviter une lambda void
});
cout << "Temps total pour creer " << orques.size() << " orques: "
<< duration_cast<milliseconds>(dt0).count() << " ms." << endl;
auto [r1,dt1] = tester([&orques] {
for (auto p : orques)
delete p;
return orques.size(); // pour éviter une lambda void
});
cout << "Temps total pour detruire " << orques.size() << " orques: "
<< duration_cast<milliseconds>(dt1).count() << " ms." << endl;
}Il s'agit évidemment d'un programme de test très limité, mais qui démontre que, dans une situation simpliste, votre stratégie est compétitive avec celle mise en place à l'aide des mécanismes standards.
La classe Orque se décline a priori comme suit.
#ifndef ORQUE_H
#define ORQUE_H
#include "config.h"
#include <string>
#include <random>
#include <memory>
#include <cassert>
class Outil;
class Personnage;
struct Metier {
virtual void agir(Personnage&) {}
virtual void utiliser(Outil&) {}
virtual ~Metier() = default;
};
class chomeur {};
class Personnage {
std::string nom_;
int vie_;
static int generer_vie(int minval, int maxval) {
using namespace std;
static mt19937 prng{ random_device{}() }; // pas Thread-Safe, mais bon...
assert(minval <= maxval);
return uniform_int_distribution<int>{ minval, maxval }(prng); // discutable
}
std::unique_ptr<Metier> metier_;
public:
Personnage(const std::string &nom, int vie_min, int vie_max, Metier *metier = {})
: nom_{ nom }, vie_{ generer_vie(vie_min, vie_max) }, metier_{ metier }
{
}
Metier& metier() const {
if (!metier_) throw chomeur{};
return *metier_;
}
void blesser(int degats) {
assert(degats >= 0);
vie_ -= degats;
}
void guerir(int degats) {
assert(degats >= 0);
vie_ += degats;
}
bool est_mort() const {
return vie_ <= 0;
}
};
struct Chamane : Metier {
void agir(Personnage &p) {
p.guerir(10);
}
};
struct Guerrier : Metier {
void agir(Personnage &p) {
p.blesser(15);
}
};
class Orque final : public Personnage {
float puanteur_;
static float generer_puanteur() {
using namespace std;
static mt19937 prng{ random_device{}() };
static uniform_real_distribution<float> distrib{ 0, 1 };
return distrib(prng);
}
public:
enum { NB_MAX = 10'000'000, VIE_MIN = 1, VIE_MAX = 100 };
Orque(const std::string &nom, Metier *metier)
: Personnage{ nom, VIE_MIN, VIE_MAX, metier }, puanteur_{ generer_puanteur() }
{
}
// etc.
#ifdef ALLOC_MAISON
void *operator new(std::size_t);
void *operator new[](std::size_t);
void operator delete(void *);
void operator delete[](void *);
#endif
};
class pas_implemente {};
#endifÉtant donné les contraintes mentionnées plus haut, pour le moment :
Cependant, on vous explique que ces hypothèses contraignantes ne tiendront pas en pratique, car bien que toutes les instances d'Orque aient présentement pour métier celui du guerrier, il est possible que certaines instances d'Orque aient éventuellement un rôle de chamane et puissent ramener d'autres instances d'Orque à la vie. Notez que chamane est une profession pour un Orque, pas une classe dérivée de la classe Orque; votre classe Orque est terminale, et n'aura donc jamais d'enfants.
L'implémentation actuelle de la classe Orque et de ses services va comme suit.
#include "Orque.h"
#include "config.h"
#include <random>
#include <new>
#include <cassert>
#include <cstdlib>
#include <memory>
using namespace std;
class Arena {
unique_ptr<char[]> p;
Orque *cur;
Arena() : p{ new char[sizeof(Orque) * Orque::NB_MAX] } {
cur = reinterpret_cast<Orque*>(p.get());
}
public:
static Arena& get() {
static Arena singleton;
return singleton;
}
~Arena() = default;
void* allouer() {
return cur++;
}
};
#ifdef ALLOC_MAISON
void* Orque::operator new(size_t n) {
assert(n == sizeof(Orque));
return Arena::get().allouer();
}
void* Orque::operator new[](size_t) {
throw pas_implemente{};
}
void Orque::operator delete(void*) {}
void Orque::operator delete[](void*) {}
#endifVotre travail va comme suit : seul(e) ou par équipe de deux personnes, raffinez le code existant pour tenir compte des suppositions suivantes :
Le code que vous aurez retouché devra permettre d'exécuter un programme comme le suivant, sans planter et, idéalement, à une vitesse comparable (ou meilleure!) à celle des mécanismes d'allocation livrés avec votre implémentation de la bibliothèque standard.
#include "Orque.h"
#include <chrono>
#include <iostream>
#include <algorithm>
#include <vector>
#include <random>
#include <utility>
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 };
}
template <class T>
bool kill_with_last_swap(vector<T> &v, typename vector<T>::size_type n) {
using std::swap;
if (n >= v.size() || !v[n]) return false;
swap(v[n], v.back());
delete v.back();
v.pop_back();
return true;
}
int main() {
mt19937 prng { random_device{}() };
cout << "Test sur " << Orque::NB_MAX << " Orques, " << CFG_STR << endl;
vector<Orque*> orques(Orque::NB_MAX);
auto [r0,dt0] = tester([&orques] {
for (int i = 0; i < Orque::NB_MAX; ++i)
orques[i] = new Orque{ "Orque #" + std::to_string(i + 1), new Guerrier };
return orques.size(); // pour éviter une lambda void
});
cout << "Temps total pour creer " << orques.size() << " orques: "
<< duration_cast<milliseconds>(dt0).count() << " ms." << endl;
//
// ICI, CARNAGE!!!
//
enum { NB_EVENEMENTS = 10'000'000 };
uniform_int_distribution<vector<Orque>::size_type> distrib{0, orques.size() - 1};
uniform_int_distribution<int> d5{0,4};
int nmorts = 0, nressu = 0;
auto [r1,dt1] = tester([&] {
for(int i = 0; i < NB_EVENEMENTS; ++i) {
switch(d5(prng)) { // bof
case 0: case 1 : case 2: // mort!
{
auto n = distrib(prng);
if (kill_with_last_swap(orques, n))
++nmorts;
}
break;
case 3: case 4: // sauve!
if (orques.size() < Orque::NB_MAX) {
orques.push_back(new Orque{ "Orque ressucite", new Guerrier });
++nressu;
}
break;
}
}
return orques.size(); // pour éviter une lambda void
});
cout << "Temps total pour tuer " << nmorts << " orques et creer " << nressu << " orques: "
<< duration_cast<milliseconds>(dt1).count() << " ms." << endl;
auto [r2,dt2] = tester([&orques] {
for (auto p : orques)
delete p;
return orques.size(); // pour éviter une lambda void
});
cout << "Temps total pour detruire " << orques.size() << " orques: "
<< duration_cast<milliseconds>(dt2).count() << " ms." << endl;
}Note importante
Si vous essayez le programme de test proposé pour l'activité, avec l'Arena de base, le programme plantera, et c'est normal puisque la version de base, naïve de l'Arena ne récupère pas les espaces rendus disponibles lors d'un appel à delete.
C'est suite à vos efforts que le programme pourra éventuellement fonctionner.
Je veux le code du fichier Orque.cpp, de même que tout fichier auxiliaire que vous aurez vous-même codés. Assurez-vous que les noms de tous les auteurs soient dans les commentaires débutant chaque fichier.
Je compterai ce travail comme deux minitests. Ainsi, la note sera calculée sur dix et sera divisée en deux parties égales, une pour chaque minitest.
Les points seront donnés comme suit :
| Particularité |
Points |
|---|---|
Le mécanisme d'allocation fonctionne et ne fuit pas |
|
Sur une série de dix exécutions du programme de test (dans une boucle, pas lors de dix lancements manuels!), votre mécanisme est plus rapide que le standard pour l'allocation et pour la libération au moins sept fois sur dix |
|
Qualité générale du code (programmatique et tout le tralala) |
|
Petit texte analysant de stratégie que vous avez choisi d'appliquer pour la gestion de votre aréna : quel est le coût en mémoire de votre approche? Quels sont ses avantages? Ses inconvénients? Quelles auraient été, selon vous, des alternatives intéressantes à explorer? |
Il y a toujours des avantages et des inconvénients à une stratégie d'allocation dynamique de mémoire. C'est pourquoi il vaut mieux analyser notre stratégie et comprendre dans quelles circonstances elle serait avantageuse, dans l'optique de l'utiliser judicieusement.
Ne faites ce qui suit que si la première tâche est complétée. Ce qui suit peut vous donner un de points bonis, mais c'est plus difficile.
Notez que pour réaliser cette tâche, il vous faudra ajouter un constructeur par défaut à la classe Orque.
Ajoutez à votre classe Orque un support pour l'allocation et la libération de tableaux.
En faisant ceci, vous vivrez de la fragmentation de mémoire. Conséquemment, ajoutez (sur une base optionnelle, par exemple avec support à la compilation conditionnelle du style #ifdef DEBUG) un service permettant de connaître le taux de fragmentation de votre aréna, de même que la taille du plus gros bloc qui y reste disponible. Assurez-vous que lorsque le programme se termine, ces informations (taille du plus gros bloc disponible, taux de fragmentation) soient écrites dans un fichier de journalisation (Log File) pour consultation ultérieure.
Il arrive qu'une implémentation demande, pour les tableaux, plus de mémoire que le minimum requis. Je suspecte que ce soit pour insérer un marqueur à la fin du bloc pour vérifier les débordements, mais ce n'est qu'une hypothèse.
Ça a aussi comme conséquence que les tableaux brisent un peu le schème chouette que nous avions et qui tenait compte de la taille des éléments à entreposer. Si vous comptez faire le bonus, faudra que votre solution ne soit pas rattachée à une supposition sur la taille des éléments (ou qu'elle tienne compte du fait que c'est un quatre bytes de plus, mais certains compilateurs... Ce n'est pas une donnée portable).
Je vous rappelle que c'est un bonus, pas une obligation. Bizous!
