Discussion :

[r0d]

Bonjour,

il m'arrive un truc je n'y comprends rien.
L'idée est la suivante: je créé un tableau "c-style", ainsi qu'une fonction exists qui regarde si un élément donné k existe dans ce tableau.
J'utilise une méthode basique, brutale, moche, je sais qu'on peut faire beaucoup mieux et surtout beaucoup plus rapide, mais là n'est pas le problème.

Prenons donc ce bout de code:

Code cpp :

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
#include <iostream>
#include <chrono>
 
using namespace std;
 
bool exists(int ints[], int size, int k)
{
	bool found = false;
	int i = 0;
	while (!found && i<size)
		found = (ints[i++] == k);
	return found;
}
 
void main()
{
	const int size = 100000;
	const int k = 90000;
	int ints[size];
 
	for (int i = 0; i < size; ++i)
		ints[i] = i; 
 
	auto start = chrono::steady_clock::now();
	cout << exists(ints, size, k) << endl;
	cout << chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now() - start).count() << endl << endl;
 
	start = chrono::steady_clock::now();
	cout << exists(ints, size, k) << endl;
	cout << chrono::duration_cast<chrono::nanoseconds>(chrono::steady_clock::now() - start).count() << endl << endl;
 
	getchar();
}

Ce que je fais, c'est que je fais exactement 2 fois la même chose. Mais voilà l'output que j'obtiens:

Code :

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

1
2
3
4
5
1
395370
 
1
252556

La première recherche et plus lente que la deuxième!
Et c'est systématique, quelques soient les options de compilation que je choisis! Même en mode Debug!
Je suis sous Windows, je compile avec Visual Studio 2017.
J'ai relancé le test des dizaines de fois, et j'ai toujours le même ordre de différence de vitesse d'exécution.

Comment est-ce possible? J'imagine que le compilateur doit effectuer quelque optimisation? Mais c'est étrange puisque le résultat est le même en Debug et/ou sans optimisation.
Une idée?

[Bousk]

My guess : lors du premier traitement il y a mise en cache, lors du 2eme c'est deja en cache.

Aussi, il me semble qu'utiliser ce genre de clock pour ce genre de mesures n'est pas top. Tu peux essayer avec la high_resolution_clock, mais l'implementation peut etre la meme, sinon faut directement taper dans les fonctions systemes, QueryPerformanceCounter sous Windows.

[dalfab]

L'écart des temps de traitement n'est pas directement lié au code, il est dû à ce qui se passe à l'intérieur même du processeur.
Le temps de transfert d'une donnée de la RAM vers la mémoire cache est nettement plus important que les calculs que tu effectues.
L'autre chose "compliquée" pour le processeur dans ton code est la prédiction de branchement. Quand il y a un test, le processeur essaie de deviner ce qu'il va se passer. Quand il y arrive, le saut qui suit le test est quasi-immédiat, quand il se trompe il va perdre du temps.
Dans ton code les actions potentiellement "longues" sont donc :
* le test : !found (le test sera 90000 fois vrai et une fois faux.)
* le test : i<size (le test sera toujours vrai ici.)
* la lecture de : ints[i] (il faudra parfois attendre que la mémoire parvienne au cache.)
* le return de la fonction (mais il n'y en a qu'un.)
* toutes les autres se font en moins d'une ns chacune.

Quand tu appelles ta fonction une seconde fois :
* le processeur se souvient que la dernière fois les 2 tests étaient presque toujours vrais, il va miser sur cela et devrait moins souvent commettre d'erreur de prédiction de branchement.
* il y aura un peu plus de ints[i] qui seront encore dans le cache, et donc il y aura un peu moins de faute de page.

Je pense que c'est surtout la mémoire cache qui est la cause ici.

[Kannagi]

@dalfab Inutile de parlé des failles meltdown et spectre ça n'a aucun rapport, surtout que ce genre d'optimisation est faite juste pour optimiser la pipeline (qu'on optimise manuellement sur certain autre processeur comme celui du CELL sur la PS3 mais bref c'est pas le sujet ici).

Sinon oui c'est du a la mémoire cache , si tu veux avoir un temps pareil il faudrait faire un flush en asm(pour vider la mémoire cache ).

[Luc Hermitte]

A noter qu'il existe `std::find` et `std::find_if` qui ne souffrent pas du syndrome du SESE -> moins de tests redondants.

Si tu veux mesurer les perfs de ce genre de code, regarde des frameworks comme google.Benchmark. Ils sont fait pour ça -> les benchs sont faits sur des traitements réalisés plusieurs fois, il y a de quoi faire sauter les optimisations de type "variable non utilisée", etc.

[r0d]

Ok, merci pour vos réponses

A noter qu'il existe `std::find` et `std::find_if` qui ne souffrent pas du syndrome du SESE -> moins de tests redondants.

Dans mon cas, j'ai finalement opté pour un std::binary_search qui, dans mon contexte, semble offrir les meilleurs résultats.

[koala01]

Salut,

Ok, merci pour vos réponses
Dans mon cas, j'ai finalement opté pour un std::binary_search qui, dans mon contexte, semble offrir les meilleurs résultats.

Ah, ben, de fait : si un tableau est trié (une question en passant l'est il "d'origine" ou doit-il être trié de manière explicite ), la recherche dichotomique présente par nature une complexité bien moindre (en O(log(n) contre une complexité en O(n) ), si bien que, sur 100 000 éléments, tu devrais pouvoir trouver l'élément recherché en 15 mouvements contre -- dans le pire des cas -- 100 000