IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C++ Discussion :

std::priority_queue et constructeurs par recopie


Sujet :

C++

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2011
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Janvier 2011
    Messages : 3
    Par défaut std::priority_queue et constructeurs par recopie
    Petite question philosophique concernant les std::priority_queue.

    Soit le code suivant, dans lequel on définit un foncteur qui permet la comparaison entre deux entiers, qui est utilisé dans une std::priority_queue.

    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
     
    #include <cstdlib>
    #include <iostream>
    #include <queue>
     
    struct Comparator
    {
            Comparator(){}
            Comparator(const Comparator & c) { std::cout << "Copy constructor of Comparator\n" ; }
            bool operator()(int a, int b) const { return a<b ; }
    } ;
     
    int main(int argc, char** argv)
    {
            Comparator comp ;
            std::priority_queue<int, std::vector<int>, Comparator> queue(comp) ;
     
            queue.push(3) ; queue.push(5) ; queue.push(4) ; queue.push(6) ; 
     
            while (! queue.empty())
            {
                    std::cout << queue.top() << std::endl ;
                    queue.pop() ;
            }
     
            return EXIT_SUCCESS ;
    }
    Si on execute le code, on se rend compte que le constructeur par recopie de Comparator est appelé 26 fois. Je comprends bien qu'en dessous il y a toute la mécanique des appels à make_heap/push_heap/... et que ces fonctions sont appelées 26 fois.

    La question que je me pose, cependant, c'est pourquoi le comparateur est copié à chaque appel ?

    A noter, en plus, qu'une référence vers instance du comparateur est passé au constructeur de la priority_queue. Au pire, qu'il y ait une copie du comparateur à la construction pour garantir l'existence du comparateur serait tout à fait logique, mais une multitude de copies pour chaque opérations ??

    En plus on ne peut pas définir de static operator() .

    Je suis conscient que c'est du pinaillage parce que ce n'est pas la mort de recopier une structure sans attribut, mais quand même je trouve que c'est du gâchis. A moins que quelqu'un ait une explication raisonnable qui explique ce choix de conception. Si c'est le cas, je serai plus qu'heureux de l'entendre (je veux dire de la lire).

  2. #2
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2011
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Janvier 2011
    Messages : 3
    Par défaut
    en modifiant l'opérateur parenthèse de la manière suivante :

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    bool operator()(int a, int b) const
    {
            std::cout << "compare("<<a<<","<<b<<")\n" ;
            return a<b ;
    }
    On se rend compte que l'opérateur est appelé 6 fois dans l'exemple précédent.
    26 copies du foncteur pour 6 appels effectifs, piètre rendement...

  3. #3
    r0d
    r0d est déconnecté
    Membre expérimenté

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    4 290
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Août 2004
    Messages : 4 290
    Billets dans le blog
    2
    Par défaut
    L'idée du foncteur dans ce genre d'utilisation est que cet objet a un état. Autrement dit, il peut posséder des attributs (variables membres) qui peuvent évoluer au fil de l'exécution d'un algorithme. D'où la copie à chaque étape d'un algorithme, pour prendre en compte l'état courant du foncteur.

    Si tu n'as pas besoin de cet avantage fourni par l'utilisation d'un foncteur, alors utilises un pointeur de fonction ou une fonction lambda.

  4. #4
    Expert éminent
    Avatar de koala01
    Homme Profil pro
    aucun
    Inscrit en
    Octobre 2004
    Messages
    11 644
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 53
    Localisation : Belgique

    Informations professionnelles :
    Activité : aucun

    Informations forums :
    Inscription : Octobre 2004
    Messages : 11 644
    Par défaut
    Salut,

    Ceci dit, étant donné que ton foncteur n'a strictement aucun membre, la copie est particulièrement rapide.

    Actuellement, le plus gros du temps que prend cette copie est du... à l'affichage que tu demandes sur la sortie standard

    Autrement, je ne suis même pas sur que cela prenne effectivement plus que le temps nécessaire à placer un acu du processeur sur la pile

    Bref, avant que cette copie ne pose réellement des problèmes raisonnablement quantifiables en terme de performances, il faudra sans doute avoir un très grand nombre d'éléments
    A méditer: La solution la plus simple est toujours la moins compliquée
    Ce qui se conçoit bien s'énonce clairement, et les mots pour le dire vous viennent aisément. Nicolas Boileau
    Compiler Gcc sous windows avec MinGW
    Coder efficacement en C++ : dans les bacs le 17 février 2014
    mon tout nouveau blog

  5. #5
    r0d
    r0d est déconnecté
    Membre expérimenté

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    4 290
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Août 2004
    Messages : 4 290
    Billets dans le blog
    2
    Par défaut
    Effectivement. D'ailleurs, pour savoir quel est le coût de ces appels au copy ctor, il faudrait faire des tests; et je ne suis même pas sûr qu'on y gagne en passant par un pointeur de fonction ou une lambda.

  6. #6
    Membre Expert
    Homme Profil pro
    Étudiant
    Inscrit en
    Juin 2012
    Messages
    1 711
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Juin 2012
    Messages : 1 711
    Par défaut
    Citation Envoyé par r0d Voir le message
    Effectivement. D'ailleurs, pour savoir quel est le coût de ces appels au copy ctor, il faudrait faire des tests; et je ne suis même pas sûr qu'on y gagne en passant par un pointeur de fonction ou une lambda.
    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
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    #include <cstdlib>
    #include <iostream>
    #include <queue>
    #include <functional>
    #include <ctime>
     
    #define WIN32_LEAN_AND_MEAN
    #include <Windows.h>
     
    struct Comparator {
    	Comparator(){}
    	Comparator(const Comparator & c) { }
    	bool operator()(int a, int b) const { return a<b ; }
    };
     
    inline bool CompFct(int a, int b) {
    	return a < b;
    }
     
    int main(int argc, char** argv) {
     
    	const size_t SIZE = 1000000U; // 1 million
     
    	double timeA, timeC, timeD, dFreq;
    	LARGE_INTEGER begin, end, freq;
    	QueryPerformanceFrequency(&freq);
    	dFreq = (double)freq.QuadPart / 1000.0; // ms;
     
    	timeA = timeC = timeD = 0.0;
     
    	srand((unsigned int)time(NULL));
     
    	std::vector<int> containerA(SIZE);
    	std::vector<int> containerB(SIZE);
    	std::vector<int> containerC(SIZE);
     
    	Comparator compA;
    	std::priority_queue<int, std::vector<int>, Comparator> queueA(compA, containerA);
    	std::priority_queue<int, std::vector<int>, std::function<bool(int, int)>> queueC(CompFct, containerB);
    	std::priority_queue<int, std::vector<int>, bool(*)(int, int)> queueD(CompFct, containerC);
     
    	for(size_t i=0; i<SIZE; ++i) {
     
    		int val = rand();
     
    		// foncteur 
    		QueryPerformanceCounter(&begin);
    		queueA.push(val);
    		QueryPerformanceCounter(&end);
    		timeA += (end.QuadPart - begin.QuadPart) / dFreq;
     
    		// std::function
    		QueryPerformanceCounter(&begin);
    		queueC.push(val);
    		QueryPerformanceCounter(&end);
    		timeC += (end.QuadPart - begin.QuadPart) / dFreq;
     
    		// fonction libre
    		QueryPerformanceCounter(&begin);
    		queueD.push(val);
    		QueryPerformanceCounter(&end);
    		timeD += (end.QuadPart - begin.QuadPart) / dFreq;
    	}
     
    	std::cout << "temps d'insertion de " << SIZE << " random elements\n"
    		<< "foncteur: " << timeA << "ms\n"
    		<< "std::function: " << timeC << "ms\n"
    		<< "fonction libre: " << timeD << "ms\n";
     
    	return EXIT_SUCCESS ;
    }
    (Oui, code pas portable )

    temps d'insertion de 1 000 000 random elements
    32bits:
    foncteur: 30.3689ms
    std::function: 78.391ms
    fonction libre: 27.696ms

    64 bits:
    foncteur: 24.9393ms
    std::function: 46.4982ms
    fonction libre: 18.8789ms

    Les mêmes nombres sont insérés dans le même ordre dans les 3 cas.
    Les vectors sont créés à la bonne taille pour ne pas prendre en compte le temps de réservation de la mémoire etc.

    Il y à bien un gain, ~10% en 32bits et ~30% en 64bits. L'utilisation de std::function dans ce cas est pas contre à proscrire.

  7. #7
    Futur Membre du Club
    Profil pro
    Inscrit en
    Janvier 2011
    Messages
    3
    Détails du profil
    Informations personnelles :
    Localisation : Canada

    Informations forums :
    Inscription : Janvier 2011
    Messages : 3
    Par défaut
    Merci pour vos réponses.

    Comme je l'avais indiqué dans le post initial, je suis bien conscient qu'au niveau performance c'est complètement négligeable. (peut être pas pour les puristes finalement ...)

    Citation Envoyé par r0d Voir le message
    L'idée du foncteur dans ce genre d'utilisation est que cet objet a un état. Autrement dit, il peut posséder des attributs (variables membres) qui peuvent évoluer au fil de l'exécution d'un algorithme. D'où la copie à chaque étape d'un algorithme, pour prendre en compte l'état courant du foncteur.
    Ma première réaction à cette réponse était que si on avait une instance unique du foncteur (ou une référence sur cette instance) pour toutes les opérations sur la priority_queue, ses attributs évolueraient au cours de l'algorithme. Je ne voyais pas pourquoi Il serait nécessaire de faire une copie de l'instance pour obtenir ces évolutions de paramètres.

    Par curiosité, j'ai quand même modifié le code pour bien comprendre la portée de la remarque en ajoutant un attribut exec_nb_ qui évolue dans le foncteur:

    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
    #include <cstdlib>
    #include <iostream>
    #include <queue>
     
    struct Comparator
    {
            unsigned int exec_nb_ ;
            Comparator(): exec_nb_(0){}
            Comparator(const Comparator & c): exec_nb_(c.exec_nb_) { std::cout << "copy of comparator\n" ; }
            bool operator()(int a, int b)
            {
                    std::cout << "compare("<<a<<","<<b<<") [ exec_nb_ = "<< (++exec_nb_) << "]\n" ;
                    return a<b ;
            }
    } ;
     
    int main(int argc, char** argv)
    {
            Comparator comp ;
            std::priority_queue<int, std::vector<int>, Comparator> queue(comp) ;
     
            queue.push(3) ; queue.push(5) ; queue.push(4) ; queue.push(6) ;
     
            while (! queue.empty())
            {
                    std::cout << queue.top() << std::endl ;
                    queue.pop() ;
            }
     
            return EXIT_SUCCESS ;
    }
    Dans la sortie on obtient :

    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
    ...
    copy of comparator
    compare(3,5) [ exec_nb_ = 1]
    copy of comparator
    copy of comparator
    compare(5,4) [ exec_nb_ = 1]
    copy of comparator
    copy of comparator
    compare(3,6) [ exec_nb_ = 1]
    compare(5,6) [ exec_nb_ = 2]
    6
    copy of comparator
    copy of comparator
    copy of comparator
    compare(4,5) [ exec_nb_ = 1]
    copy of comparator
    compare(5,3) [ exec_nb_ = 2]
    5
    ...

    Il s'avère qu'il y a effectivement une différence entre le fait de faire une copie et d'avoir une seule instance du foncteur : Comme il s'agit d'une copie du foncteur passé en paramètre, à chaque appel des fonctions sous-jacentes (make_heap/push_heap/...), le paramètre du foncteur est, en quelque sorte, "réinitialisé" à chacun de ces appels. Avec une instance unique pour toutes les opérations de la priority_queue on n'aurait pas cette réinitialisation.

    Du coup, je dirais plutôt que la copie à chaque étape d'un algo permet d'oublier l'état courant du foncteur (et de repartir avec un foncteur tel qu'il était à l'état initial).

    A l'utilisateur de faire attention à l'évolution de ses paramètres de foncteur afin de ne pas avoir de mauvaises surprises.

    Encore merci pour vos réponses.

  8. #8
    r0d
    r0d est déconnecté
    Membre expérimenté

    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2004
    Messages
    4 290
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Ain (Rhône Alpes)

    Informations professionnelles :
    Activité : Développeur informatique

    Informations forums :
    Inscription : Août 2004
    Messages : 4 290
    Billets dans le blog
    2
    Par défaut
    Citation Envoyé par Sant-kadog Voir le message
    Du coup, je dirais plutôt que la copie à chaque étape d'un algo permet d'oublier l'état courant du foncteur (et de repartir avec un foncteur tel qu'il était à l'état initial).
    C'est très intéressant... J'avoue que je ne voyais pas les choses comme ça, et je suis surpris par le fait que visiblement... tu as raison.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 11
    Dernier message: 25/08/2006, 16h00
  2. Constructeur par recopie
    Par Bebert71 dans le forum C++
    Réponses: 13
    Dernier message: 18/05/2006, 15h08
  3. [Débutant] Constructeur par recopie pour TComponent
    Par Runlevel dans le forum C++Builder
    Réponses: 9
    Dernier message: 06/05/2006, 16h58
  4. Constructeur par recopie
    Par KernelControl dans le forum C++
    Réponses: 2
    Dernier message: 29/12/2005, 12h24
  5. Constructeur par recopie
    Par sdebrois dans le forum Composants VCL
    Réponses: 13
    Dernier message: 21/10/2004, 14h47

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo