Optimisation des tableaux C ++ 2D

StackOverflow https://stackoverflow.com/questions/152745

Question

Il me faut un moyen de représenter un tableau 2D (une matrice dense) de doubles en C ++, avec un temps d’accès minimal absolu.

J'ai effectué des chronométrages sur diverses machines Linux / Unix et les versions gcc. Un vecteur de vecteurs STL, déclaré comme: 

vector<vector<double> > matrix(n,vector<double>(n));

et auquel il est accédé via matrix[i][j] est plus lent à accéder entre 5% et 100% qu'un tableau déclaré comme suit: 

double *matrix = new double[n*n];

accessible via une fonction d'indexation en ligne matrix[index(i,j)], où index(i,j) est évalué à i + n * j. Autres façons d’organiser un tableau 2D sans LIST - un tableau de n pointeurs au début de chaque ligne ou de définir l’ensemble de la pile comme une taille constante matrix[n][n] - s’exécute presque à la même vitesse que l’index méthode de la fonction.

Les versions récentes de GCC (> 4.0) semblent être capables de compiler le vecteur de vecteurs STL avec une efficacité presque identique à celle du code non-STL lorsque les optimisations sont activées, mais ceci est quelque peu automatique. dépendante.

J'aimerais utiliser STL si possible, mais je devrai choisir la solution la plus rapide. Quelqu'un at-il de l'expérience dans l'optimisation de la STL avec GCC?

Était-ce utile?

La solution

Si vous utilisez GCC, le compilateur peut analyser vos accès à la matrice et modifier l’ordre en mémoire dans certains cas. Le drapeau du compilateur magique est défini comme suit: 

-fipa-matrix-reorg
  

Effectuer un aplatissement de la matrice et   transposer. Essais d'aplatissement de la matrice   pour remplacer une matrice m-dimensionnelle par   sa matrice équivalente à n dimensions,   où n < m. Cela réduit le niveau de   indirection nécessaire pour accéder au   éléments de la matrice. La deuxième   l'optimisation est la transposition de la matrice   qui tente de changer l'ordre de   les dimensions de la matrice afin de   améliorer la localisation du cache. Tous les deux   les optimisations ont besoin de fwhole-programme   drapeau. La transposition est activée uniquement si   les informations de profilage sont disponibles.

Notez que cette option n'est pas activée par -O2 ou -O3. Vous devez le passer vous-même.

Autres conseils

Je pense que le plus rapide serait, pour une matrice, d'utiliser un tableau STD 1D et de remplacer l'opérateur () pour l'utiliser comme matrice 2D.

Cependant, la STL définit également un type spécifique pour les tableaux numériques non redimensionnables: valarray. Vous disposez également de diverses optimisations pour les opérations sur place.

valarray accepte comme argument un type numérique: 

valarray<double> a;

Ensuite, vous pouvez utiliser des tranches, des tableaux indirects, ... et bien sûr, vous pouvez hériter du valarray et définir votre propre opérateur () (int i, int j) pour les tableaux 2D ...

Très probablement, il s'agit d'un problème de localité de référence. vector utilise new pour allouer son tableau interne, ainsi chaque ligne sera au moins légèrement séparée en mémoire en raison de l'en-tête de chaque bloc; la mémoire est déjà fragmentée lorsque vous les allouez, la distance peut être longue. Différentes lignes du tableau risquent au moins de provoquer une erreur de ligne de cache et peuvent entraîner une erreur de page; si vous êtes vraiment malchanceux, deux lignes adjacentes pourraient se trouver sur des lignes de mémoire partageant un emplacement TLB et l'accès à l'une d'elles entraînerait l'expulsion de l'autre.

En revanche, vos autres solutions garantissent que toutes les données sont adjacentes. Cela pourrait améliorer vos performances si vous aligniez la structure de manière à ce qu'elle traverse autant de lignes de cache que possible.

<=> est conçu pour les tableaux redimensionnables . Si vous n'avez pas besoin de redimensionner les tableaux, utilisez un tableau C ++ standard. Les opérations STL peuvent généralement fonctionner sur des tableaux C ++.

Veillez à déplacer le tableau dans la bonne direction, c'est-à-dire (adresses mémoire consécutives) plutôt que vers le bas. Cela réduira les erreurs de cache.

Ma recommandation serait d'utiliser Boost.UBLAS, qui fournit des classes matricielles / vectorielles rapides.

Pour être juste, cela dépend des algorithmes que vous utilisez sur la matrice.

Le format double nom [n * m] est très rapide lorsque vous accédez à des données par lignes, car il n’ya pratiquement aucune surcharge, à part une multiplication et une addition, et parce que vos lignes sont des données condensées qui seront cohérentes dans le cache.

Si vos algorithmes accèdent aux données ordonnées par colonne, la cohérence du cache d’autres mises en page sera peut-être bien meilleure. Si votre algorithme accède aux données dans les quadrants de la matrice, même d'autres présentations pourraient être meilleures.

Essayez de faire des recherches sur le type d’utilisation et les algorithmes que vous utilisez. Cela est particulièrement important si la matrice est très volumineuse, car les erreurs de cache peuvent nuire beaucoup plus à vos performances que de nécessiter 1 ou 2 opérations mathématiques supplémentaires pour accéder à chaque adresse.

Vous pouvez tout aussi facilement créer des vecteurs < double > (n * m);

Blitz ++ est une autre bibliothèque connexe: http://www.oonumerics.org/blitz /docs/blitz.html

Blitz ++ est conçu pour optimiser la manipulation de tableaux.

Je l'ai fait il y a quelque temps pour les images brutes en déclarant mes propres classes de tableaux à 2 dimensions.

Dans un tableau 2D normal, vous accédez aux éléments tels que:

tableau [2] [3]. Maintenant, pour obtenir cet effet, vous auriez un tableau de classe avec une surcharge [] accesseur de tableau. Mais, cela retournerait essentiellement un autre tableau, donnant ainsi vous la deuxième dimension.

Le problème avec cette approche est qu’elle a une surcharge d’appel à fonction double.

Pour ce faire, j'ai utilisé la surcharge de style ().

So au lieu de array [2] [3], change je l'ai fait faire ce tableau de style (2,3).

Cette fonction () était très petite et je me suis assuré qu'elle était en ligne.

Voir ce lien pour le concept général de cela: http://www.learncpp.com/cpp-tutorial / 99-overloading-the-parenthesis-operator /

Vous pouvez modéliser le type si vous en avez besoin.
La différence que j'avais était que mon tableau était dynamique. J'ai eu un bloc de mémoire de caractère que je déclarerais. Et j'ai utilisé un cache de colonne, donc je savais où la rangée suivante commençait dans ma séquence d'octets. L'accès a été optimisé pour accéder aux valeurs voisines, car je l'utilisais pour le traitement d'images.

C’est difficile à expliquer sans code, mais le résultat était essentiellement aussi rapide que C et beaucoup plus facile à comprendre et à utiliser.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top