std::priority_queue et constructeurs par recopie

**Sant-kadog** · 22/01/2013, 20h10

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).

**Sant-kadog** · 22/01/2013, 20h58

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...

**r0d** · 23/01/2013, 12h40

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.

**koala01** · 23/01/2013, 14h07

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

**r0d** · 23/01/2013, 14h32

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.

**Iradrille** · 24/01/2013, 00h42

Envoyé par r0d

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.

**koala01** · 24/01/2013, 00h50

Et en relançant plusieurs fois l'application

Et en faisant une boucle séparée pour chaque cas (begin juste avant le début de la boucle, fin en sortie de boucle)

Il faut se méfier énormément des tests exécutés une seule et unique fois, car il y a tant de choses qui peuvent faire varier les résultats

**Sant-kadog** · 24/01/2013, 01h01

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 ...

)

Envoyé par r0d

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.

**Iradrille** · 24/01/2013, 01h02

Envoyé par koala01

Et en relançant plusieurs fois l'application

Et en faisant une boucle séparée pour chaque cas (begin juste avant le début de la boucle, fin en sortie de boucle)

Il faut se méfier énormément des tests exécutés une seule et unique fois, car il y a tant de choses qui peuvent faire varier les résultats

Relancé plusieurs fois toujours les mêmes résultats (ou du moins, la même tendance, ça varie forcément légèrement). Mais oui, j'aurais du faire une moyenne sur une centaine de tests.

Pour la boucle je test ça.

edit: bon ok, je m'avoue vaincu

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
72
73
74
75
76
77
78
79
80
81
82
83
84
#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
	const size_t TESTS = 100U;
 
	double timeA, timeB, timeC, dFreq;
	LARGE_INTEGER begin, end, freq;
	QueryPerformanceFrequency(&freq);
	dFreq = (double)freq.QuadPart / 1000.0; // ms;
 
	timeA = timeB = timeC = 0.0;
 
	srand((unsigned int)time(NULL));
 
	int *values = new int[SIZE];
 
	for(size_t n=0; n<TESTS; ++n) {
		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)>> queueB(CompFct, containerB);
		std::priority_queue<int, std::vector<int>, bool(*)(int, int)> queueC(CompFct, containerC);
 
		for(size_t i=0; i<SIZE; ++i) {
			values[i] = rand();
		}
 
		QueryPerformanceCounter(&begin);
		for(size_t i=0; i<SIZE; ++i) {
			queueA.push(values[i]);
		}
		QueryPerformanceCounter(&end);
		timeA += (end.QuadPart - begin.QuadPart) / dFreq;
 
		QueryPerformanceCounter(&begin);
		for(size_t i=0; i<SIZE; ++i) {
			queueB.push(values[i]);
		}
		QueryPerformanceCounter(&end);
		timeB += (end.QuadPart - begin.QuadPart) / dFreq;
 
		QueryPerformanceCounter(&begin);
		for(size_t i=0; i<SIZE; ++i) {
			queueC.push(values[i]);
		}
		QueryPerformanceCounter(&end);
		timeC += (end.QuadPart - begin.QuadPart) / dFreq;
	}
 
	timeA /= (double)TESTS;
	timeB /= (double)TESTS;
	timeC /= (double)TESTS;
 
	std::cout << "temps d'insertion de " << SIZE << " random elements, moyenne de " << TESTS << " tests\n"
		<< "foncteur: " << timeA << "ms\n"
		<< "std::function: " << timeB << "ms\n"
		<< "fonction libre: " << timeC << "ms\n";
 
	delete values;
 
	return EXIT_SUCCESS ;
}

Temps d'insertion de 1 000 000 random elements, moyenne de 100 tests
32 bits:
foncteur: 17.8701ms
std::function: 59.7487ms
fonction libre: 23.1814ms

64 bits:
foncteur: 16.0669ms
std::function: 47.2518ms
fonction libre: 19.3947ms

**koala01** · 24/01/2013, 01h15

Ben, je viens de modifier un tout petit peu ton code pour tester séparément les différentes possibilités sous la forme de

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
72
73
74
75
76
77
78
79
#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);
 
		QueryPerformanceCounter(&begin);
	for(size_t i=0; i<SIZE; ++i) {
 
		int val = rand();
 
		// foncteur
		queueA.push(val);
 
	}
    QueryPerformanceCounter(&end);
    timeA = (end.QuadPart - begin.QuadPart) / dFreq;
    QueryPerformanceCounter(&begin);
    for(size_t i=0; i<SIZE; ++i) {
 
		int val = rand();
		// std::function
		queueC.push(val);
 
	}
    QueryPerformanceCounter(&end);
    timeC = (end.QuadPart - begin.QuadPart) / dFreq;
    QueryPerformanceCounter(&begin);
    for(size_t i=0; i<SIZE; ++i) {
 
		int val = rand();
 
		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 ;
}

Chose assez surprenante, le foncteur devient globalement plus efficace qu'une fonction libre (34 à 35 pour le foncteur contre 38 à 39 pour la fonction libre ) , mais std ::function crève tous les plafond avec des valeurs de l'ordre de 101 à 104

(en 64 bits)

**Iradrille** · 24/01/2013, 01h32

Envoyé par koala01

Chose assez surprenante, le foncteur devient globalement plus efficace qu'une fonction libre (34 à 35 pour le foncteur contre 38 à 39 pour la fonction libre ) , mais std ::function crève tous les plafond avec des valeurs de l'ordre de 101 à 104

(en 64 bits)

Au moins on arrive au même résultat, mais après avoir retester la 1ere version en rajoutant juste une boucle pour faire la moyenne de 100 tests, j'obtiens des résultats comparable à ceux que j'obtenais (fonction libre plus rapide qu'un foncteur)

Donc un foncteur est plus rapide si on insère tous les éléments "en même temps", sinon une fonction libre est plus rapide.

Si quelqu'un à une explication à ça, je prend, car j'avoue ne pas trop comprendre et être assez curieux de savoir.

**koala01** · 24/01/2013, 02h18

Il faudrait sans doute s'intéresser à l'assembleur généré pour s'en assurer, mais voici l'interprétation que j'en ferais a priori:

Lorsque l'on effectue tous les tests dans la même boucle, les calculs sont un peu biaisés par le fait que l'on "change régulièrement de contexte" (bon, le terme n'est peut etre pas le bon

):

Pour chaque test, tu as deux QueryPerformance + une actions + un calcul.

Typiquement, un calcul demande deux acu (ou un acu et une adresse mémoire), mais l'action va aussi avoir besoin d'un certain nombre d'acu, ce qui fait que l'on va passer son temps à charger différentes valeurs dans différents acus, et cela demande malgré tout du temps.

Comme le chargement de ces valeurs se fait, en gros, entre les deux QueryPerformance, il n'en faut pas beaucoup plus pour que cela fausse tout à fait les calculs

Et comme on ne peut pas dire que la précision dont on dispose (de l'ordre de la milli seconde) soit faramineuse...

Par contre, quand on effectue les différents tests dans des boucles séparées il y a déjà beaucoup moins de "changement de contexte" (le terme n'est peut etre pas plus approprié

) dans le sens où on a un QueryPerformance suivi du million d'insertion, suivi du deuxième QueryPerformance et du calcul.

On peut alors penser que le foncteur ou que le pointeur de fonction reste dans le même acu durant toute la durée du million d'insertions, ce qui va relativiser énormément le temps qu'il faut pour effectuer le chargement de l'acu

Et comme on n'effectue le calcul qu'une fois sur une durée plus importante, on gagne aussi au niveau de l'imprécision de l'horloge

Mais l'inversion de la différence (qui reste toujours grosso modo de l'ordre des 10%) vient sans doute du fait que, bien que la fonction soit inlinée, on passe par un pointeur de fonction, ce qui fait que le code n'est, en définitive, plus inliné du tout pour le pointeur de la fonction à cause de l'indirection occasionnée par celui-ci, alors que, pour le foncteur, le code reste inliné.

Cela voudrait donc sans doute aussi impliquer que, si le foncteur est bel et bien une structure vide à l'exception de l'opérateur (), la copie se réduit en définitive à une no-op ou quelque chose de très proche (ce qui serait parfaitement plausible, vu qu'il n'y a... aucun membre à copier

).

Maintenant, ce n'est qu'une supposition, car il faudrait vraiment aller voir du coté de l'assembleur généré pour avoir confirmation de cela, mais l'explication semble pour le moins plausible, non

**JolyLoic** · 24/01/2013, 09h08

Envoyé par koala01

Chose assez surprenante, le foncteur devient globalement plus efficace qu'une fonction libre (34 à 35 pour le foncteur contre 38 à 39 pour la fonction libre ) , mais std ::function crève tous les plafond avec des valeurs de l'ordre de 101 à 104

(en 64 bits)

Ce qui me surprend ici, c'est qu'il y ait surprise

Que les foncteurs puissent être plus rapides qu'une fonction libre, c'est normal, car ils facilitent les optimisations, et plus particulièrement l'inlining, par rapport à un pointeur de fonction (voir comparatifs qsort / std::sort par exemple).

Que std::function soit plus lente, normal aussi : Le fait d'être une abstraction au dessus de plein de possibilités (type erasing) implique de passer par des pointeurs intermédiaires à déréférencer, et par la non possibilité d'inlining. Un std::function est très bien pour un callback, où la flexibilité de ce qu'on peut mettre dedans est importante, pas pour configurer un algorithme où les performances jouent.

**r0d** · 24/01/2013, 09h44

Le fait que std::function est lent, c'est bien connu. Ce qu'on sait moins - en tout cas moi - c'est ce qu'il en est pour les lambdas. Est-ce que les performances d'une lambda sont différentes de celles d'une fonction libre?

**r0d** · 24/01/2013, 09h47

Envoyé par Sant-kadog

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.

**JolyLoic** · 24/01/2013, 09h54

Envoyé par r0d

Le fait que std::function est lent, c'est bien connu. Ce qu'on sait moins - en tout cas moi - c'est ce qu'il en est pour les lambdas. Est-ce que les performances d'une lambda sont différentes de celles d'une fonction libre?

Un lambda est juste une écriture plus sympathique d'un foncteur. Donc la performance devrait être identique, et optimale.

**Iradrille** · 24/01/2013, 10h53

@koala01 C'est probablement la bonne explication (ou du moins elle parait probable)

Envoyé par r0d

Le fait que std::function est lent, c'est bien connu. Ce qu'on sait moins - en tout cas moi - c'est ce qu'il en est pour les lambdas. Est-ce que les performances d'une lambda sont différentes de celles d'une fonction libre?

J'ai refait les tests avec une lamba, le temps d'exec colle avec celui d'un foncteur ou celui d'une fonction libre en fonction de comment on crée la queue

Code :

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

1
2
3
4
5
auto CompLmb = [](int a, int b)->bool { return a < b; };
std::vector<int> containerD(SIZE);
 
std::priority_queue<int, std::vector<int>, bool(*)(int, int)> queueD(CompLmb, containerD); // syntaxe pointer de fonction -> performance identique à une fonction libre
std::priority_queue<int, std::vector<int>, decltype(CompLmb)> queueD(CompLmb, containerD); // performance identique à un foncteur

edit: ce qui au final est normal, une lamba peut être vu comme une fonction libre quand elle ne capture aucune variable

**koala01** · 24/01/2013, 12h06

Envoyé par JolyLoic

Ce qui me surprend ici, c'est qu'il y ait surprise

Que les foncteurs puissent être plus rapides qu'une fonction libre, c'est normal, car ils facilitent les optimisations, et plus particulièrement l'inlining, par rapport à un pointeur de fonction (voir comparatifs qsort / std::sort par exemple).

Disons que, comme tu as pu le remarquer, je n'ai été surpris que dans un premier temps, puis, je me suis repris, et j'ai même trouvé une explication qui semblait logique (basée effectivement sur l'inlining, entre autres choses

std::priority_queue et constructeurs par recopie

C++

Discussions similaires

Partager

Partager