Discussion :

[pingouin84k]

Bonjour,

Jusqu'à présent j'ai codé en Matlab mes modèles de simulations de fluide. Jusqu'à présent tout le monde me disait que je devrais utiliser c++ (ou fortran) c'est plus rapide.
Aujourd'hui je me suis dit qu'on allait essayer... Je n'arrive pas à la même conclusion, j'aimerai donc un peu de vos lumières (je suis débutant en c++).

En Matlab il faut à mon PC 0.176 secondes pour faire la somme élément à élément de deux matrices contenant 5000x5000 nombres aléatoires (double précision).
En C++ il lui faut 1.46 (presque 10 fois plus lent)!

Alors comme je débute en C++, je ne fais peut être pas les choses correctement. Je ne suis pas arrivé à trouver de bibliothèque qui me permette de faire des opérations à la volé entre 2 tableaux en c++ comme on peut le faire en Matlab. J'ai donc 2 boucles imbriquées... Bref, je vous met le code ci-dessous (les fonctions tic toc sont codés ailleurs, j'ai utilisé ça: http://www.cplusplus.com/reference/ctime/).

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
#include "tic_toc.h"
 
#include <iostream>
#include <stdlib.h>
#include <time.h>
 
 
using namespace std;
 
 
int main()
{
 
	int n(5000);
 
	double* A = new double[n*n];
	double* B = new double[n*n];
	double* C = new double[n*n];
 
 
	int i(0);
	int j(0);
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
 
			A[i*j] = float(rand() % 100000)/100000;
			B[i*j] = float(rand() % 100000)/100000;
 
		}
	}
 
 
 
	tic();
 
	for (i = 0; i < n; i++)
	{
		for (j = 0; j < n; j++)
		{
			C[i*j] = A[i*j] + B[i*j];
		}
	}
 
	toc();
 
	delete[] A;
	delete[] B;
	delete[] C;
 
 
	system("pause");
	return 0;
}

J'ai quand même remarqué qu'en utilisant ça

Code :

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

1
2
3
4
for (i = 0; i < n*n; i++)
	{
		C[i] = A[i] + B[i];
	}

le temps de l'opération tombait 0.23 secondes.


Pouvez vous me m'expliquer si bon benchmark est comparable, s'il y a d'autres moyens de faire en c++ (une librairie?) etc.
NB: Je ne parallélise pas car mon Matlab s’exécute sur un cœur. A terme je compte bien passer en c++ pour pouvoir paralléliser mes modèles.


Merci d'avance pour votre aide/explications.

[fcharton2]

Bonjour,

Ton calcul d'indice est étrange: ça ne devrait pas être i*n+j, ou quelque chose du genre?

Sur le benchmark, ça parait un peu étonnant, tu lances une boucle qui contient 25 millions d'itérations, ça ne devrait pas prendre plus d'une seconde (même les 0,23 secondes pour la seconde version paraissent énormes, à moins que tu travailles sur une machine de musée). Peux tu regarder les paramètres de ton compilateur:
- les optimisations sont activées?
- tu n'es pas dans un mode de débogage qui vérifie chaque accès à chaque tableau?

Francois

[pingouin84k]

Hum en fait en matlab on peut faire un tableau de 5000x5000 sans soucis. En c++ je n'ai pas trouvé comment faire (je débute vraiment, avant le benchmark j'en étais à "Hello World"). J'ai pu faire des petit tableau, mais passé une limite (100x100) je me retrouve avec un stack overflow (pas la moindre idée d'où ça vient). Sur internet, j'ai cru comprendre qu'il fallait passer par un pointeur avec un constructeur et un destructeur... Mais que dans le process on ne pouvait plus que faire des tableaux à une dimension.
Bon pour le moment l'important c'est qu'il y ait autant d'éléments dans un code que dans l'autre.

Je ne travaille pas avec une pièce de musée ^_^ enfin je ne crois pas!
Voilà ma config en quelques lignes:
Proc i7 930 @2.8Ghz 8 threads
RAM 6 Go
Asus P6T6 WS.

