Bonjour à tous, petite réflexion face au calcul de matrice de grandes dimensions. Selon vous est-il préférable d'effectuer les additions via l'opérateur + qui va donc créé une nouvelle matrice puis ensuite la swaper via l'opérateur = dans la matrice qui contient le résultat. Ou alors il serait mieiux selon moi de créer une fonction qui prend en paramètre, la référence cette matrice devant contenit le résultat evitant ainsi l'etape de copie supplémentaire lors du =.

Le calcul se fait sur des matrices de dimensions 1000 environ 15000 fois d'où le nécessite de perf.

Merci

Hello, pour avoir travaillé souvent avec de grosses matrices, évite autant que possible des copies ! Tu risquerais en plus de swaper ou tout faire planter. Si tu nous donnes un code ou pseudo-code exemple, on pourra peut-être affiner ta demande.

A+

-
Edité par Nozio 25 août 2018 à 22:19:43

Sans le code que tu veux écrire, on ne peut pas trop répondre. En particulier, il n'est pas rare qu'on puisse avoir des optimisations comme du transfert de pointeurs à la place des copies.

Dans la vraie vie, on ne copie pas les matrices sur affectation depuis expression. Les Expression Template viennent à notre rescousse.

Sinon, pour minimiser il faut plein de surcharges pour intercepter lvalue + lvalue, rvalue + lvalue, lvalue + rvalue, etc -- j'ai un vieux post dans le coin. Mais au final, ce n'est pas le plus efficace.

//1er cas
void add(Matrix &a, Matrix &b, Matrix &res){

//faire addition de a+b dans res
} 

add(a,b,res);

//2eme cas

operator +(Matrix &b){
Matrix res;
//faire addition de a+b dans res
return res;
}

res=a+b;

-
Edité par Catztorien 26 août 2018 à 14:22:00

Salut,

Bien souvent, on va baser T operator + (T const & a, T const & b) sur T& operator += (T const & a)qui sera défini comme fonction membre de la classe, ce qui donnera souvent un code proche de

class T{
public:
    T& operator+=(T const &){
        //calcul nécessaire
    }
};
T operator + (T const & a, T const & b){
     T copy(a);
     return copy+=b;
}
int main(){
     T a;
     T b;
     a+=b; // a est modifié, car ses données membres subissent
           // l'addition de celles de b
     T c;
     T d;
     auto e = c+d // ni c ni d ne sont modifié, mais une
                  // copie est nécessaire pour obtenir e
}

On ne peut pas éviter la copie d'une donnée d'origine avec operator +, car on doit forcément travailler sur une donnée totalement indépendante des deux opérandes, alors que operator += peut travailler sur l'opérande de gauche, vu que l'assignation automatique cherche à assigner le résultat à celui-ci.

Si tu recherches une optimisation possible, ce n'est donc pas en évitant la copie que tu pourras l'obtenir, car c'est une étape indispensable de l'opération.

Par contre, la copie prendra forcément du temps, et ce sera surtout vrai si le type de donnée manipule en interne des ressources pour lesquelles l'allocation dynamique sera utilisée (par exemple, parce que le type de donnée utilise un std::vector pour "stocker" des informations).

Or, il est possible de limiter au maximum le nombre d'allocations dynamiques qui seront effectuées par std::vector lorsqu'on le remplira.  Par exemple, un code proche de

#include <iostream>
#include <vector>
int main()
{
	const size_t rows{100};  // le nombre de lignes
	const size_t cols{100};  // le nombre de colonnes
	std::vector<size_t> tab;
	auto capacity = tab.capacity();
	for(size_t i = 0; i < rows * cols; ++i){
		tab.push_back(i);
		if(tab.capacity() != capacity){
			std::cout<<"tab capacity changed to "<<tab.capacity()<< "for i ="<<i<<"\n";
			capacity = tab.capacity();
		}
	}
	return 0;
}

produira une sortie proche de

./a.out 
tab capacity changed to 1 for i = 0
tab capacity changed to 2 for i = 1
tab capacity changed to 4 for i = 2
tab capacity changed to 8 for i = 4
tab capacity changed to 16 for i = 8
tab capacity changed to 32 for i = 16
tab capacity changed to 64 for i = 32
tab capacity changed to 128 for i = 64
tab capacity changed to 256 for i = 128
tab capacity changed to 512 for i = 256
tab capacity changed to 1024 for i = 512
tab capacity changed to 2048 for i = 1024
tab capacity changed to 4096 for i = 2048
tab capacity changed to 8192 for i = 4096
tab capacity changed to 16384 for i = 8192

ce qui nous montre que la mécanique interne de std::vector implique qu'il y ait (dans selon l'exemple) 15 adaptations de la capacité de tab pour pouvoir ajouter les 10 000 (100 * 100) éléments.

Or, qui dit adaptations de la capacité, dit:

• allocation dynamique de la nouvelle capacité
• copie des données de "l'ancienne" capacité dans la "nouvelle"
• prise en compte du nouvel espace mémoire pour stocker les élément
• libération de la mémoire allouée à l'ancienne capacité

Et ce processus prend "énormément" de temps (du moins, à l'échelle du processeur)

Si l'on peut éviter que ce processus d'augmentation de la capacité du tableau ne se reproduise "trop souvent" (ou disons plutôt : plus souvent que nécessaire ) nous gagnerons forcément en performances.

Ce qui est chouette, c'est qu'il suffit d'une instruction de plus bien placée pour atteindre cet objectif.  Observe ce code:

#include <iostream>
#include <vector>
int main()
{
	const size_t rows{100};  // le nombre de lignes
	const size_t cols{100};  // le nombre de colonnes
	std::vector<size_t> tab;
	tab.reserve(rows * cols);
	auto capacity = tab.capacity();
	for(size_t i = 0; i < rows * cols; ++i){
		tab.push_back(i);
		if(tab.capacity() != capacity){
			std::cout<<"tab capacity changed to "<<tab.capacity()<< "for i = "<<i<<"\n";
			capacity = tab.capacity();
		}
	}
	std::cout<<"final capacity :"<<tab.capacity()<<" for "<< tab.size()<<" elements \n";
	return 0;
}

Dans lequel je me suis contenté de rajouter la ligne tab.reserve(row* cols); (et un affichage de la capacité finale), mais qui produit une sortie proche de

 ./a.out 
final capacity :10000 for 10000 elements 

et qui nous indique qu'il n'y a pas eu d'adaptation de la capacité de notre tableau  dans la boucle.

Pour le reste, la priorité si tu cherches les optimisations possible est -- comme l'on dit les autres -- toujours de chercher l'endroit qui sera le "plus intéressant" à optimiser:

il ne sert à rien de "tordre" ton code pour gagner même 100 cycles d'horloge dans une instruction qui ne sera effectuée qu'une ou deux fois.  Par contre, il est peut-être intéressant de tordre ton code pour gagner 1 cycle d'horloge dans une instruction qui sera effectuée 150 000 fois

De plus, de nombreux "sucres syntaxiques" n'ont en réalité pas la moitié du pouvoir qu'on leur prête généralement...  La clé pour obtenir les "meilleures performances" (une fois que l'on a clairement déterminé quelle instruction nous permettra d'en gagner le plus) est toujours la même:

1- améliorer l'algorithme : si tu peux -- d'une manière ou d'une autre -- éviter d'avoir à traiter la moitié des données, tu gagneras sans doute la moitié des cycles d'horloges lors du traitement (moins le temps nécessaire à l'exécution des tests qui te permettront d'éviter la moitié des données)

2- améliorer les structures : Il n'y a pas de miracle.  On peut avoir de très grosses quantité de mémoire OU de la mémoire très rapide.  Mais on ne peut pas avoir de très grosses quantités de mémoire très rapide.

C'est pourquoi tous les processeurs récents proposent ce que l'on appelle de la "mémoire cache" (de différents niveaux) : ce sont de petites quantités de mémoire extrêmement rapide.

Lorsque le processeur a besoin d'une donnée, il va commencer par regarder s'il la trouve dans sa mémoire cache.  Si elle n'y est pas, il va "charger" dans son cache la donnée recherchée et "autant de données que possibles" qui se trouvent "à coté" de la donnée recherchée, dans l'espoir que les données dont il aura besoin "après" s'y trouve également.

C'est un processus qui prend -- forcément -- du temps, mais, comme la mémoire cache est beaucoup plus rapide que la RAM, plus il pourra accéder à une donnée qui aura été chargée "en même temps qu'une autre" dans le cache, plus il "rentabilisera" le temps qu'il lui aura fallu pour remplir le cache.

Evidemment, si la "donnée suivante" à laquelle il devra accéder ne se trouve pas dans le cache, il aura "perdu son pari" car il aura "perdu du temps pour rien"; et nous aurons alors un "cache miss" : le processeur devra... perdre du temps à charger "une autre série" de données en cache.

L'idéal est donc de créer et / ou choisir ses structures de telle manière à ce que les données soient "le plus contiguës possible" en mémoire, et de préférer la notion de tableau quand c'est possible aux notions de pile, de file, de liste ou d'arbres binaires.

Mais cela signifie aussi de faire en sorte d'éviter (autant que possible) d'avoir "trop d'espaces de remplissage" destinés à l'alignement des données dans nos structures personnelles

3 - Eviter les copies à chaque fois que possible:

On le sait, la copie d'une donnée est un processus qui prend du temps.  Si on peut éviter la copie, on économise forcément le temps nécessaire à ce processus.

Si -- en plus -- on peut éviter la copie dans un processus qui se répète très souvent, cela nous permettra de gagner énormément de temps.

Pour notre malheur, il y a des situations dans lesquelles il nous est littéralement impossible d'éviter la copie (l'opérateur + en est un parfait exemple).

