Discussion :

[germinolegrand]

Sean Parent - C++ Seasoning
GoingNative 2013

La conférence de Sean Parent lors des GoingNative 2013 est disponible :

Rediffusion de la conférence

Sean Parent propose trois objectifs à viser lors de l'écriture de code C++ :


Pas de boucle brute

Une boucle brute est une boucle dans une fonction qui fait plus que l'algorithme de la boucle lui-même.

Ces boucles rendent la compréhension du code difficile, son analyse ardue, ce qui a pour conséquence de générer un code prompt à l'erreur, particulièrement dans les cas qui ne sont pas évidents, et dont les problèmes de performances sont difficiles à résoudre.

Quelles solutions ?

• Utilisez un algorithme existant, standard de préférence s'il est disponible.
• S'il n'est pas disponible, écrivez-le en tant que fonction générale.
• Il serait bénéfique que chacun essaye de contribuer à une bibliothèque (de préférence open-source) en soumettant au moins un algorithme par an.
• Si vous inventez un algorithme, écrivez un papier, faites des conférences, devenez célèbres ! Il n'y a rien de négatif à cela, bien que cela risque d'être extrêmement rare.

Un des plus grands problèmes est que les développeurs C++ ne connaissent pas leurs algorithmes : prenez du temps, apprenez-les, c'est vital ! Vous gagnerez du temps, des performances, de la lisibilité, de la sécurité.

Apprenez ce qu'ils font, apprenez à les reconnaître, apprenez à jouer avec en réduisant itérativement la complexité de votre code.

Le code généré sera également considérablement plus évolutif.


Pas de primitives de synchronisation brutes

Les primitives de synchronisation en question sont des mutex, des atomic, des sémaphores, des barrières.

Vous avez un pourcentage de chance extrêmement élevé de vous tromper, générant des erreurs du genre le plus teigneux : les data race ponctuelles (une ou deux fois par semaine, votre application va crasher, amusez-vous à débuguer ).

De plus, si vous voulez que vos performances augmentent le plus proportionnellement possible au nombre de cœurs, la synchronisation n'est pas votre alliée.

Il faut penser en termes de tâches asynchrones. Le standard ne fournit malheureusement aucun outil pour ceci actuellement.

S. Parent donne quelques clés pour disposer d'outils de base.


Pas de pointeurs bruts

Un pointeur brut peut être ici :

• T* p = new T
• std::unique_ptr<T>
• std::shared_ptr<T>

On utilise les pointeurs pour un nombre conséquent de raisons. Très peu se justifient, notamment dans les interfaces. On doit être capable de manipuler des Objets, sans passer par des pointeurs bruts.

Pour les conteneurs, on dispose déjà de conteneurs non-intrusifs dans la STL, il n'est ainsi pas nécessaire d'hériter d'une classe Node pour être stocké dans un std::vector.

Le problème se pose pour le polymorphisme dynamique où l'on commence à vouloir ajouter une classe de base pour la hiérarchie afin de pouvoir la stocker, alors qu'il est possible de le faire de façon non-intrusive, ainsi que Sean Parent va le montrer dans ce code :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class object_t {
  public:
    template<typename T> // T models Drawable
    object_t(T x) : self_(make_shared<model<T>>(move(x)))
    { }
    void draw(ostream& out, size_t position) const
    { self_->draw_(out, position); }
 
  private:
    struct concept_t {
        virtual ~concept_t() = default;
        virtual void draw() const = 0;
    };
 
    template <typename T>
    struct model : concept_t {
        model(T x): data_(move(x)) { }
        void draw(ostream& out, size_t position) const
        { data_.draw(out, position); }
 
        T data_;
    };
 
    shared_ptr<const concept_t> self_; // [Ndlr] une copie de shared_ptr<const> copie l'objet contenu
};
 
using document_t = vector<object_t>;
 
void draw(const document_t& x, ostream& out, size_t position)
{
    out << string(position, ' ') << "<document>" << endl;
    for (const auto& e : x) e.draw(out, position + 2);
    out << string(position, ' ') << "</document>" << endl;
}

