Désoptimisation et comment faire un benchmark ?

Hello,

j'essaye d'avoir un code simple de benchmarking, mais mon cas semble trop simple et complètement optimisé par le compilo...
Voici le code

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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <chrono>
#include <iostream>
struct A {
	enum class Type { B, C, };
	A(Type _t) : type(_t) {}
	virtual ~A() = 0 {}
	Type type;
	template<class T>
	bool is() const { return T::StaticType == type; }
	template<class T>
	bool is_using_dynamic_cast() const { return dynamic_cast<const T*>(this) != nullptr; }
	template<class T>
	T* as() { return static_cast<T*>(this); }
};
struct B : A {
	static const Type StaticType = Type::B;
	B() : A(Type::B) {}
	size_t value() const { return 1; }
};
struct C : A {
	static const Type StaticType = Type::C;
	C() : A(Type::C) {}
};
int main() {
	B b;
	A* a = &b;
	{
		size_t n = 0;
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (auto b = dynamic_cast<B*>(a))
			{
				n += b->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with dynamic_cast" << std::endl;
	}
	{
		size_t n = 0;
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (typeid(*a) == typeid(B))
			{
				n += static_cast<B*>(a)->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with typeid" << std::endl;
	}
	{
		size_t n = 0;
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (&typeid(*a) == &typeid(B))
			{
				n += static_cast<B*>(a)->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with &typeid" << std::endl;
	}
	{
		size_t n = 0;
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (a->is_using_dynamic_cast<B>())
			{
				n += a->as<B>()->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with is_using_dynamic_cast (internal dynamic_cast)" << std::endl;
	}
	{
		size_t n = 0;
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (a->is<B>())
			{
				n += a->as<B>()->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with is (enum)" << std::endl;
	}
	return 0;
}

Rien de fabuleux mais voilà quelques sorties

Code:

1
2
3
4
5
1479042506 ns with dynamic_cast
541149801 ns with typeid
386570206 ns with &typeid
1355755663 ns with is_using_dynamic_cast (internal dynamic_cast)
256 ns with is (enum)

Code:

1
2
3
4
5
1479745740 ns with dynamic_cast
536910174 ns with typeid
385768924 ns with &typeid
1392601325 ns with is_using_dynamic_cast (internal dynamic_cast)
0 ns with is (enum)

Code:

1
2
3
4
5
1473431996 ns with dynamic_cast
554813324 ns with typeid
384597977 ns with &typeid
1270466484 ns with is_using_dynamic_cast (internal dynamic_cast)
0 ns with is (enum)

On peut voir que le dernier cas, celui qui m'intéresse particulièrement, est un peu... rapide ?
Vu que ça implique du template, et que le main est simple, je pense que c'est optimisé et calculé pendant la compilation...

Du coup j'ai tenté avec un genre de class intermédiaire

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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include <chrono>
#include <iostream>
struct A {
	enum class Type { B, C, };
	A(Type _t) : type(_t) {}
	virtual ~A() = 0 {}
	Type type;
	template<class T>
	bool is() const { return T::StaticType == type; }
	template<class T>
	bool is_using_dynamic_cast() const { return dynamic_cast<const T*>(this) != nullptr; }
	template<class T>
	T* as() { return static_cast<T*>(this); }
};
struct B : A {
	static const Type StaticType = Type::B;
	B() : A(Type::B) {}
	size_t value() const { return 1; }
};
struct C : A {
	static const Type StaticType = Type::C;
	C() : A(Type::C) {}
};
#include <functional>
class Checker {
public:
	Checker(std::function<bool(const A*)> _f) : func(_f) {}
	bool operator()(const A* a) const { return func(a); }
private:
	std::function<bool(const A*)> func;
};
int main() {
	B b;
	A* a = &b;
	{
		size_t n = 0;
		Checker check([&](const A* a) { return dynamic_cast<const B*>(a) != nullptr; });
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (check(a))
			{
				n += static_cast<B*>(a)->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with dynamic_cast" << std::endl;
	}
	{
		size_t n = 0;
		Checker check([&](const A* a) { return typeid(*a) == typeid(B); });
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (check(a))
			{
				n += static_cast<B*>(a)->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with typeid" << std::endl;
	}
	{
		size_t n = 0;
		Checker check([&](const A* a) { return &typeid(*a) == &typeid(B); });
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (check(a))
			{
				n += static_cast<B*>(a)->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with &typeid" << std::endl;
	}
	{
		size_t n = 0;
		Checker check([&](const A* a) { return a->is_using_dynamic_cast<B>(); });
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (check(a))
			{
				n += a->as<B>()->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with is_using_dynamic_cast (internal dynamic_cast)" << std::endl;
	}
	{
		size_t n = 0;
		Checker check([&](const A* a) { return a->is<B>(); });
		const auto start = std::chrono::high_resolution_clock::now();
		for (size_t i = 0; i < 100000000; ++i)
		{
			if (check(a))
			{
				n += a->as<B>()->value();
			}
		}
		const auto end = std::chrono::high_resolution_clock::now();
		const auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count();
		std::cout << elapsed << " ns with is (enum)" << std::endl;
	}
	return 0;
}

La sortie semble plus normale:

Code:

1
2
3
4
5
1193004782 ns with dynamic_cast
561807262 ns with typeid
449779071 ns with &typeid
1097718778 ns with is_using_dynamic_cast (internal dynamic_cast)
141872748 ns with is (enum)

Code:

1
2
3
4
5
1713590819 ns with dynamic_cast
723503932 ns with typeid
553266825 ns with &typeid
1423687229 ns with is_using_dynamic_cast (internal dynamic_cast)
154689676 ns with is (enum)

Et les résultats vont dans le sens que j'attends, mais est-ce vraiment probant selon vous ?

Merci

Mais que veux-tu mesurer?

Après tout, si le compilateur calcule complètement le résultat, c'est totalement optimal: O(0).

Bonjour,

Chercher à différencier les complexités en effectuant des mesures de durée est souvent trompeur (on voit apparaître des problèmes de mise en cache, de mauvaise prédiction de branchement du processeur ou des optimisations du compilateur.)
Ici le résultat attendu est évidemment : dynamic_cast<> est le moins performant (parcours de plusieurs tables) suivi de typeid() (accès indirect à une table), la lecture d'une donnée (accès direct) est plus optimal en temps.
Mais chacun à son avantage; dynamic_cast<> fonctionne aussi quand *a est un dérivé de B que la comparaison des typeid() ratera, et la donnée directe peut augmenter la taille de tous les objets.
Dans le dernier cas le compilateur a "vu" que l'on ajoutait 100000000 fois 1 et l'a remplacé par un n=100000000, pour les autres cas, il a moins réussi l'optim.

Et attention, comparer les adresses des typeid() n'est pas une méthode valide, ça ne fonctionnera pas si l'objet vient d'un autre module de compilation . Il faut faire if ( std::type_index(typeid(*a)) == std::type_index(typeid(B)) )

Citation:

Envoyé par ternel

Après tout, si le compilateur calcule complètement le résultat, c'est totalement optimal: O(0).

Le compilo optimise parce que ce code est simple. Ce a est sensé venir d'une lib à terme et non du main - pas grand intérêt sinon.
Il n'y aura pas de dérivée de B, que des dérivées de A. Mais ça n'est pas définitif et j'ai une version qui gèrerait ça si besoin.
La donnée directe est uniquement ce flag enum donc la taille des objets ça va ça bouge pas trop. Et ce sont des objets à durée de vie relativement courtes.

Pour ne pas optimiser n'importe comment le code, il faut donner le minimum d'information au compilo.

1. Empêcher le compilateur de déduire les types réels des objets:
- faire des fonctions avec les types de base. Le compilo ne propage pas toujours les types réels. Ne pas en faire une fonction template puisque le compilo est plus susceptible de propager les types réels.
- construire des types virtuelles avec de l'allocation dynamique (ce que fait std::fonction). Mais ce n'est pas toujours suffisant, clang est plutôt bon pour le détecter et peut même supprimer des allocations dynamiques.
- initialiser les valeurs de test avec des entrées utilisateur.

2. Empêcher le compilateur de supprimer le code:
- afficher/écrire les valeurs de résultat. Généralement, je mets tous dans un tableau que j'affiche après.
- les conditions doivent être sur des valeurs variables. Le compilateur peut faire sauter les conditions sinon.

Ici, la condition est réévaluée parce que le compilo ne fait pas de supposition sur le comportement de std::function: il y une fonction virtuelle -> comportement réel inconnue -> effet de bord possible -> pas d'optimisation.

Quelque chose qui fonctionne est de faire un cpp pour les tests (ou une lib) et mettre la boucle d'appel du tests dans le main. Ainsi, le compilateur n'optimise pas la fonction de test en fonction des types réels puisqu'il ne les connaît pas.
Et ne surtout pas compiler avec des trucs comme -flto qui optimise la phase de link.

Et si tu veux optimiser une bibliothèque, fais une bibliothèque.