Concernant les paramètres du compilateur je vais chercher. Comme je débute, ça non plus je ne sais pas faire (vais apprendre et je reviens).

Merci pour ta réponse en tout cas!

[foetus]

Hum en fait en matlab on peut faire un tableau de 5000x5000 sans soucis. En c++ je n'ai pas trouvé comment faire

Au moins 2 façons . Soit avec des malloc soit:

Code :

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

1
2
    double A[5000][5000];
    memset(A, 0, 5000*5000*sizeof(double);

Mais ici pas besoin de memset puisque tu fais une initialisation aléatoire

Et pas besoin de free à la fin.

Et l'autre truc, il me semble, c'est la précision. Si tu n'as pas besoin de précision, utilise des float au lieu de double.

Édit: tu as oublié d’initialiser la graine documentation rand

[fcharton2]

Hum en fait en matlab on peut faire un tableau de 5000x5000 sans soucis. En c++ je n'ai pas trouvé comment faire (je débute vraiment, avant le benchmark j'en étais à "Hello World"). J'ai pu faire des petit tableau, mais passé une limite (100x100) je me retrouve avec un stack overflow (pas la moindre idée d'où ça vient). Sur internet, j'ai cru comprendre qu'il fallait passer par un pointeur avec un constructeur et un destructeur... Mais que dans le process on ne pouvait plus que faire des tableaux à une dimension.

En gros, en C++, il faut allouer l'espace dont tu as besoin pour tes tableaux. Ce que tu déclares dans la pile (avec des choses comme double montableau[100][100]) est limité à la taille de la pile, d'où le stack overflow

Pour l'allocation, ce que tu fais (avec new) est globalement correct. Tu peux aussi utiliser un vector<double>, (vector<double> v(n*n,0.0); ). Et tu peux aussi fabriquer des tableaux à deux dimensions, soit comme des vector< vector<double> >, soit comme des double **, dont tu réalloues toutes les lignes.

A mon avis, ton problème vient d'ailleurs. Il n'y a pas de raison que la copie mette autant de temps. Donc regarde la configuration de ton compilateur. C'est un bon investissement, de toutes façons.

Francois

[JolyLoic]

Pour l'allocation, ce que tu fais (avec new) est globalement correct. Tu peux aussi utiliser un vector<double>, (vector<double> v(n*n,0.0); ). Et tu peux aussi fabriquer des tableaux à deux dimensions, soit comme des vector< vector<double> >, soit comme des double **, dont tu réalloues toutes les lignes.

C'est généralement une mauvaise idée (sauf si vraiment très grands tableaux), ça on remplace une allocation mémoire par plein de plus petites, ce qui est coûteux...

[JolyLoic]

J'ai quand même remarqué qu'en utilisant ça

Code :

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

1
2
3
4
for (i = 0; i < n*n; i++)
	{
		C[i] = A[i] + B[i];
	}

le temps de l'opération tombait 0.23 secondes.

Cette seconde façon de faire est bien meilleurs, et en plus, elle n'a pas d’erreur dans le calcul des indices Je serais curieux de savoir combien de temps prend la première façon de faire corrigée (qui du coup va bénéficier du cache mémoire, alors que ta version avec les indices farfelus n'en bénéficie pas).

Mais si tu veux rivaliser avec Matlab, il te faut probablement tirer parti de la vectorisation du ton processeur (le fait qu'il peut simultanément faire des additions de plusieurs double d'un coup, sans pour autant programmer en parallèle). Certains compilateurs arrivent dans des cas simples à utiliser ces instructions sur des cas simples, je ne sais pas si ça a été le cas ici. Peut-être en regardant le code généré ?

Sinon, pour ce genre de choses, j’utiliserais une bibliothèque existante, comme par exemple eigen ou nt² (je ne peux juger de la qualité, ça fait longtemps que je n'ai pas fait de calcul scientifique dans mon boulot, mais les deux ont l'air à jour et maintenues). Lire par exemple http://eigen.tuxfamily.org/dox/Topic...enExample.html pour une idée de ce qui peut se passer dans ce genre de bibliothèques.

