C/C++ d'optimiser les structures de données, tableau de tableaux ou matrices juste

Question

Travailler avec un programme qui utilise des matrices 4c4 un octet 16bytes:

unsigned char matrix[4][4]; 

et quelques 256 octets 16v16 une des matrices d'octets:

unsigned char bigMatrix[16][16]; 

Très souvent, en raison de la manipulation des données, je suis obligé de faire une boucle dans le programme en faisant des erreurs dans le cache.

Est-ce que la performance d'améliorer si j'utilise un tableau à la place, à savoir

unsigned char matrix[16]; 
unsigned char matrix[256]; 

et accéder aux éléments en utilisant des variables pour récupérer des éléments, à savoir

matrix[variableA*variableB + i]; 

où variableA * variableB + i besoins être recalculé chaque fois que je veux accéder à un élément. Je veux seulement l'optimisation de la vitesse et la mémoire ne pose aucun problème. Est-ce que cela aidera, comme donner un coup ou une perte de performance, ou est-ce que la différence est trop petite pour s'en soucier?

Answer 1

Cela ne fait aucune différence. Les données sont disposées exactement de la même manière dans les deux cas, et sont également accessibles de la même manière. Je serais surpris s'il ne produisait pas exactement le même assemblage, même. Cependant, avec une table de 256 octets, il est peu probable que vous obteniez des échecs de cache dans tous les cas. Le cache L1 de la CPU est généralement compris entre 32 et 128 Ko, donc je doute que vous obteniez de nombreux échecs de cache dans tous les cas.

Answer 2

Vous dites que variableA*variableB+i doit être recalculé chaque fois que vous accédez à un élément, cela se produit dans tous les cas, même lorsque vous utilisez des tableaux multidimensionnels. La seule différence est que dans les tableaux multidimensionnels, le compilateur émet ce code de sorte que vous ne le voyez pas et dans le tableau à une dimension, vous voyez le code dans votre source.

Answer 3

Le grand réseau linéaire peut être légèrement plus rapide si vous effectuez un accès séquentiel au réseau car vous enregistrez une opération de multiplication à chaque index. Si vous tournez en colonne, vous accédez séquentiellement; au moins en notation [row] [col], qui a été «standard» avec tous ceux à qui j'ai jamais parlé. Je doute que votre matrice de 256 éléments provoque des erreurs de mémoire cache sur le matériel moderne, mais je suis prêt à me tromper. Que vous dit Cachegrind?

Answer 4

Bien que le code compilé se comporte tout aussi rapidement, il y a un problème de conception: la réutilisation du code d'indexation pourrait être maximisée. À mon avis, la meilleure façon de le faire est de l'encapsuler dans un conteneur qui sait comment faire la boucle sur ses éléments de la manière la plus rapide. Ils ont un nom pour cela: un «itérateur interne», comme mentionné dans le modèle «Iterator» des modèles de conception du GoF.

Un bref exemple:

template< int N > 
struct CNxN { 
    typedef int t_row[N]; 
    typedef t_row t_matrix[N]; 
    t_matrix m_Contents; 

    template< typename Functor > 
    void each(Functor & f) { 
     for(int col = 0; col != N; ++col) 
      for(int row = 0; row != N; ++row) 
       f(m_Contents[row][col]); 
    } 
}; 

// client code 
CNxN<3> matrix = { { {1,1,1},{1,1,1},{1,1,1} } }; 

struct sum { 
     long result; 
     sum():result(0){} 
     void operator()(int i){ result +=i; } 
}; 
matrix.each(sum); 
assert(sum.result==0); 
assert(has_performed_in_the_fastest_possible_way);//;) 

Answer 5

jalf est le plus souvent droit. Le cache L1 est divisé en blocs, la taille des blocs dépend du processeur mais est de l'ordre de 32 octets. Donc, si vous parcourez la mémoire un octet à la fois, vous obtiendrez une cache manquante tous les 32 octets (ou quelle que soit la taille du bloc). Maintenant, la puce Intel est assez intelligente ici et peut détecter des lectures séquentielles et pré-extraire les données en réduisant l'impact d'un cache manqué.La matrice 4x4 est très susceptible de résider dans un seul bloc L1 (ou ligne de cache), donc l'accès par ligne ou par colonne fait peu de différence. Bien sûr, vous ne voulez pas diviser la matrice entre deux lignes de cache, donc la mémoire bien alignée est importante.

La matrice 16x16 ne rentrera cependant pas dans une ligne de cache. Donc, si vous ignorez les colonnes de traitement de tableau, vous obtiendrez beaucoup d'échec de cache. Le calcul de l'index, comme le dit jalf, fait peu de différence car le rapport entre CPU et mémoire est élevé (c'est-à-dire que vous pouvez faire beaucoup de travail CPU pour chaque cache manquant). Maintenant, si vous traitez principalement la matrice de manière orientée colonne, alors votre meilleure option est de transposer toutes vos matrices (échangez les rangées avec les colonnes), ainsi vos accès mémoire seront plus séquentiels et le nombre de cache manquera. sera réduit et le processeur sera en mesure de préfixer les données mieux. Ainsi, au lieu d'organiser la matrice comme ceci:

0 1 2 .... 15 
16 17 18 .... 31 
.... 
240 241 242 .... 255 

où le nombre est la mémoire décalée par rapport au début de la matrice, organiser ainsi:

0 16 32 ... 240 
1 17 33 ... 241 
... 
15 31 47 ... 255 

Answer 6

Quand j'étais à l'école, l'un des mon professeur CS a insisté sur le fait que si vous faites un tableau pour une dimension unique, ce sera plus rapide. Ce jour-là, je suis très ennuyé ...

Answer 7

Très souvent, en raison de la manipulation des données que je suis forcé à la colonne en boucle sage [...]

Vous ne pouvez pas avoir les deux façons: soit une boucle en ligne ou en colonne entraînera des échecs de cache si la matrice est suffisamment grande (voir Skizz' answer). Optimiser pour le type de bouclage qui est exécuté plus souvent.

Si la consommation de mémoire n'est pas un problème, vous pouvez également envisager d'enregistrer à la fois la matrice et sa transposition.