Discussion :

[ToTo13]

Bonjour,

je travaille sur des tableaux de grandes tailles, dont l'index d'accès à une case a besoin d'être au minimum un UINT32, voire un UINT64/size_t (mais très rarement). Par pure curiosité, j'aurai des questions à propos des performances.

Sur mes tableaux, je fais ENORMEMENT d'accès I/O. Est ce que j'aurai des écarts de performances (même faibles) si j'essai d'accéder aux cases de mon tableau en manipulant des UINT32 versus des UINT64 ?
Une autre façon de voir les choses serait : est ce que l'addition de deux UINT32 est beaucoup plus rapide que l'addition de deux UINT64 (car manipuler les indices d'un tableau revient à faire des additions pour passer d'un indice à l'autre) ? En toute naiveté de débutant, j'aurai envie de dire que c'est deux fois plus long... car deux fois plus de bits.

Merci par avance...

[Iradrille]

En toute naiveté de débutant, j'aurai envie de dire que c'est deux fois plus long... car deux fois plus de bits.

Çà marche pas comme ça

Un petit test rapide

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
#include <iostream>
#include <functional>
#include <chrono>
#include <vector>
 
template <class Function>
int timeIt(Function const& fct) {
	using namespace std::chrono;
	auto start = high_resolution_clock::now();
	fct();
	auto end = high_resolution_clock::now();
	return duration_cast<milliseconds>(end - start).count();
}
 
template <class Function>
double xTimes(Function const& fct, int n) {
	double ret = 0.0;
	for (int i = 0; i < n; ++i) {
		ret += timeIt(fct);
	}
	return ret /= n;
}
 
#define b32
#ifdef b32
typedef std::uint32_t type;
#else
typedef std::uint64_t type;
#endif
 
void foo(std::vector<int> & vec) {
	for (type i = 0u, n=(type)vec.size(); i < n; ++i) {
		vec[i] = 42;
	}
}
 
int main() {
	std::size_t size = 100'000'000u;
	int nTimes = 1'000;
 
	std::vector<int> vec(size);
	std::cout << xTimes([&vec]() { foo(vec); }, nTimes);
	std::cerr << vec[18];
	return 0;
}

Code :

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

1
2
3
4
5
x64, uint64 : 20.574ms
x64, uint32 : 20.596ms
 
x86, uint64 : 75.944ms
x86, uint32 : 20.359ms

Utiliser des uint64_t en 32 bits c'est ~4 fois plus lent (), le reste est plus ou moins équivalent. Maintenant en ajoutant des I/O la différence sera surement imperceptible.

Mais comme d'hab quand on parle performance... Une seule bonne réponse : profile et vois ce que ça donne

[ToTo13]

Merci pour la réponse !!!

[koala01]

Salut,

J'arrive un peu comme les carabiniers d'offenbach, je sais, mais je ne peux m'empêcher d'apporter mon grain de sel

Déjà, ce qu'il faut savoir, c'est que tous les processeurs travaillent avec ce que l'on peut appeler des "registres" qui permettent de représenter différentes données.

Ces registres sont, comme tout ce qui a trait aux données au niveau d'un ordinateur, composé d'un nombre bien précis de bits (d'interrupteurs "ON/OFF"). On peut partir du principe (bien qu'il y ait des variantes) que les registres d'une architecture 32 bits seront composés de... 32 bits et que ceux d'une architecture 64 bits seront composés... de 64 bits.

De manière générale, on peut dire que, toute chose étant égale par ailleurs, cela ne te prendra pas moins de temps de manipuler une donnée codée sur un nombre de bits inférieur à celui de ton registre que de manipuler une donnée dont le nombre de bits est strictement égal à celui de ton registre pour une simple raison : tous les bits du registre seront passés en revue quoi qu'il arrive (du moins, tant que l'on n'utilise pas les instructions qui permettent de travailler sur les demi ou les quart de registre )

C'est la raison pour laquelle le bench effectué par Iradille montre des performances identiques avec des int 32 bits et avec des int 64 bits sur une architecture 64 bits

Par contre, lorsque le nombre de bits nécessaire pour représenter une donnée dépasse le nombre de bits des registres, les choses commencent à se compliquer singulièrement au niveau du processeur car il ne pourra à chaque fois charger que... le nombre de bits dont ses registres dispose, ce qui l'obligera **forcément ** à scinder la donnée en plusieurs "morceaux" pour pouvoir la manipuler.

Evidemment, le simple fait d'avoir deux demi données à traiter, de prendre en compte le dépassement éventuel sur la première moitié afin de le reporter sur la deuxième moitié avant de pouvoir -- effectivement -- traiter la deuxième moitié de la donnée, ca prend... beaucoup de temps (au niveau du processeur, s'entend), et c'est -- en gros -- ce que le bench d'Iradille démontre

