Type de variable optimale pour gérer 4 valeurs possibles

Version imprimable

23/02/2016, 11h41
dazzle

Type de variable optimale pour gérer 4 valeurs possibles

Bonjour tout le monde,

Je développe un programme en C++ pour modéliser un réseau métabolique (comprendre réseau de réactions chimiques) par un graphe : un ensemble de noeuds liés par des arêtes. Les noeuds correspondent aux composés et les arêtes aux réactions impliquant ces composés. J'ai donc les classes correspondantes : Graph, Node (noeud) et Edge (arête). Graph connait la liste des noeuds et des arêtes. Enfin, chaque noeud est dans un état parmi 4 états possibles : gris, blanc, vert ou rouge.

Un graphe aura dans de nombreux cas plusieurs milliers de noeuds, qui doivent être traversés par l'algorithme de recherche qui tient compte de la couleur des noeuds. Dans l'idée d'optimiser l'utilisation de la mémoire et la vitesse d'exécution, je me demande comment implémenter au mieux la gestion de la couleur des noeuds.

Quel type de variable utiliser pour la couleur (est-ce qu'on peut faire mieux qu'un int) ? Accessoirement, est-il préférable qu'elle soit gérée par le noeud concerné (classe Node) ou par la classe Graph qui se chargerait de mapper le numéro du noeud à sa couleur ?

EDIT : On doit pouvoir différencier rapidement les noeuds verts/rouges des noeuds gris/blancs.
23/02/2016, 13h47
gangsoleil

Bonjour,

Dans la mesure où tu n'as que 4 valeurs possibles, pourquoi ne pas utiliser un (unsigned) char ? Ca prend un octet, ce qui sera toujours moins que 4 (ou 8) pour les entiers.

En complément de gangsoleil, un truc comme cela :mrgreen:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
typedef enum e_COLOR_ID {
    COLOR_GREEN = 1,
    COLOR_GREY  = 2,
    COLOR_RED   = 4,
    COLOR_WHITE = 8
} COLOR_ID;
 
 
#define IS_GREEN(C) \
    (((C  & COLOR_GREEN) == COLOR_GREEN) && ((C & COLOR_GREY) == 0) && ((C  & COLOR_RED) == 0) && ((C  & COLOR_WHITE) == 0))
 
 
#define IS_GREY(C) \
    (((C  & COLOR_GREEN) == 0) && ((C & COLOR_GREY) == COLOR_GREY) && ((C  & COLOR_RED) == 0) && ((C  & COLOR_WHITE) == 0))
 
 
#define IS_RED(C) \
    (((C  & COLOR_GREEN) == 0) && ((C & COLOR_GREY) == 0) && ((C  & COLOR_RED) == COLOR_RED) && ((C  & COLOR_WHITE) == 0))
 
 
#define IS_WHITE(C) \
    (((C  & COLOR_GREEN) == 0) && ((C & COLOR_GREY) == 0) && ((C  & COLOR_RED) == 0) && ((C  & COLOR_WHITE) == COLOR_WHITE))

Avec le C++11, tu peux même combiner les deux approches (et sans macro) ainsi:
Code:

1 2 3 4 5 6 7 8 9 10 11 enum COLOR_ID : char{ COLOR_GREEN = 1, COLOR_GREY = 2, COLOR_RED = 4, COLOR_WHITE = 8 }; inline bool IS_GREEN(COLOR_ID c) {return c==COLOR_GREEN;} inline bool IS_GREY(COLOR_ID c) {return c==COLOR_GREY;} inline bool IS_RED(COLOR_ID c) {return c==COLOR_RED;} inline bool IS_WHITE(COLOR_ID c) {return c==COLOR_WHITE;}
Voire même mieux encore, avec les class enum:
Code:

1 2 3 4 5 6 enum class COLOR_ID : char {GREEN, GREY, RED, WHITE}; inline bool IS_GREEN(COLOR_ID c) {return c==COLOR_ID::GREEN;} inline bool IS_GREY(COLOR_ID c) {return c==COLOR_ID::GREY;} inline bool IS_RED(COLOR_ID c) {return c==COLOR_ID::RED;} inline bool IS_WHITE(COLOR_ID c) {return c==COLOR_ID::WHITE;}
Pour plus de détails sur les class enum, dites aussi scoped enum, regardes sur cppreference.com.

