C / C++ performance des tableaux statiques vs tableaux dynamiques
quand la performance est essentielle à une application, devrait-on considérer s'il faut déclarer un tableau sur la pile vs le tas? Permettez-moi de décrire pourquoi cette question est venue à l'esprit.
puisque les tableaux en c/" class="blnk">C / C++ ne sont pas des objets et se décomposent en pointeurs, le compilateur utilise l'index fourni pour effectuer l'arithmétique des pointeurs pour accéder aux éléments. Je crois comprendre que cette procédure diffère d'un tableau statiquement déclaré à un tableau dynamiquement déclaré Lorsque va au-delà de la première dimension.
Si je devais déclarer un tableau sur la pile comme suit:
int array[2][3] = { 0, 1, 2, 3, 4, 5 }
//In memory { row1 } { row2 }
Ce tableau serait stocké dans Ligne Principale formater en mémoire puisqu'il est stocké dans un bloc contigu de mémoire. Cela signifie que lorsque j'essaie d'accéder à un élément du tableau, le compilateur doit effectuer une addition et une multiplication afin de déterminer l'emplacement correct.
Donc, si je devais faire ce qui suit
int x = array[1][2]; // x = 5
le compilateur aurait ensuite utiliser cette formule:
I = index des lignes j = index des colonnes n = Taille d'une seule ligne (ici n = 2)
array = pointeur vers le premier élément
*(array + (i*n) + j)
*(array + (1*2) + 2)
cela signifie que si je devais boucler ce tableau pour accéder à chacun de ses éléments, une étape de multiplication supplémentaire est effectuée pour chaque accès par index.
Maintenant, dans un tableau déclaré sur le tas, le paradigme est différent et nécessite plusieurs étapes de la solution. Note: j'ai pu utilisez également le nouvel opérateur C++ ici, mais je crois qu'il n'y a pas de différence dans la façon dont les données sont représentées.
int ** array;
int rowSize = 2;
// Create a 2 by 3 2d array on the heap
array = malloc(2 * sizeof(int*));
for (int i = 0; i < 2; i++) {
array[i] = malloc(3 * sizeof(int));
}
// Populating the array
int number = 0;
for (int i = 0; i < 2; i++) {
for (int j = 0l j < 3; j++) {
array[i][j] = number++;
}
}
Depuis le tableau est maintenant dynamique, sa représentation est un tableau unidimensionnel de dimensions des tableaux. Je vais essayer de faire un dessin ascii...
int * int int int
int ** array-> [0] 0 1 2
[1] 3 4 5
Cela impliquerait que la multiplication est plus impliqué droit? Si je devais faire ce qui suit
int x = array[1][1];
ceci effectuerait alors l'arithmétique indirecte/pointeur sur le tableau [1] pour accédez à un pointeur sur la deuxième rangée et exécutez-le à nouveau pour accéder au deuxième élément. Ai-je raison en disant cela?
Maintenant que le contexte est, de retour à la question. Si j'écris du code pour une application qui exige des performances nettes, comme un jeu qui a environ 0,016 secondes pour rendre un cadre, devrais-je réfléchir à deux fois à l'utilisation d'un tableau sur la pile vs le tas? Maintenant je réalise qu'il y a un coût unique pour utiliser malloc ou le nouvel opérateur, mais à un certain point (tout comme L'analyse de Big O) lorsque l'ensemble de données devient grand, serait-il préférable d'itérer à travers un tableau dynamique pour éviter l'indexation de la rangée principale?
5 réponses
Ces "plaine" C (pas C++).
D'abord, clarifions un peu la terminologie
"static" est un mot-clé en C qui va changer radicalement la façon dont votre variable est attribuée / consultée si elle est appliquée sur les variables déclarées dans les fonctions.
Il y a 3 endroits (sujet C) lorsqu'une variable (y compris les tableaux) peut s'asseoir:
- Stack: ce sont des variables locales de fonction sans
static. - section des données: de l'espace est alloué pour ceux-ci lorsque le programme commence. Ce sont des variables globales (que ce soit
staticou pas, il y a le mot se rapporte à la visibilité), et de toute fonction de variables locales déclaréesstatic. - tas: mémoire allouée dynamiquement (
malloc()&free()) visé par un pointeur. Vous accédez à ces données uniquement par des pointeurs.
voyons maintenant comment les matrices unidimensionnelles sont accéder
si vous accédez à un tableau avec un index constant (peut être #defined, mais pas const dans la plaine, C), cet indice peut être calculé par le compilateur. Si vous avez un vrai tableau dans le section des données, il sera accessible sans indirection. Si vous avez un pointeur ( tas) ou un tableau sur l' Stack, une action indirecte est toujours nécessaire. Si les tableaux dans le section des données avec ce type d'accès peut être un très peu plus vite. Mais ce n'est pas une chose très utile qui pourrait changer le monde.
si vous accédez à un tableau avec une variable index, il se décompose essentiellement en pointeur puisque l'index peut changer (par exemple incrément dans une boucle pour). Le code généré sera probablement très similaire ou même identique pour tous les types ici.
Apporter plus de dimensions
si vous déclarez un tableau bidimensionnel ou plus, et y accédez partiellement ou totalement par des constantes, un compilateur intelligent peut très bien optimiser ces constantes comme ci-dessus.
si vous accédez par des indices, notez que la mémoire est linéaire. Si les dimensions ultérieures d'un tableau true ne sont pas un multiple de 2, le compilateur devra générer des multiplications. Par exemple, dans le tableau int arr[4][12]; la deuxième dimension est 12. Si vous avez maintenant accès arr[i][j] où i et j sont des variables d'index, la mémoire linéaire doit être indexée comme 12 * i + j. Si le compilateur doit générer du code pour multiplier avec une constante ici. La complexité dépend de la distance entre la constante et une puissance de 2. Ici, le code résultant ressemblera probablement un peu à calculer (i<<3) + (i<<2) + j pour accéder à l'élément dans le tableau.
si vous construisez le "tableau" bidimensionnel à partir de pointeurs, la taille des dimensions n'a pas d'importance puisqu'il y a des pointeurs de référence dans votre structure. Ici, si vous pouvez écrire arr[i][j], cela implique que vous l'avez déclaré comme exemple int* arr[4] et malloc() ed quatre morceaux de mémoire de 12 ints chacune. Notez que vos quatre pointeurs (que le compilateur peut maintenant utiliser comme base) consomment aussi de la mémoire qui n'a pas été prise si c'était un tableau true. Notez aussi que le code généré contiendra ici une double expression indirecte: D'abord le code charge un pointeur de iarr, puis il chargera un int à partir de ce pointeur par j.
si les longueurs sont "loin" des puissances de 2 (si complexe les codes" multiplier avec constante " devraient être générés pour accéder aux éléments), puis l'utilisation de pointeurs peut générer des codes d'accès plus rapides.
James Kanze mentionné dans sa réponse, dans certaines circonstances le compilateur peut être en mesure d'optimiser l'accès pour de vrais tableaux multidimensionnels. Ce type d'optimisation est impossible pour les tableaux composés à partir de pointeurs car le "tableau" n'est pas en fait un morceau linéaire de mémoire que le cas.
Localité
si vous développez pour les architectures de bureau / mobiles habituelles (processeurs Intel / ARM 32 / 64 bits), la localisation est également importante. C'est probablement ce qui se trouve dans la cache. Si vos variables sont déjà dans le cache pour une raison quelconque, ils seront accessibles plus rapidement.
Dans la durée de la localité Stack est toujours le gagnant, depuis le Stack c'est souvent utilisé, il est très probable pour toujours assis dans le cache. Si petit les tableaux sont meilleures.
utiliser de vrais tableaux multidimensionnels au lieu d'en composer un à partir de pointeurs peut aussi aider sur ce terrain puisqu'un tableau vrai est toujours un morceau linéaire de mémoire, donc il pourrait avoir besoin de moins de blocs de cache pour charger. Une composition de pointeur dispersé (c'est-à-dire si l'on utilise séparément malloc() ed chunks) au contraire pourrait nécessiter plus de blocs de cache, et pourrait augmenter les conflits de lignes de cache en fonction de la façon dont les morceaux se retrouvaient physiquement sur le tas.
la façon habituelle d'implémenter un tableau 2 dimensions en C++
serait l'envelopper dans une classe, à l'aide de std::vector<int>, et
avoir des accesseurs de classe qui calculent l'index. Cependant:
toutes les questions concernant l'optimisation ne peuvent être répondues que par de mesure, et même alors, ils ne sont valables que pour le compilateur vous utilisez, sur la machine sur laquelle vous faites les mesures.
Si vous écrivez:
int array[2][3] = { ... };
et puis quelque chose comme:
for ( int i = 0; i != 2; ++ i ) {
for ( int j = 0; j != 3; ++ j ) {
// do something with array[i][j]...
}
}
il est difficile d'imaginer un compilateur qui ne génère pas réellement quelque chose le long des lignes de:
for ( int* p = array, p != array + whatever; ++ p ) {
// do something with *p
}
c'est l'une des optimisations les plus fondamentales autour, et a été pour les moins de 30 ans.
si vous attribuez dynamiquement comme vous le proposez, le compilateur être en mesure d'appliquer cette optimisation. Et même pour un seul accès: la matrice a une localisation plus pauvre, et nécessite plus de mémoire accès, risque de sois moins performante.
si vous êtes en C++, vous écririez normalement un Matrix classe,
en utilisant std::vector<int> pour la mémoire, et le calcul de la
index explicitement utilisant la multiplication. (La localité améliorée
il en résultera probablement une meilleure performance, malgré
multiplication.) Cela pourrait rendre plus difficile pour l'
compilateur pour faire l'optimisation ci-dessus, mais si cela s'avère
être un problème, vous pouvez toujours fournir des itérateurs pour
la manipulation de ce un cas particulier. Vous plus d'
code lisible et plus souple (par exemple les dimensions n'ont pas
être constant), à peu ou pas de perte de performance.
en ce qui concerne le choix qui offre une meilleure performance, alors la réponse dépendra largement de vos circonstances spécifiques. La seule façon de savoir si une solution est meilleure ou s'ils sont à peu près équivalent est de mesurer les performances de votre application.
ce qui pourrait être un facteur sont: combien de fois vous le faites, la taille réelle des tableaux/données, Combien de mémoire votre système a, et comment bien votre système gère la mémoire.
Si vous avez le luxe de pouvoir choisissez entre les deux options, il faut dire que les tailles sont déjà cloués. Ensuite, vous n'avez pas besoin du schéma d'allocation multiple que vous avez illustré. Vous pouvez effectuer une seule allocation dynamique de votre tableau 2D. In C:
int (*array)[COLUMNS];
array = malloc(ROWS * sizeof(*array));
EN C++:
std::vector<std::array<int, COLUMNS>> array(ROWS);
tant Que COLUMNS est cloué vers le bas, vous pouvez effectuer une allocation unique pour obtenir votre tableau 2D. Si aucun n'est trouvé, alors vous n'avez pas vraiment le choix de l'utilisation d'un tableau statique de toute façon.
il y a souvent un compromis entre la consommation de mémoire et la vitesse. Empiriquement, j'ai vu que la création de tableau sur la pile est plus rapide que l'allocation sur tas. Lorsque la taille du tableau augmente, cela devient plus apparent.
Vous pouvez toujours diminuer la consommation de mémoire. Par exemple, vous pouvez utiliser short ou char à la place de int etc.
comme la taille du tableau augmente, surtout avec l'utilisation de realloc, il pourrait y avoir beaucoup plus de remplacement de page (Haut et bas) pour maintenir l'emplacement contigu des articles.
vous devriez également considérer qu'il y a une limite inférieure pour la taille des choses que vous pouvez stocker dans la pile, car cette limite est plus élevée, mais comme je l'ai dit avec le coût de la performance.
L'allocation de mémoire de traçage offre un accès plus rapide aux données que le tas. Le CPU serait à la recherche de l'adresse dans le cache si il ne l'a pas, si il ne trouve pas l'adresse dans le cache alors il faudrait chercher dans la mémoire principale. La tige est un endroit préféré après le cache.