4- Et si tout cela ne produit pas encore les gains de performances souhaités, reprendre en (1)

@Koala01 tu présupposes des vecteurs sur lesquels on peut agir de diverses façons, ici, l'OP est sur de l'optim de calculs matriciels exprimés de façon mathématique (et pas à coup d'appels à des fonctions BLAS)

Tu as présenté l'écriture typique en effet. Si on a des objets dont le poids est réparti en deux parties, pour optimiser à fond, il faut 4 surcharges de l'opérateur +, autant du -, pour les autres, j'ai la flemme de compter. C'est mon expérience retracée ici: https://openclassrooms.com/forum/sujet/declaration-canonique-d-un-operateur-binaire?page=2#message-89276639 (suivre le lien pour le code). Je me souviens en avoir parlé ailleurs.

Mais cela reste très insuffisant. D'où les expressions templates mises en avant il y a plus de 20 ans avec la bibliothèque de calcul matriciel en C++: Blitz++. Depuis, plein d'autres libs. Eigen et Blaze semblent être les plus pertinentes en utilisation professionnelle aujourd'hui. C'est du FOSS, elles passent par des Expressions Templates pour traduire des expressions mathématiques de calculs vectoriel/matriciel de la façon la plus efficace possible en éliminant toute allocation qui peut l'être, voire qui vont même jusqu'à trouver la fonction BLAS dispo sur le système qui sera la plus efficace pour réaliser un calcul pouvant impliquer 3 opérandes à la fois. Quand l'implémentation de la fonction BLAS provient de la bibliothèque Intel MKL, sur les cibles Intel, on aura les meilleures performances possibles, tout en gardant un niveau d'expressivité "humain" -- plus exactement, avec un formalisme le plus proche possible du formalisme mathématique.

Et puis, sur l'optimisation, il ne faut jamais oublier la première règle "Premature optimization is the root of evil". Entre un programme optimisé qui ne marche pas et un programme non optimisé qui marche, je choisis toujours celui qui marche...

Le programme fonctionne deja, je cherche juste a l'optimiserpour avoir des maillages avec plus de 1000 noeuds pour mon solveur FEM sans attendre 30min.

Je vais regarder vos propositions, merci a tous des precisions!

Facile alors, s'il s'agit d'un vrai développement : ne pas réinventer la roue, et utiliser les solutions disponibles qui ont déjà été développées par d'autres. J'en ai déjà cité 2.

Ne pas réinventer la roue permet de gagner un temps considérable (ce qui en soit est déjà une optimisation). D'autre part les "grandes bibliothèques" sont souvent très mature (très peu de bug y traînent) et réalisées/maintenues par des pointures. Cela apporte plusieurs avantages immédiats, le premier est de ne pas avoir à se retaper tout depuis le début, ce qui économise un temps de développement considérable, le second, c'est la fiabilité, ces bibliothèques sont généralement très bien testées, ce qui diminue d'autant le temps que tu devras consacrer à tes tests et si par malheur il y traîne un bug, celui-ci sera très vite découvert par la communauté des utilisateurs, et très vite corrigé, souvent avant que tu le découvres par toi même. Tu as très souvent une interface très stable dans le temps avec un très bon support de la compatibilité ascendante ce qui te garantit que tu ne seras pas obligé de tout refaire pour upgrader en version de la bibliothèque. Enfin elles ont pas mal de bouteille, les gars ont ont largement eu le temps de les optimiser dans tous les sens, donc tu auras du mal à faire mieux sur ce chapitre...

Je n'en doute pas mais je serais tres curieux de m'y essayer un peu pour le sport et decouvrir les principes derriere ces biblio. Les expression template semblent repondre exactement a mon probleme dans les articles associes que j'ai trouve.

Merci a tous !