Par ailleurs, si ton noeud n'a aucune autre fonctionnalité (meme technique) que d'avoir une couleur, tu peux envisager de ne pas avoir de classe.
A voir comment ton code s'organise.

23/02/2016, 15h44
dazzle

Merci pour vos réponses complémentaires, ça correspond très bien à ce que je cherche en terme d'optimisation de l'espace mémoire (en plus ça a l'avantage de clarifier la notion de couleur dans le code). Par contre, quelqu'un pourrait-il me préciser ce qu'il en est de la rapidité d'accès à ce type de données ? Toujours par rapport à l'utilisation d'un int tout bête par exemple

Citation:

Envoyé par leternel

Par ailleurs, si ton noeud n'a aucune autre fonctionnalité (meme technique) que d'avoir une couleur, tu peux envisager de ne pas avoir de classe.
A voir comment ton code s'organise.

Oui, mais dans cette situation les noeuds possèdent d'autres attributs et méthodes qui justifient la définition d'une classe :)
23/02/2016, 15h56
ternel
Une énum est normalement aussi rapide que le type primitif sous-jacent. Ca n'apporte pour ainsi dire que de robustesse à la compilation.
Mieux, le compilateur est peut-être capable de faire des optimisations spécifiques (surtout avec les scoped enums)

Un type primitif est optimal (en rapidité) s'il fait la meme taille que le mot machine, dont la théorie voudrait que ce soit la taille de int.
En pratique, tu ne devrais pas voir d'écart avec un (un)signed char.

Question optimisation mémoire, il faut étudier le layout mémoire des classes, et le plus simple pour cela, c'est de faire attention à la taille de chaque membre, et à l'ordre correspondant.

Supposons les structures suivantes:
Code:

1 2 3 4 5 6 7 8 9 10 struct Truc { char color; int id; char a, b, c; }; struct Bidule { char color, a, b, c; int id; };
Sur une machine telle que sizeof(int) == 4, Truc a des chances de faire un sizeof de 12, tandis que Bidule peut n'en faire que 8.
La raison, c'est que, d'une part, une variable ne peut avoir pour adresse qu'un multiple de sa propre taille, et d'autre part que l'ordre en mémoire des membres d'une class/struct est celui déclaré. Dans Truc, le champ [c]id ne peut être aligné que sur un multiple de 4, laissant un trou entre color et lui-même.

En règle général, il y a un compromis à faire sur ces deux aspects d'optimisations (temps et espace).
Dans tous les cas, on n'optimise qu'après mesure, et on ne mesure que dans les conditions réelles, donc quand le programme est compilé avec les options d'optimisations qui conviennent.
Pour gcc, par exemple, il s'agit probablement d'utiliser -O3 (ou -O2).
23/02/2016, 15h58
gangsoleil

Citation:

Envoyé par dazzle

Par contre, quelqu'un pourrait-il me préciser ce qu'il en est de la rapidité d'accès à ce type de données ? Toujours par rapport à l'utilisation d'un int tout bête par exemple

Les optimisations de base des compilateurs sont souvent (beaucoup) plus performantes que ce qu'on croit, donc à ta place, je commencerai par l'implémenter avec une solution proposée ici, et ensuite seulement tu verras si tu as des problèmes de perfs. Et si oui, alors seulement tu utiliseras un profiler qui t'indiquera dans quelles classes/fonctions tu passes le plus de temps, et donc où faire tes optimisations.
23/02/2016, 16h19
stendhal666

Dans l'en-tête <cstdint>, tu as des définitions de type qui devraient être intéressantes pour toi, en particulier uint_fast8_t: http://www.cplusplus.com/reference/cstdint/?kw=cstdint

Dans l'ensemble il n'est pas garanti que plus petit soit plus rapide (c'est l'intérêt d'une définition de type comme uint_fast8_t) puisque les registres du processeur sont dimensionnés en général pour 32/64 bits, avec parfois des registres spécialisés plus grand pour le calcul en virgule flottante.

Je ne pense pas que cela fasse une quelconque différence pour ton programme d'avoir des entiers de telle ou telle taille. En revanche, pour aller plus vite, je te conseillerais de creuser la piste d'un allocateur spécialisé, dans le genre de boost::pool ou celui de Loki (la bibliothèque d'Alexandrescu) car tu vas allouer des milliers de noeuds de petite taille. L'opérateur new peut-être sous-optimal dans ces cas-là. Ou bien, si le graphe est régulier (dans le genre n-arity tree) tu peux utiliser une représentation en heap.
23/02/2016, 16h43
dourouc05

Autre solution : un poids-mouche. Il y a quelque chose pour ça dans boost, jamais utilisé : http://www.boost.org/doc/libs/1_60_0...doc/index.html.

Ici, je pars du principe que les nœuds ne contiennent que la couleur. Tu n'auras plus de classe de nœud, mais seulement un identifiant dans un gros tableau de couleurs, représentées "efficacement" (à voir la meilleure manière de faire : un octet par couleur comme proposé précédemment, seulement deux bits et chipoter avec des opérations sur les bits… ou autre). Au lieu d'utiliser l'objet nœud, tu remplaces par un accès dans le tableau.

L'avantage en performance est que tous les éléments sont bien côte à côte (localité des données), tu peux espérer exploiter au mieux les caches du processeur (c'est pour ça qu'il vaut peut-être mieux aller vers une représentation avec des bits, pour bien les exploiter, mais ça rendra ton code bien plus illisible).

Pas à essayer pour un premier jet, en tout cas :aie:.
23/02/2016, 17h48
dazzle

Citation:

Envoyé par leternel

En règle général, il y a un compromis à faire sur ces deux aspects d'optimisations (temps et espace).
Dans tous les cas, on n'optimise qu'après mesure, et on ne mesure que dans les conditions réelles, donc quand le programme est compilé avec les options d'optimisations qui conviennent.

Citation:

Envoyé par gangsoleil

Les optimisations de base des compilateurs sont souvent (beaucoup) plus performantes que ce qu'on croit, donc à ta place, je commencerai par l'implémenter avec une solution proposée ici, et ensuite seulement tu verras si tu as des problèmes de perfs. Et si oui, alors seulement tu utiliseras un profiler qui t'indiquera dans quelles classes/fonctions tu passes le plus de temps, et donc où faire tes optimisations.

En effet, il est peut-être un peu tôt pour penser à l'optimisation du programme alors que l'algo lui-même n'est pas finalisé... :aie: mais je voulais un avis expérimenté sur ce petit détail dont l'impact sera très probablement démultiplié à l'exécution.

Citation:

Envoyé par stendhal666

Je ne pense pas que cela fasse une quelconque différence pour ton programme d'avoir des entiers de telle ou telle taille. En revanche, pour aller plus vite, je te conseillerais de creuser la piste d'un allocateur spécialisé, dans le genre de boost::pool ou celui de Loki (la bibliothèque d'Alexandrescu) car tu vas allouer des milliers de noeuds de petite taille. L'opérateur new peut-être sous-optimal dans ces cas-là. Ou bien, si le graphe est régulier (dans le genre n-arity tree) tu peux utiliser une représentation en heap.

A priori, l'ensemble des noeuds devrait être créé une seule fois lors du chargement du graphe, mais le reste des opérations seront par exemple des modifications d'attributs, mais pas de créations/délétions rapides de noeuds. Est-ce qu'un allocateur spécialisé reste bénéfique dans ce cas ? (Désolé pour la question hyper-naïve mais on part assez loin de mon champ de compétences)
Et le graphe n'est pas régulier, malheureusement...

Citation:

Envoyé par dourouc05

Autre solution : un poids-mouche. Il y a quelque chose pour ça dans boost, jamais utilisé : http://www.boost.org/doc/libs/1_60_0...doc/index.html.

Je garde ça à portée de main comme méthode à tester une fois l'algo terminé et implémenté alors :).
23/02/2016, 18h46
Luc Hermitte

Je préfère généralement faire mes safe enums avec des enums pas classes. La raison est que l'on ne peut pas rajouter des fonctions à un enum class, ce qui ne permet pas d'avoir un constructeur par défaut qui initialise à une valeur bidon maitrisée.

Maintenant, les enum class permettent de choisir la représentation sous-jacente, ce qui pas possible avec les anciens énumérés. Et si vraiment, tu as des besoins de ce côté là, ils peuvent être encore plus intéressants.
23/02/2016, 21h55
stendhal666

Citation:

A priori, l'ensemble des noeuds devrait être créé une seule fois lors du chargement du graphe, mais le reste des opérations seront par exemple des modifications d'attributs, mais pas de créations/délétions rapides de noeuds. Est-ce qu'un allocateur spécialisé reste bénéfique dans ce cas ? (Désolé pour la question hyper-naïve mais on part assez loin de mon champ de compétences)

Non, ce n'est pas une question naïve, ça reste un sujet plutôt "avancé"! Comme cela a été bien dit dans certaines réponses, tu ne pourras rien savoir sans profiler ton programme d'abord. Mais oui, c'est le genre de scénario où boost::pool peut être utile: il te permet d'allouer bien plus rapidement la mémoire pour tes quelques milliers de petits objets et tu peux, quand tu en as terminé avec eux, les abandonner sans les détruire, puisque la destruction du pool te garantit l'absence de fuite mémoire.

Pour en savoir plus sur l'intérêt du pooling tu peux regarder là: http://www.boost.org/doc/libs/1_60_0...l/pooling.html L'idée générale est que new ou malloc, qui sont généralistes, sans idée préconçue sur la taille des objets qu'ils devront allouer, ne peuvent pas optimiser leur stratégie d'allocation: si par exemple ton programme ne procédait qu'à l'allocation de quelques std::string, commencer par réserver une place mémoire importante pour les y stocker serait contre-productif; donc new alloue plus ou moins le minimum de mémoire demandée tout en étant obligé de conserver des informations pour chaque allocation et doit répéter les mêmes efforts à chaque fois: recherche d'un emplacement libre, mise-à-jour des indexs, etc. Tandis que boost::pool suit justement la stratégie de réserver une place mémoire importante, le fameux pool, et peut la gérer à sa façon en limitant le coût de chaque pseudo-allocation suivante.
24/02/2016, 08h53
ternel

Citation:

Envoyé par Luc Hermitte

Je préfère généralement faire mes safe enums avec des enums pas classes. La raison est que l'on ne peut pas rajouter des fonctions à un enum class, ce qui ne permet pas d'avoir un constructeur par défaut qui initialise à une valeur bidon maitrisée.

Maintenant, les enum class permettent de choisir la représentation sous-jacente, ce qui pas possible avec les anciens énumérés. Et si vraiment, tu as des besoins de ce côté là, ils peuvent être encore plus intéressants.

En fait, si, on peut définir le sous-jacent pour une "unscoped enum". Il suffit d'écrire enum truc : char {truc_1, truc_2}.
Je ne connais aucun cas où, quand je crée une enum, opter pour une class enum est pénalisante.

Par contre, en effet, l'absence de valeur par défaut est dommageable.

C'est exactement ce que je dis, je ne peux pas avoir une valeur par défaut comme ce que j'obtiens avec:

Code:

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
struct truc
{
    enum type { v1, v2, MAX__, UNDEFINED__ };
 
    truc()
    [[expects: m_value == UNDEFINED__]]
    : m_value(UNDEFINED__) {}
 
    truc(type v)
    [[requires: v <= MAX__]]
    [[expects: m_value <= MAX__]]
    : m_value(v)
    {}
 
    explicit truc(int v)
    [[expects: m_value <= MAX__]]
    : m_value(type(v))
    {
        if (m_value > MAX_) throw std::domain_error("....");
    }
    explicit truc(std::string const& name)
    [[expects: m_value < MAX__]]
    ;
 
    char const* name() const
    [[requires: m < MAX__]]
    ;
    type internal() const
    [[requires: m <= MAX__]]
    { return m_value; }
 
    truc& operator++()
    [[requires: m < MAX__]]
    {
        ++m_value;
        return *this;
    }
    truc operator++(int)
    [[requires: m < MAX__]]
    {
        tmp truc = *this;
        ++*this;
        return tmp;
    }
 
    static truc begin() { return v1; }
    static truc end  () { return MAX__; }
 
private:
    type m_v;
};

Si je peux définir toutes les fonctions membres en libre, même les opérateurs oui (ainsi qu'émuler les constructeurs de conversion), je ne peux pas définir de constructeur par défaut sur des enum class qui font que [minicode]truc e;[/minicode] est bien dans l'état undefined que je désire -- OK, la sanitization=memory (IIRC) me permettra aussi de détecter ces cas d'énumérés non initialisés.

24/02/2016, 13h22
dazzle

Citation:

Envoyé par stendhal666

Tandis que boost::pool suit justement la stratégie de réserver une place mémoire importante, le fameux pool, et peut la gérer à sa façon en limitant le coût de chaque pseudo-allocation suivante.

Ok je comprends mieux l'avantage qu'il peut y avoir à utiliser ça !

Je pense que je vais utiliser class enum dans un premier temps. Je n'ai a priori pas besoin de définir de valeur par défaut, mais si c'est le cas il y a toujours la solution indiquée par Luc Hermitte. Et à plus long terme, selon les résultats du profiling, j'irai voir du côté de boost :)

Merci beaucoup à tous pour votre aide !
24/02/2016, 19h49
koala01
Salut,

Citation:

Envoyé par dazzle

Ok je comprends mieux l'avantage qu'il peut y avoir à utiliser ça !

Je pense que je vais utiliser class enum dans un premier temps. Je n'ai a priori pas besoin de définir de valeur par défaut, mais si c'est le cas il y a toujours la solution indiquée par Luc Hermitte. Et à plus long terme, selon les résultats du profiling, j'irai voir du côté de boost :)

Merci beaucoup à tous pour votre aide !

De toutes façons, il faudrait vraiment que tu utilises énormément de données pour en arriver à voir une différence entre les différents types primitifs utilisés en termes de performances! Et, avant que le choix d'un type primitif ne puisse avoir un impact "majeur" sur les performances, il faut te dire qu'il y aura sûrement bien d'autres choses à améliorer, dont tes algorithmes et / ou le choix des collections utilisées pour maintenir tes données ;)

Dés lors, dans un premier temps le conseil à te donner est :
Citation:
utilises une énumération ("classique","fortement typée" comme permis depuis l'arrivée de C++11 ou "safe enum" comme proposée par Luc), ce sera toujours bien mieux que les différentes alternatives qui existent.

Mais, surtout, commence par avoir quelque chose qui fonctionne car tu n'as aucun intérêt à arriver rapidement à faire planter ton application ;) . Une fois que tu as quelque chose qui fonctionne, si tu as des problèmes de performances, après profiling et pour les parties les plus consommatrices de temps

veille à éviter autant que possible la copie pour "tout ce qui est plus gros qu'un type primitif".
essaye, si tu utilises std::vector, de déterminer à l'avance la taille qu'il devra avoir, afin d'éviter qu'il ne réalloue trop souvent de la mémoire
revois les algorithmes utilisés
revois les choix des éventuelles collections utilisées, car chaque collection a son cas d'utilisation bien particulier
n'hésite pas à faire plusieurs passes de profilling + améliorations citées ici
Et si, une fois que tu es sur et certain qu'il n'y a plus moyen d'améliorer les chose à l'aide de cette liste, tu éprouves toujours des problèmes de performances, alors il sera peut être temps de voir si le choix d'un type "plus petit" peut encore t'apporter un gain intéressant en termes de performances ;)