Les shared_ptr ne valent pas mieux que des globales : il devient impossible de résonner de façon locale sur le code, deux morceaux de code indépendants travaillent sur la même portion de mémoire.

Il faut garder la possibilité de raisonner localement : le code sera plus simple à analyser, plus facile à intégrer, plus généraliste, plus correct, plus efficace.

Sean Parent donne plus d'informations sur cette approche dans sa deuxième conférence intitulée Inheritance is the base class of Evil, "L'héritage est la classe mère du Vice" (résumé à venir prochainement).

Conférence précédente : Bjarne Stroustrup - L'Essence du C++

Évènement : GoingNative 2013

Conférence suivante : Andrei Alexandrescu - Ecrire du code rapide en C++, rapidement

Et vous,
Qu'en pensez-vous ?

[Luc Hermitte]

À noter aussi l'exemple didactique d'un refactoring de code dans le sujet "pas de raw for". Si on prend une liste d'éléments contigus (des random access containers), deux questions de réorganisation des éléments :
1- comment remonter (/descendre) un ensemble contigus d'éléments dans la liste ? -> avec std::rotate
2- comment prendre un ensemble non contigus d'éléments, et les déplacer ailleurs et les rendre contigus ? -> avec std::stable_partition.

D'où le "know your algorithms".
C'est une des meilleures illustrations du conseil, "utiliser les algorithmes standards" que j'ai pu voir. Souvent, on se cantonne à des for-each, des find_if faits à la main (à cause du besoin de l'écriture lourde des foncteurs), au mieux on utilise des std::sort. Là, on voit une mise en oeuvre d'un algo pas si trivial, et d'une façon efficace qui aura des impacts bénéfiques sur les performances.

[CedricMocquillon]

Pas de pointeurs bruts

Un pointeur brut peut être ici :

• T* p = new T
• std::unique_ptr<T>
• std::shared_ptr<T>

J'ai personnellement du mal à voir comment ça peut être compatible si on a des objets à sémantique d'entité qui sont référencés par d'autres (type association UML) : il faut bien un lien entre la personne et ses magasines (on aura un truc comme un vector<Magazine*> ou vector<std::shared_ptr<Magazine>>). Je vois pas comment on peut s'en passer à moins de ne pas travailler avec des objets à sémantique d'entité (ce qui est peut être le cas de Sean Parent)

[PilloBuenaGente]

"on aura un truc comme un vector<Magazine*> ou vector<std::shared_ptr<Magazine>>"

Ou bien vector< magazine_id > avec map< int, Magazine >
#edit Ou bien map< Magazine_id, Magazine >

[CedricMocquillon]

@PilloBuenaGente je comprend pas bien ton édit, si on a deux classes comme l'exemple de Wikipedia: Person et Magazine et que l'on veut lister les magazines auxquels une personne est abonnée, soit on stocke dans Person les références aux magazines soit on passe comme tu l'indiquais par des id.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
class Person
{
public:
  void add(Magazine* m) { magazines_m.push_back(m); }
  std::vector<Magazine*> const& magazines() const { return magazines_m; }
private:
  std::vector<Magazine*> magazines_m;
};

ou

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
class Person
{
public:
  typedef size_t magazine_id_t;
 
  void add(magazine_id_t m) { magazines_m.push_back(m); }
  std::vector<magazine_id_t> const& magazines() const { return magazines_m; }
private:
  std::vector<magazine_id_t> magazines_m;
};

Par contre maintenant si je veux lister les titres des magazines auxquels une personne est abonnée, par ta méthode c'est bien plus lourd puisqu'il faut que je connaisse le manager (au sens informatique) des magazines. De plus on passe d'un accès en temps constant (O(1)) à un accès en temps logarithmique (la recherche dans la map) ce qui n'est vraiment pas efficace.

[JolyLoic]

J'ai personnellement du mal à voir comment ça peut être compatible si on a des objets à sémantique d'entité qui sont référencés par d'autres (type association UML) : il faut bien un lien entre la personne et ses magasines (on aura un truc comme un vector<Magazine*> ou vector<std::shared_ptr<Magazine>>). Je vois pas comment on peut s'en passer à moins de ne pas travailler avec des objets à sémantique d'entité (ce qui est peut être le cas de Sean Parent)

Dans son cas, il avait des objets dont il aurait aimé que la sémantique soit une sémantique de valeur, mais pour lesquels il voulait un comportement polymorphe. Le fait de les gérer par pointeur et de dire "maintenant, ils ont une sémantique d'entité" le gênait.

Sa solution s'approche un peu des value_ptr, clone_ptr ou autres (il la développe dans sa deuxième présentation), mais avec la différence qu'il n'impose pas de dériver d'une classe de base. J'avoue que je suis assez tenté de l'essayer à la prochaine occasion.

[koala01]

J'ai personnellement du mal à voir comment ça peut être compatible si on a des objets à sémantique d'entité qui sont référencés par d'autres (type association UML) : il faut bien un lien entre la personne et ses magasines (on aura un truc comme un vector<Magazine*> ou vector<std::shared_ptr<Magazine>>). Je vois pas comment on peut s'en passer à moins de ne pas travailler avec des objets à sémantique d'entité (ce qui est peut être le cas de Sean Parent)

A vrai dire, dés que l'on parle d'entité, on parle d'objet identifiable "de manière unique et non ambigüe".

Bien sûr, l'adresse d'un objet est une des manières qui permettent une telle identification, mais, de manière générale, il y a toujours certaines données qui représentent cette unicité référentielle :

Que ce soit le numéro d'un compte bancaire, le numéro IBAN d'un livre, le numéro de sécu d'une personne ou le numéro de série d'autre chose, tu trouveras toujours une donnée qui te permettra de dire que c'est cet objet là en particulier qui t'intéresse et non celui qui se trouve juste à coté.

Il n'y a strictement rien qui t'oblige à utiliser un (pointeur sur l') objet associé pour représenter l'association : tu peux parfaitement te contenter d'utiliser cet identifiant unique.

C'est d'ailleurs généralement beaucoup plus efficace dans le sens où les associations sont souvent bidirectionnelles et de type "un à plusieurs" : chaque personne peut être abonnée à 0 ou plusieurs magazines, mais chaque magazine peut avoir 0 à plusieurs abonnés.

En ne plaçant que l'identifiant unique du magazine (au niveau de la personne) ou de la personne (au niveau du magazine), voire, en créant une abstraction supplémentaire (qui peut être utilisé comme identifiant unique) qui représente à chaque fois la relation entre une personne bien particulière et un magazine bien particulier, tu te facilite énormément le travail de recherche.

Note d'ailleurs que c'est l'une des règles à respecter au niveau des BDD pour pouvoir dire qu'elles sont normalisées (même si je ne sait plus le niveau de normalisation )

[CedricMocquillon]

Je commence à douter de l'approche que j'ai de cette problématique:
Si on prend l'exemple Person / Magazine avec une association plusieurs à plusieurs, on a plusieurs approches possibles:
Celle que j'utilise jusqu'à maintenant utilise des pointeurs, j'ai également un manager de personnes et de magazines qui est utilisé lors de la lecture des data pour mettre à jour les relations. Niveau code ça donne en gros ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
class Person
{
public:
  typedef std::size_t id_type;
  typedef std::vector<std::shared_ptr<Magazine>> magazines_t;
 
  Person(id_type id) : id_m(id) {}
 
  id_type id() const { return id_m; }
 
  void add_magazine(std::shared_ptr<Magazine> const& m) { magazines_m.push_back(m); }
 
  magazines_t const& magazines() const { return magazines_m; }
private:
  id_m;
  magazines_t magazines_m;
};

et la classe magazine

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
class Magazine
{
public:
  typedef std::size_t id_type;
  typedef std::vector<std::shared_ptr<Person>> persons_t;
 
  Magazine(id_type id, std::string title) : id_m(id), title_m(std::move(title) {}
 
  id_type id() const { return id_m; }
 
  std::string const& title() const { return title_m; }
 
  void add_person(std::shared_ptr<Person> const& p) { persons_m.push_back(p); }
 
  persons_t const& persons() const { return persons_m; }
private:
  id_type id_m;
  std::string title_m;
  persons_t persons_m;
};

au niveau des managers, j'ai ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
 
class MagazineManager
{
  typedef Magazine::id_type magazine_id_t;
public:
  void add_magazine(std::shared_ptr<Magazine> const& m) { magazines_m[m->id()] = m; }  //avec en plus une gestion des collisions de clef avec levée d'exception
 
  std::shared_ptr<Magazine> const& get_magazine(magazine_id_t const& id) { return magazines_m[id]; } //avec en plus gestion des magazines manquant avec levée d'exception
 
private:
 
  std::map<magazine_id_t, std::shared_ptr<Magazine>> magazines_m;
};
 
class PersonManager
{
  typedef Person::id_type person_id_t;
public:
  void add_person(std::shared_ptr<Person> const& p) { persons_m[p->id()] = p; }  //avec en plus une gestion des collisions de clef avec levée d'exception
 
  std::shared_ptr<Person> const& get_magazine(person_id_t const& id) { return persons_m[id]; } //avec en plus gestion des magazines manquant avec levée d'exception
 
private:
 
  std::map<person_id_t, std::shared_ptr<Person>> persons_m;
};

au niveau de la lecture des données, j'ai effectivement besoin que la base soit normalisée, j'ai donc trois tables: Person, Magazine, et Subscriptions. Je commence par peupler mes managers avec les tables person et magazine ensuite lors de la lecture des subscriptions, ça donne en gros ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void read_subscription(std::istream& in, PersonManager const& pm, MagazineManager const& mm)
{
  //lectures des données de la base  
  Person::id_type id_p;
  Magazine::id_type id_m;
  in >> id_p >> id_m;
 
  //récupération des entités via les managers
  auto const& person = pm.get_person(id_p);
  auto const& magazine = mm.get_magazine(id_m);
 
  //mise à jour des relations entre les entités
  person.add_magazine(magazine);
  magazine.add_person(person);
}

Voila pour mon approche, maintenant, on peut effectivement passer par des identifiants uniques: au niveau de la classe Person, on aurait donc une liste d'identifiants de Magazine (donc une liste de Magazine::id_type) et non plus directement les références (au sens large du terme) directes aux objets. L'inconvénient que je vois à cette approche (mais bon j'ai pas trop de recul ;-) ) c'est que pour lister les magazines d'une personne, je vais avoir besoin en plus de la personne, du manager de magazines (sinon comment avoir les objets magazines). Pour moi, je vais passer de ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for(auto const& m: p->magazines())
  std::cout << m->title() << '\n';

à quelque chose comme ça:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
for(auto const& idm : p->magazines())
  std::cout << mm.get_magazine(idm)->title() << '\n';  //avec mm le MagazineManager

La différence d'écriture n'est pas en soit très importante (en plus ça dépend fortement du choix de nommage) mais par contre je passe d'un accès en O(1)*le nombre de magazines de la personne à un accès en O(log n)*le nombre de magazines de la personne avec n le nombre de magazines dans la Bd!
On pourrait toujours essayer de "limiter la casse" au niveau du manager (en utilisant par exemple des unordered_map) mais on aura toujours un overhead non négligeable.

[Arzar]

Attention quand même, dans la conférence Sean Parent utilise une définition assez spécial de pointeur brut. Pour lui un pointeur brut est "a pointer to an object with implied ownership and reference semantics". Par exemple pour lui, std::unique_ptr et std::shared_ptr sont des pointeurs bruts.

Donc il ne met pas en cause les pointeurs d'association, en fait il n'en parle pas du tout.

[Iradrille]

@CedricMocquillon

Si tes managers possèdent les magazines / personnes, pourquoi avoir des shared_ptr dans tes magazines / personnes ? Des weak_ptr auraient ici leurs utilités.

Ça sens les références cycliques à plein nez, attention.

edit: ou des unique_ptr dans tes managers, et des pointeurs nus dans magazines / personnes.

[koala01]

Sans compter que je ne vois pas en quoi un accès en temps constant(en o(1) ) peut t'apporter quoi que ce soit.

En effet, à moins de savoir que tu veux atteindre le 105eme abonné à un magazine ou le 3emeabonnement d'une personne, l'accès en temps constant ne te sera d'aucune utilité.

Or, justement, pour pouvoir dire que c'est le 105eme abonné à au magazine ou le 3eme abonnement d'une personne, tu auras du... recherché l'abonné ou l'abonnement en question.

Et, si tu ne veux pas devoir passer potentiellement l'ensemble des abonnés / abonnements en revue pour trouver celui qui t'intéresse, il faudra maintenir un tableau trié, histoire par exemple de pouvoir faire une recherche dichotomique (et gagner un peu de temps)

Or, quelle que soit la solution choisie pour garder un tableau trié après insertion, elle est clairement moins efficace que ce que les solutions basées sur des arbres binaires sont susceptibles de donner.

Dés lors, pourquoi ne pas utiliser des structures qui vont bien, comme boost.multi_index qui te permettraient, en une seule collection, d'avoir comme index "primaire" la composée des deux identifiants (personne + magazine) et deux index "secondaires" qui seraient l'identifiant du magazine pour l'un et celui de l'abonné pour l'autre

A priori, comme tu feras beaucoup plus de recherches que n'importe quoi d'autre, tu as tout à gagner à séparer les différentes informations.

Et ce, d'autant plus que cela participe au respect du SRP, car tes personnes / magazines ont sans doute déjà d'autres responsabilités que le simple fait de fournir la liste des abonnements / abonnés

[CedricMocquillon]

@Arzar: effectivement, Sean Parent n'aborde pas les pointeurs sur objets à sémantique d'entité, c'est juste que sa présentation m'a fait réfléchir sur mon approche du problème pour les objets à sémantique d'entité
@Iradrille: ok pour le risque sur les références cycliques, l'idée c'est plus de discuter autour du bien fondé de passer par des pointeurs (ceux que tu veux ) ou de passer par des identifiants pour représenter les relations entre objets à sémantique d'entité
@koala01

Sans compter que je ne vois pas en quoi un accès en temps constant(en o(1) ) peut t'apporter quoi que ce soit.

En effet, à moins de savoir que tu veux atteindre le 105eme abonné à un magazine ou le 3emeabonnement d'une personne, l'accès en temps constant ne te sera d'aucune utilité.

En fait le O(1) ne porte pas sur l'utilisation d'un vecteur par la classe Person pour accéder aux magazines mais sur l'utilisation d'un pointeur à la place d'un id.
Si pour simplifier, une personne ne peut être abonnée qu'à un magazine mais que cet abonnement peut changer au cours du temps (on ne pourra donc pas utiliser en interne une référence sur le magazine car il n'y a pas possibilité de rebinder une référence). On a deux approches: par pointeur ou par id.
Si on privilégie l'approche par pointeur, je peux directement faire person.magazine()->title() pour avoir le titre du magazine auquel est abonné ma personne.
Si on privilégie l'approche par id, il faut que je passe par le manager: manager_magazines.get_magazine(person.id_magazine())->title() et c'est là qu'on va avoir un O(log n) puisque le manager doit retrouver le magazine de la personne (via son id) parmi l'ensemble des magazines chargés (recherche dichotomique sur les id).
Après tu marques un point sur les responsabilités des classes mais je ne vois personnellement pas comment le concilier avec l'efficacité d'accès.

[PilloBuenaGente]

Un logiciel se doit d'être d'avantage robuste que rapide.
De plus, la recherche d'identifiants ( nombre entiers de préférence ) dans une map est très rapide.
Cela m’étonnerais qu'il faille faire faire cette opération plusieurs fois par secondes.

Ensuite je ne vois le problème de devoir faire appel à la base de donnée magazine pour afficher ceux d'un utilisateur. Cette liste est permanente.

Pourquoi ne pas avoir une troisième classe représentant les abonnements, qui lierait un identifiant utilisateur avec un identifiant magazine.
Personne et magazine garderaient leur sémantique de valeur.

[Médinoc]

De plus, la recherche d'identifiants ( nombre entiers de préférence ) dans une map est très rapide.

C'est pas sûr, elle parcourt plusieurs indirections de pointeurs (dues à l'arbre) avec une localité mémoire pas vraiment garantie...

[koala01]

@koala01

En fait le O(1) ne porte pas sur l'utilisation d'un vecteur par la classe Person pour accéder aux magazines mais sur l'utilisation d'un pointeur à la place d'un id.
Si pour simplifier, une personne ne peut être abonnée qu'à un magazine mais que cet abonnement peut changer au cours du temps (on ne pourra donc pas utiliser en interne une référence sur le magazine car il n'y a pas possibilité de rebinder une référence). On a deux approches: par pointeur ou par id.

oui, c'est ce que j'ai compris après avoir relu attentivement ton intervention

Si on privilégie l'approche par pointeur, je peux directement faire person.magazine()->title() pour avoir le titre du magazine auquel est abonné ma personne.
Si on privilégie l'approche par id, il faut que je passe par le manager: manager_magazines.get_magazine(person.id_magazine())->title() et c'est là qu'on va avoir un O(log n) puisque le manager doit retrouver le magazine de la personne (via son id) parmi l'ensemble des magazines chargés (recherche dichotomique sur les id).
Après tu marques un point sur les responsabilités des classes mais je ne vois personnellement pas comment le concilier avec l'efficacité d'accès.

Il faut quand même faire la part du diable : ici, on parle de rajouter l'équivalent de maximum 16 comparaisons pour retrouver un magazine (ou une personne) parmi 65000!

Et il est d'ailleurs plus que probable que ce que tu "perd" en recherche dichotomique, tu puisse le gagner en évitant un cachemiss éventuel

Je m'explique :

Tes pointeurs ( qu'il pointent vers une personne vers un magazine, ce sera le même combat) vont, de toutes manières, très certainement demander au processeur d'aller chercher une adresse qui ne sera pas dans son cache lorsque tu voudras y arriver depuis (le magazine ou la personne) dont il est membre.

Si tu veux parcourir toutes tes personnes et savoir à quel magazine elles sont abonnées, tu vas faire une boucle du genre de (C++11 inside)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
UnConteneur quelconque recup;
for (auto it : collectionDePersonne){
    recup.pushBack(it->magazine());
}

Dans le meilleur des cas, collectionDePersonne est un tableau (donc à accès constant) qui contient des pointeurs (pour lesquels l'espace mémoire a été alloué dynamiquement ! ) sur des personnes.

Cela signifie que, dans le meilleur des cas le processeur va charger dans son cache les éléments contigus de collectionDePersonne, mais que lorsque tu feras it->magazine(), le simple fait d'appeler une fonction membre va obliger le processeur à charger dans son cache une ligne qui contienne l'adresse spécifique représentée par it.

C'est un fait auquel on ne peut pas grand chose à partir du moment où l'on utilise l'allocation dynamique pour des objets dont le type a sémantique de valeur, donc, il faut juste en être conscient.

Mais cela implique de, dans le pire des cas, le processeur devra charger une ligne de cache par élément contenu dans collectionDePersonne.

Le problème, c'est que dans la fonction membre magazine, tu vas de nouveau suivre une logique proche de pointeur->fonctionMembre() (pour etre précis, ce sera magazine_->getName()) et que, comme le pointeur en question est aussi un pointeur qui correspond à un espace mémoire alloué dynamiquement, et que cela obligera donc de nouveau le processeur à charger une ligne de cache.

Cela signifie que pour chaque personne se trouvant dans collectionDePersonne, tu vas obliger le processeur à charger 1+(nombre d'abonnements) lignes de cache en mémoire.

Si tu travailles sous la forme d'id, si chaque personne ne peut avoir qu'un seul abonnement, l'id du magazine se trouvera d'office dans la ligne de cache du processeur (sous la forme d'une variable membre) et, si chaque personne peut avoir plusieurs abonnement, au pire, le processeur a de bonne chance de pouvoir se contenter du chargement d'une ligne de cache qui contiendra l'ensemble des abonnement auxquels la personne est abonnées, et qui seront contigus.

Tu passes donc de 1+(nombre d'abonnements) chargements de lignes de cache à 1+1 chargements de lignes de cache.

Le nombre de données lues par chargement de ligne de cache devient, de facto, beaucoup plus intéressant (et d'autant plus intéressant que le nombre d'abonnements d'une personne est important).

A partir de là, on a récupéré l'id du magazine, et on repart donc sur le même principe : tu recherches le magazine par dichotomie (maximum seize itérations, donc chargement de 16 lignes de cache) pour 65000 magazines), et comme ton magazine est, lui aussi le fruit d'une allocation dynamique, le chargement d'une ligne de cache supplémentaire pour être en mesure de récupérer le nom du magazine.

Dés lors, je t'accorde que l'accès en temps constant est globalement plus rapide que l'accès en O(log(n) ), mais, tout bien considéré, l'accès en O(log(n)) ne sera pas forcément beaucoup plus lent, grace au fait que tu arrives à lire d'avantage de données après chaque chargement d'une ligne de cache.

Maintenant, ce que je te propose, c'est d'avoir une structure qui soit, justement, l'abstraction de l'abonnement et qui mette en relation le magazine et son abonné.

Là encore, tu as deux solutions : la baser sur des pointeurs sous la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
struct Subscription{
    Person * person;
    Magazine * magazine;
};

ou sou la forme d'identifiant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
struct Subscription{
    PersonId_t  person;
    MagazineId_t magazine;
};

et tu te rends compte que, si tu veux accéder au nom de la personne ou à celui du magazine, tu obliges encore une fois le processeur à charger une ligne de cache pour la personne et une autre pour le magazine dans le premier cas, alors que, dans le deuxième cas, tout ce qui te permet d'accéder à l'ensemble des informations se trouve plus que vraisemblablement dans la même ligne de cache (ou, au pire, dans une ligne de cache et sa suivante).

Cela signifie que si, en plus, tu peux t'arranger pour que tous les objets de types Subscription soient contigus en mémoire, tu peux en arriver à permettre au processeur d'avoir l'intégralité de l'ensemble des informations d'abonnement dans une seule et unique ligne de cache, ou, au pire, dans plusieurs lignes de cache contigües.

A partir de là, tout ce qu'il te faut, c'est d'être en mesure de les trier et de les indexer de la manière la plus intelligente possible :

En fonction du cas, tu les tries d'abord sur l'id de la personne puis sur l'id du magazine, ou l'inverse, et tu les indexe sur l'id de la personne et sur l'id du magazine, de manière à pouvoir y accéder "facilement" et grace à une recherche dichotomique.

l'énorme avantage supplémentaire est que tu t'abstrait totalement de la notion de personne et de la notion de magazine dans ta notion d'abonnement, et que tu fais donc un pas supplémentaire vers le respect du DIP (Dépendancy Inversion Principle) et donc vers plus d'évolutivité.

Et comme, les id sont classiquement des types de base (de préférence des valeurs numériques), la comparaison devient très rapide

[koala01]

C'est pas sûr, elle parcourt plusieurs indirections de pointeurs (dues à l'arbre) avec une localité mémoire pas vraiment garantie...

Mais, la localité mémoire n'est pas plus garantie si tu travailles directement avec un (des) pointeur(s) à l'intérieur de ta classe Person ou de ta classe Magazine, vu que, a priori, les objets correspondant à ces deux classes seront créés au travers de l'allocation dynamique de la mémoire.

Tu ne pourras donc pas éviter le cache-miss dés le moment où tu travailles avec des pointeurs, alors que tu as de fortes chances de l'éviter (ou, du moins, tu as beaucoup plus de chances de l'éviter) si tu travailles simplement avec un identifiant unique

[Médinoc]

J'ai du mal à comprendre ton raisonnement dans ce post et le précédent.
Tes "cache-miss supplémentaires" semblent impliquer qu'on déréférence les pointeurs de Person ou Magazine, alors qu'on ne le fait pas dans le cas des ID.

Et là, je ne vois pas le lien, sauf si tu présupposes que l'identité est un champ des classes en question plutôt que l'adresse des objets.

[koala01]

J'ai du mal à comprendre ton raisonnement dans ce post et le précédent.
Tes "cache-miss supplémentaires" semblent impliquer qu'on déréférence les pointeurs de Person ou Magazine, alors qu'on ne le fait pas dans le cas des ID.

Et là, je ne vois pas le lien, sauf si tu présupposes que l'identité est un champ des classes en question plutôt que l'adresse des objets.

Bien sur que je suppose que c'est un champs des classes et non l'adresse des objets.

Je ne fais que suivre la logique que j'exposais dés le départ dans ma première intervention consacrée à ce problème particulier selon laquelle n'importe quel objet ayant sémantique d'entité est par nature identifiable de manière unique et non ambigüe au niveau de ses seules données (ou du moins, au niveau de certaines de ses données uniquement)

[Médinoc]

Dans ce cas, je comprends parfaitement ton explication: "extraire" ce champ d'ID pour l'utiliser directement à la place des pointeurs d'objet économise des déréférencements, au prix de rendre ceux-ci plus coûteux.

[koala01]

Dans ce cas, je comprends parfaitement ton explication: "extraire" ce champ d'ID pour l'utiliser directement à la place des pointeurs d'objet économise des déréférencements, au prix de rendre ceux-ci plus coûteux.

disons que la recherche de l'objet à déréférencer sera effectivement un peu plus coûteuse, parce que tu passes effectivement par une étape obligatoire de recherche.

Mais, d'un autre coté:

• L'ID te permet de t'abstraire totalement de la donnée qu'il identifie et tu évites donc une dépendance indue entre le magazine, la personne et l'abonnement
• Tu n'as, de toutes manières, généralement besoin que de l'ID d'un objet, tu n'as absolument pas besoin de te trimbaler tout l'objet dans la majeure partie des cas (tu n'as besoin de l'objet en lui même que quand c'est pour l'afficher ou le modifier)
• Quelle que soit sa forme un ID ne contient de toutes manières que ce qui permet d'identifier un objet de manière unique et non ambigüe, ce qui minimise l'espace mémoire nécessaire à sa représentation et qui permet donc d'espérer d'en avoir un plus grand nombre par ligne de cache si l'on s'arrange pour les placer de manière contigüe

tu as donc "tout à gagner" à utiliser cet ID plutôt que l'objet lui-même, ne serait-ce que pour éviter un code proche de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
personne->addAbonnement(std::string const & magName, Person * autrePersonne){
    abonnements_.find(magName).addAbonnement(autrePersonne);
}

qui serait tout à fait envisageable avec des pointeurs.

Sauf que cela impliquerait le fait que tu donnes, encore une fois, une responsabilité à ta classe Personne qu'elle n'a absolument pas à avoir : celle de te permettre de modifier l'un des magazines auquel elle est abonnée.

Le simple fait d'utiliser des abstractions te permet en l'occurrence une énorme souplesse (tu n'as, dans la plupart des cas, qu'à utiliser l'identifiant) et de mettre en place un système qui t'assure qu'aucun objet ne sera modifié de manière indue.

La seule chose à laquelle il faudra, bien sûr, être attentif, est de ne pas rechercher l'identifiant d'un personne auprès de ton "gestionnaire" de magazines et inversement