[pingouin84k]

Bonjour à tous et merci pour vos réponses!

@JolyLoic, fcharton2
Oui effectivement mon calcul d'indice était farfelu. Je n'y avais même pas fait attention (la fatigue ).
En corrigeant i*j par i*n+j ça va plus vite, 0.25 seconde, c'est presque aussi rapide qu'avec une seule boucle.
J'imagine que pour faire de la vectorisation de double, ce n'est pas vraiment à la portée d'un débutant...
Étant donné que la parallélisation en c++ semble bien plus simple qu'en Matlab, j'ai bon espoir d'arriver à quelques chose de plus performant au final.

Et comme je fais de la mécanique des fluides avec écoulement réactifs, oui j'ai de nombreux "très grands" tableaux. De manière générale avec Matlab j'avais typiquement des tableaux de 5.000 à 10.000 cellules. En passant en c++ avec de la parallélisation, j'ai bon espoir de pouvoir monter à 100.000 cellules sans trop impacter mon temps de calcul global.

@foetus
J'ai copié collé ton bout de code et je me retrouve avec Stack Overflow.

@fcharton2
J'utilise MS Visual C++ 2010 Express. J'ai cherché les options de compilation, pas trouvé. Donc je ne peux dire quels sont les options d'optimisation il y a. J'ai exécuté mon code alors qu'il y a écrit "Debug" dans le drop box "Configurations de solutions". En mode Release j’obtiens sensiblement le même résultat.

[JolyLoic]

@JolyLoic, fcharton2
Oui effectivement mon calcul d'indice était farfelu. Je n'y avais même pas fait attention (la fatigue ).
En corrigeant i*j par i*n+j ça va plus vite, 0.25 seconde, c'est presque aussi rapide qu'avec une seule boucle.

Bien ce qu'il me semblait... C'est là qu'on voit l'intérêt du cache de mémoire du processeur. Après, si tu avais de plus petits tableaux, peut-être que l'écart entre la solution à 2 boucles et la solution à 1 boucle serait plus sensible.

J'imagine que pour faire de la vectorisation de double, ce n'est pas vraiment à la portée d'un débutant...

Ce n'est pas non plus totalement impossible pour des calculs simples comme ça, là où c'est moins simple, c'est quand la complexité des calculs augmente, ou quand tu veux faire des solutions génériques... Mais de toute manière, une bonne bibliothèque est là pour que tu n'aies pas à te poser ce genre de questions bas niveau, et que tu puisses te concentrer sur ta valeur ajoutée.

Étant donné que la parallélisation en c++ semble bien plus simple qu'en Matlab, j'ai bon espoir d'arriver à quelques chose de plus performant au final.

Vectorisation et parallélisation ne sont pas concurrents, mais complémentaires.

@fcharton2
J'utilise MS Visual C++ 2010 Express. J'ai cherché les options de compilation, pas trouvé. Donc je ne peux dire quels sont les options d'optimisation il y a. J'ai exécuté mon code alors qu'il y a écrit "Debug" dans le drop box "Configurations de solutions". En mode Release j’obtiens sensiblement le même résultat.

Par défaut, la configuration Release contient les options d'optimisation classiques qui marchent bien pour avoir du code rapide dans le cas général. Donc, globalement, si tu travailles en Release, pas en Debug, tu n'es pas loin des performances optimales du compilateur.

[pingouin84k]

Bon je viens de rebooter le PC et surprise, mon code est bien plus rapide.
Déjà il y a une nette amélioration en passant de Debug à Release (alors que je l'avais pas remarqué avant de rebooter).

Mais la différence la plus flagrante c'est entre la solution à une boucle et la solution à deux boucles. Il y a un facteur 2 entre les deux.
La solution a une boucle tourne plus vite que l'opération sur Matlab
J'en suis bien content, mais j'aimerai bien comprendre ^^

Mais de toute manière, une bonne bibliothèque est là pour que tu n'aies pas à te poser ce genre de questions bas niveau, et que tu puisses te concentrer sur ta valeur ajoutée.

Tu m’indiquerais pas le nom de cette bibliothèque à tout hasard
Et encore merci pour toutes ces réponses!

[fcharton2]

Mais la différence la plus flagrante c'est entre la solution à une boucle et la solution à deux boucles. Il y a un facteur 2 entre les deux.
La solution a une boucle tourne plus vite que l'opération sur Matlab
J'en suis bien content, mais j'aimerai bien comprendre ^^

La solution à une boucle est le genre de code que le compilateur optimise très bien : une boucle centrale minimalistes et un parcours séquentiel de tableaux.

La solution à deux boucles implique un calcul d'index à chaque étape de la boucle centrale. Cela revient au même qu'un parcours linéaire, mais je doute que le compilateur arrive à le repérer. Ca nous fait une boucle centrale moins minimaliste, et un parcours que le compilateur ne reconnait pas comme séquentiel.

Sur le fait que ça aille plus vite que Matlab, ce n'est pas étonnant: tu es sur le genre d'opérations minimales où les langages compilés et bas niveau gagnent toujours. Mais c'est un cas particulièrement favorable...

Pour les bibliothèques, Eigen est l'une des plus connues. Comme son nom l'indique, c'est très orienté algèbre linéaire. Si tu as pas mal d'opérations complexes sur les matrices, ça vaut la peine, c'est même indispensable si tu fais des choses un peu compliquées, avec des matrices très creuses, ou mal conditionnées (parce que les algorithmes deviennent vite délicats). Si tes calculs sont très simples (ou pas vraiment typiques de l'algèbre linéaire), c'est comme toujours un équilibre à trouver entre le temps passé à apprendre et gérer la bibliothèque et le gain qu'elle t'apporteras.

Francois

[JolyLoic]

Tu m’indiquerais pas le nom de cette bibliothèque à tout hasard

Oui, je t'en ai donné 2 dans mon premier message
Les deux ont une partie de leur doc orientée pour les utilisateurs de matlab qui souhaiteraient basculer vers eux...

[_zzyx_]

2-3 remarques au passage

Code :

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

1
2
3
 
#include <stdlib.h>
#include <time.h>

En C++ lorsqu'on utilise un header standard c on inclut cheader et non header.h (C'est une histoire de version à jours du header ou non)

Code :

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

1
2
3
 
#include <cstdlib>
#include <ctime>

Pour les nombres aléatoires, le rand() de base n'est pas conseillé, surtout si tu as besoin de grosses séries, la bonne nouvelle c'est que depuis cpp11 tu as std::random qui offre un vrai générateur de nombre aléatoire (http://www.cplusplus.com/reference/random/) et qu'il est inclus dans visual studio 2010.
Par exemple

Code :

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

1
2
3
4
 
std::mt19937_64 gen(seed) // definit un mesrenne twister avec seed 
std::normal_distribution<float> gaussian(0, (float)(sigma)) // définit une distribution aléatoire gaussienne centré sur zéro avec \sigma = sigma 
float number = gaussian(gen);  // Tire un nombre aléatoire avec la distrubtion /gaussian/ et le générateur /ge/

Pour le calcul parallèle, commence par un bête #pragma omp parallel for avant tes boucles for (celle qui ne modifient pas de variable externe à la boucle) c'est très simple et très efficace (il faut activer open mp, dans visual studio c'est une case à cocher, c'est une option avec GCC qui devient souvent une case à cocher si tu utlises cmake). Si tu veux faire des choses plus complexe ca devient vite le bordel et en général tu gagneras du temps à ne pas le faire.
Notes aussi, que lorsque c'est possible il vaut mieux diviser un lot de données en 10 fichiers traités chacun par le même programme qui tourne 10 fois en parallèle que par un seul un programme qui tourne sur 10 threads.

Sur de gros tableaux, je suis pas convaincu que std::vector soit adapté, car le fait que le tableau se redimensionne à la volée a un cout en terme de perf. par contre avec cpp11 tu as std::array ca te feras économiser un new et un delete[] par tableau c'est toujours ca comme source de problèmes en moins

[fcharton2]

Pour les nombres aléatoires, le rand() de base n'est pas conseillé, surtout si tu as besoin de grosses séries, la bonne nouvelle c'est que depuis cpp11 tu as std::random qui offre un vrai générateur de nombre aléatoire (http://www.cplusplus.com/reference/random/) et qu'il est inclus dans visual studio 2010.

En dehors de cas assez particuliers (simulation, cryptographie), et tant qu'on a besoin que quelques milliers de chiffres (voire quelques millions), rand() est généralement suffisant. Ici, le but est juste de remplir le tableau.

Sur de gros tableaux, je suis pas convaincu que std::vector soit adapté, car le fait que le tableau se redimensionne à la volée a un cout en terme de perf. par contre avec cpp11 tu as std::array ca te feras économiser un new et un delete[] par tableau c'est toujours ca comme source de problèmes en moins

Si ton tableau est statique, en ce sens que sa taille est fixée à l'initialisation, et que tu n'ajoutes ni ne supprimes d'éléments, il n'y aura aucun effet sur les performances. Dans ce cas, un vecteur est juste un "pointeur RAII". Le seul problème des vecteurs, c'est que, comme les new, ils demandent un bloc de mémoire contigüe, ce qui peut poser problème si le tableau est très gros.

Francois

[JolyLoic]

Sur de gros tableaux, je suis pas convaincu que std::vector soit adapté, car le fait que le tableau se redimensionne à la volée a un cout en terme de perf. par contre avec cpp11 tu as std::array ca te feras économiser un new et un delete[] par tableau c'est toujours ca comme source de problèmes en moins

La contrepartie est que std::array alloue sur la pile, qui est de taille bien plus limitée que ce qui est accessible par new. Donc pour des très gros tableaux, ça va vite faire sauter la pile.

[Bousk]

Sur de gros tableaux, je suis pas convaincu que std::vector soit adapté, car le fait que le tableau se redimensionne à la volée a un cout en terme de perf.

Pour les très gros tableaux on a appris il y a de nombreuses années déjà que la bonne pratique c'est reserve/push_back ou resize/[] et certainement pas de juste enchaîner les push_back qui entraînent la réallocation.

[_zzyx_]

La contrepartie est que std::array alloue sur la pile, qui est de taille bien plus limitée que ce qui est accessible par new. Donc pour des très gros tableaux, ça va vite faire sauter la pile.

J'étais convaincu que std::array était un tableau dynamique à taille fixe (et donc un std::vector allégé pour être aussi efficace qu'un tableau dynamique) merci pour l'info je me coucherais moins ignorant.

Pour les très gros tableaux on a appris il y a de nombreuses années déjà que la bonne pratique c'est reserve/push_back ou resize/[] et certainement pas de juste enchaîner les push_back qui entraînent la réallocation.

resize/[] je pratique, par contre reserve/push_back je connais pas (pourtant c'est pratique je retiens)

En dehors de cas assez particuliers (simulation, cryptographie), et tant qu'on a besoin que quelques milliers de chiffres (voire quelques millions), rand() est généralement suffisant. Ici, le but est juste de remplir le tableau.

OP parle justement de simulation, donc autant prendre les bonnes habitudes.
En bonus cpp11 offre par défaut un générateur de nombre aléatoire qui tiens la route et qui est facile à utiliser autant s'en servir dès le début plutôt que galérer avec rand() et ré-implémenter un mersenne twister à la main (ou tenter d'installer une lib dédiée)

[pingouin84k]

Je vous remercie tous de m'avoir répondu et pris le temps de m'expliquer toutes ces choses.