C/C++ de la performance des tableaux statiques vs tableaux dynamiques

Quand la performance est essentielle pour une application, devrait-on songer à la déclaration d'un tableau sur la pile et le tas? Permettez-moi de décrire pourquoi cette question est venue à l'esprit.

Comme les tableaux en C/C++ ne sont pas des objets et de la décadence de pointeurs, le compilateur utilise l'index fourni pour effectuer l'arithmétique des pointeurs pour accéder aux éléments. Ma compréhension est que cette procédure diffère d'une manière statique déclaré tableau dynamiquement un tableau déclaré lors de la 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 devraient être stockées dans Ligne principale format en mémoire, car il est stocké dans un bloc contigu de mémoire. Cela signifie que lorsque je tente d'accéder à un élément dans le tableau, le compilateur doit effectuer certaines d'addition et de 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 où:

i = index de ligne j = colonne d'indice 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 faire une boucle sur ce tableau à l'accès de chacun de ses éléments, une autre étape de multiplication 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 également utiliser le C++ opérateur de nouveau 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 dessiner un ascii image...

              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];

Ce serait alors d'effectuer indirection/l'arithmétique des pointeurs sur tableau[1] pour accéder à un pointeur vers la deuxième ligne, puis effectuer une nouvelle fois pour accéder au deuxième élément. Ai-je raison en disant cela?

Maintenant que le contexte est, de retour à la question. Si je suis à l'écriture de code pour une application qui nécessite croustillant de la performance, comme un jeu qui a autour de 0,016 secondes pour effectuer le rendu d'une image, dois-je réfléchir à deux fois au sujet de l'utilisation d'un tableau sur la pile et le tas? Maintenant je me rends compte il y a un coût pour l'utilisation de malloc ou le nouvel opérateur, mais à un certain point (tout comme Big O analyse) lorsque l'ensemble de données devient importante, serait-on mieux une itération à travers un tableau dynamique pour éviter les lignes principales de l'indexation?

Vous pouvez utiliser l'allocation de mémoire pour la 2D pour la comparaison
Quoi que vous fassiez, vous êtes encore en train de faire ligne principale (plutôt que la colonne principale). Essayez de la mesure.
Pile vs tas est une question dont la répartition est et quand vous savez comment il est grand, n'est pas une question de mise en page des données. Comme Grijesh Chauhan déjà dit, vous pouvez utiliser la même mise en page multi-dimensionnelle tableau statique sur le tas, vous n'avez pas obtenu sucre syntaxique pour elle. Vous pouvez également avoir un tableau statique de pointeurs de tableaux (et parfois on a de sens, bien que le fait de trop tableaux seront souvent allouée dynamiquement).
Si vous êtes juste de parcourir le tableau, un standard de l'optimisation de la technique dite de la "réduction de la résistance" permet aux multiplications à être convertis à des additions. Depuis plus de 40 ans. Bien que la multiplication est de moins en moins une préoccupation majeure de ces jours; les défauts de cache sont bien pire.
Une autre question intéressante serait de la performance d'un tableau statique mis en œuvre sur la pile par rapport à un tableau statique mis en œuvre dans une section de données.

OriginalL'auteur Paul Renton | 2013-07-21