Mais il y a un autre problème, lorsque l'on envisage de travailler avec les tableaux. Il est connu sous le terme de cache-miss.

Le fait est que les données sont -- on va faire simple -- théoriquement stockée dans la RAM en attendant d'être utilisée. Or, s'il est possible d'avoir peu de mémoire très rapide ou beaucoup de mémoire "bien moins rapide", il n'y a aucun moyen d'avoir beaucoup de mémoire très rapide, pour la simple et bonne raison qu'il faut le temps "d'encoder l'adresse" à laquelle on veut accéder.

Du coup, le fondeurs de processeur ont rajouter un ("petit") espace de mémoire très rapide appelée "cache" directement au processeur dans l'idée que, si le processeur doit accéder à la RAM pour avoir des informations, autant qu'il demande les informations se trouvant dans "toute la mémoire contigüe qu'il peut" afin de la mettre dans le cache dans l'espoir que la "prochaine information" dont le processeur aura besoin puisse se trouver dans le cache.

De cette manière, l'accès à la "première" information s'avère **relativement** lent mais le temps passé à charger toutes les données contiguës a de grandes chances d'être "amorti" par le fait que nous pourrons accéder aux données contiguës beaucoup plus rapidement par la suite.

Seulement, voilà... La théorie est très belle, mais il arrive régulièrement que la deuxième donnée à laquelle on veut accéder n'était pas "assez proche" de la première que pour se trouver également dans le cache. Quand cela arrive, le processeur se trouve face à l'obligation de redemander l'accès à une adresse particulière de la RAM et... de charger à nouveau "autant que possible de donnée contigues à cette adresse" afin de ... charger à nouveau les données en cache (dans l'espoir que la prochaine donnée dont on aura besoin se trouve dans le cache).

Lorsque cela arrive, on parle de "cache miss" parce que le principe de la mise en cache a été prise en défaut et dont l'effet sera exactement l'inverse de celui que l'on espérait : on perd plus de temps à mettre les données en cache que l'on n'en gagne en accédant aux données qui se trouvent dans le cache

De manière générale, il faut savoir que dés qu'un pointeur rentre en jeu (un pointeur n'est jamais qu'une variable qui représente l'adresse mémoire à laquelle on devra trouver une variable bien précise ), le risque d'occasionner un cache miss en essayant d'accéder "à l'objet pointé" devient particulièrement important (car on n'a aucun moyen de savoir si l'objet pointé se trouve déjà dans le cache ou pas), tout comme le fait de passer "d'une extrême à l'autre" (ou peu s'en faut : il suffit de vouloir se "décaler" de plus de la taille d'une page de cache )d'un tableau pour essayer d'accéder à une donnée particulière.

Ce pourrait aussi être le cas avec une mauvaise politiques d'accès aux données d'un tableau 2D "linéarisé" : lorsque l'on essaye d'accéder à la colonne suivante alors que le tableau est "row major" ou, à l'inverse, lorsque l'on essaye d'accéder à la ligne suivante alors qu'il est "colon major" .

Mais, quoi qu'il en soit, le phénomène de cache misse sera très souvent bien plus nocif pour les performances que les éventuels ralentissements que nous pourrions remarquer au niveau des opérations de base sur les différents types primitifs