1D ou 2D array, quoi de plus rapide?

J’ai besoin de représenter un champ 2D (axes x, y) et je suis confronté à un problème: Dois-je utiliser un tableau 1D ou un tableau 2D?

Je peux imaginer que le recalcul des indices pour les tableaux 1D (y + x * n) pourrait être plus lent que l’utilisation d’un tableau 2D (x, y) mais je pourrais imaginer que 1D pourrait être en cache CPU.

J’ai fait des recherches sur Google, mais je n’ai trouvé que des pages concernant les tableaux statiques (et indiquant que 1D et 2D sont fondamentalement les mêmes). Mais mes tableaux doivent être dynamics.

Donc quoi

  1. plus rapide,
  2. plus petit (RAM)

tableaux dynamics 1D ou tableaux 2D dynamics?

Merci 🙂

tl; dr: Vous devriez probablement utiliser une approche unidimensionnelle.

Remarque: On ne peut pas entrer dans les détails des performances lors de la comparaison de modèles de stockage dynamics 1d ou dynamics 2d sans remplissage de livres, car les performances du code dépendent d’un très grand nombre de parameters. Profil si possible.

1. Qu’est-ce qui est plus rapide?

Pour les masortingces denses, l’approche 1D est susceptible d’être plus rapide car elle offre une meilleure localisation de la mémoire et une réduction des frais d’allocation et de désallocation.

2. Qu’est-ce qui est plus petit?

Dynamic-1D consum moins de mémoire que l’approche 2D. Ce dernier nécessite également plus d’allocations.

Remarques

J’ai présenté une réponse assez longue avec plusieurs raisons, mais je veux d’abord faire quelques remarques sur vos hypothèses.

Je peux imaginer que le recalcul des indices pour les tableaux 1D (y + x * n) pourrait être plus lent que l’utilisation d’un tableau 2D (x, y)

Comparons ces deux fonctions:

 int get_2d (int **p, int r, int c) { return p[r][c]; } int get_1d (int *p, int r, int c) { return p[c + C*r]; } 

L’assembly (non intégré) généré par Visual Studio 2015 RC pour ces fonctions (avec les optimisations activées) est:

 ?get_1d@@YAHPAHII@Z PROC push ebp mov ebp, esp mov eax, DWORD PTR _c$[ebp] lea eax, DWORD PTR [eax+edx*4] mov eax, DWORD PTR [ecx+eax*4] pop ebp ret 0 ?get_2d@@YAHPAPAHII@Z PROC push ebp mov ebp, esp mov ecx, DWORD PTR [ecx+edx*4] mov eax, DWORD PTR _c$[ebp] mov eax, DWORD PTR [ecx+eax*4] pop ebp ret 0 

La différence est mov (2d) vs lea (1d). Le premier a une latence de 3 cycles et un débit maximum de 2 par cycle tandis que le second a une latence de 2 cycles et un débit maximum de 3 par cycle. (Selon les tableaux d’instructions – Agner Fog Comme les différences sont mineures, je pense qu’il ne devrait pas y avoir de grande différence de performance liée au recalcul des index. Je pense qu’il est très peu probable que cette différence soit le goulot d’étranglement de tout programme.

Cela nous amène au point suivant (et plus intéressant):

… mais je pourrais imaginer que 1D pourrait être en cache CPU …

Vrai, mais 2d pourrait aussi être dans le cache du CPU. Voir Les inconvénients: Emplacement de la mémoire pour une explication de pourquoi 1d est encore meilleur.

La réponse longue, ou pourquoi le stockage dynamic de données à 2 dimensions (pointeur à pointeur ou vecteur de vecteur) est “mauvais” pour les masortingces simples / petites.

Remarque: Il s’agit de tableaux dynamics / schémas d’allocation [malloc / new / vector etc.]. Un tableau 2d statique est un bloc de mémoire contigu et donc non sujet aux inconvénients que je vais présenter ici.

Le problème

Pour pouvoir comprendre pourquoi un tableau dynamic de tableaux dynamics ou un vecteur de vecteurs n’est probablement pas le modèle de stockage de données de votre choix, vous devez comprendre la disposition de la mémoire de ces structures.

Exemple de cas utilisant le pointeur sur la syntaxe du pointeur

 int main (void) { // allocate memory for 4x4 integers; quick & dirty int ** p = new int*[4]; for (size_t i=0; i<4; ++i) p[i] = new int[4]; // do some stuff here, using p[x][y] // deallocate memory for (size_t i=0; i<4; ++i) delete[] p[i]; delete[] p; } 

Les inconvénients

Localité de mémoire

Pour cette «masortingce», vous atsortingbuez un bloc de quatre pointeurs et quatre blocs de quatre nombres entiers. Toutes les allocations ne sont pas liées et peuvent donc entraîner une position de mémoire arbitraire.

L'image suivante vous donnera une idée de l'apparence de la mémoire.

Pour le vrai cas 2d :

  • Le carré violet est la position mémoire occupée par p lui-même.
  • Les carrés verts assemblent la région mémoire p points (4 x int* ).
  • Les 4 régions de 4 carrés bleus contigus sont celles désignées par chaque int* de la région verte

Pour le 2d mappé sur 1d cas :

  • Le carré vert est le seul pointeur requirejs int *
  • Les carrés bleus forment la région mémoire pour tous les éléments de la masortingce (16 x int ).

Real 2d vs mappage 2d mappé en mémoire

Cela signifie que (lorsque vous utilisez la mise en page de gauche) vous observerez probablement des performances moins bonnes que pour un modèle de stockage contigu (comme indiqué à droite), en raison de la mise en cache par exemple.

Disons qu'une ligne de cache est "la quantité de données transférées dans le cache immédiatement" et imaginons un programme accédant à la masortingce entière un élément après l'autre.

Si vous avez une masortingce de valeurs 32 bits de 4 fois 4 correctement alignée, un processeur avec une ligne de cache de 64 octets (valeur typique) est capable de "copier" les données (4 * 4 * 4 = 64 octets). Si vous commencez à traiter et que les données ne se trouvent pas déjà dans le cache, vous serez confronté à un échec du cache et les données seront extraites de la mémoire principale. Cette charge peut récupérer l'intégralité de la masortingce en une fois, car elle s'intègre dans une ligne de cache, si et seulement si elle est stockée de manière contiguë (et correctement alignée). Il n'y aura probablement plus de raté lors du traitement de ces données.

Dans le cas d'un système dynamic «réel à deux dimensions» avec des emplacements non liés de chaque ligne / colonne, le processeur doit charger chaque emplacement de mémoire séparément. Bien que seuls 64 octets soient requirejs, le chargement de 4 lignes de cache pour 4 positions de mémoire non liées pourrait, dans le pire des cas, transférer 256 octets et gaspiller 75% de bande passante de débit. Si vous traitez les données en utilisant le schéma 2d, vous devrez à nouveau (si ce n'est déjà fait en cache) faire face à une absence de cache sur le premier élément. Mais maintenant, seule la première ligne / colonne sera dans le cache après le premier chargement de la mémoire principale car toutes les autres lignes sont situées ailleurs dans la mémoire et non adjacentes au premier. Dès que vous atteignez une nouvelle ligne / colonne, il y aura à nouveau un cache manquant et le prochain chargement de la mémoire principale sera effectué.

En bref: Le modèle 2d a plus de chance de manquer le cache avec le schéma 1d offrant un meilleur potentiel de performance en raison de la localisation des données.

Affectation fréquente / Affectation

  • Autant N + 1 (4 + 1 = 5) allocations (en utilisant new, malloc, allocator :: allocate ou autre) sont nécessaires pour créer la masortingce NxM (4 × 4) souhaitée.
  • Le même nombre d'opérations de désallocation appropriées doit également être appliqué.

Par conséquent, il est plus coûteux de créer / copier de telles masortingces contrairement à un schéma d'allocation unique.

Cela devient encore pire avec un nombre croissant de lignes.

Frais généraux de consommation de mémoire

Je vais atsortingbuer une taille de 32 bits pour int et 32 ​​bits pour les pointeurs. (Remarque: dépendance du système.)

Rappelons-nous: nous voulons stocker une masortingce 4 × 4 int qui signifie 64 octets.

Pour une masortingce NxM, stockée avec le schéma de pointeur à pointeur présenté, nous consommons

  • N*M*sizeof(int) [les données bleues réelles] +
  • N*sizeof(int*) [les pointeurs verts] +
  • sizeof(int**) [la variable viol p] octets.

Cela fait 4*4*4 + 4*4 + 4 = 84 octets dans le cas du présent exemple et cela devient encore pire avec std::vector> . Il faudra N * M * sizeof(int) + N * sizeof(vector) + sizeof(vector>) octets, soit 4*4*4 + 4*16 + 16 = 144 octets au total, 64 octets pour 4 x 4 int.

En outre, en fonction de l'allocateur utilisé, chaque allocation peut avoir 16 octets supplémentaires de mémoire supplémentaire. (Quelques "Infobytes" qui stockent le nombre d'octets alloués dans le but d'une désallocation correcte.)

Cela signifie que le pire des cas est:

N*(16+M*sizeof(int)) + 16+N*sizeof(int*) + sizeof(int**)
= 4*(16+4*4) + 16+4*4 + 4 = 164 bytes ! _Overhead: 156%_

La part du surcoût diminuera à mesure que la taille de la masortingce augmentera mais sera toujours présente.

Risque de fuite de mémoire

Le groupe d'allocations nécessite une gestion des exceptions appropriée afin d'éviter les memory leaks si l'une des allocations échoue! Vous devrez suivre les blocs de mémoire alloués et vous ne devez pas les oublier lors de la désallocation de la mémoire.

Si de new exécutions de mémoire et la ligne suivante ne peuvent pas être allouées (particulièrement lorsque la masortingce est très volumineuse), un nouveau std::bad_alloc est lancé.

Exemple:

Dans l'exemple nouveau / delete mentionné ci-dessus, nous aurons plus de code si nous voulons éviter les fuites en cas d'exceptions bad_alloc .

  // allocate memory for 4x4 integers; quick & dirty size_t const N = 4; // we don't need try for this allocation // if it fails there is no leak int ** p = new int*[N]; size_t allocs(0U); try { // try block doing further allocations for (size_t i=0; i 

Résumé

Il existe des cas où les configurations de mémoire "2D réel" sont adaptées (par exemple, si le nombre de colonnes par ligne n'est pas constant) mais dans les cas de stockage de données 2D les plus simples et simples, elles compliquent la complexité de votre code et réduisent les performances. et l'efficacité de la mémoire de votre programme.

Alternative

Vous devez utiliser un bloc de mémoire contigu et mapper vos lignes sur ce bloc.

Le "moyen C ++" de le faire est probablement d'écrire une classe qui gère votre mémoire tout en considérant des choses importantes comme

  • Quelle est la règle des trois?
  • Qu'entend-on par acquisition de ressources, l'initialisation (RAII)?
  • Concept C ++: Container (sur cppreference.com)

Exemple

Pour vous donner une idée de l’apparence d’une telle classe, voici un exemple simple avec quelques fonctionnalités de base:

  • 2d-taille-constructible
  • 2D redimensionnable
  • operator(size_t, size_t) pour l'access aux éléments majeurs sur 2d lignes
  • at(size_t, size_t) pour l'access à l'élément majeur 2d
  • Satisfait aux exigences du concept pour le conteneur

La source:

 #include  #include  #include  #include  namespace masortingces { template class simple { public: // misc types using data_type = std::vector; using value_type = typename std::vector::value_type; using size_type = typename std::vector::size_type; // ref using reference = typename std::vector::reference; using const_reference = typename std::vector::const_reference; // iter using iterator = typename std::vector::iterator; using const_iterator = typename std::vector::const_iterator; // reverse iter using reverse_iterator = typename std::vector::reverse_iterator; using const_reverse_iterator = typename std::vector::const_reverse_iterator; // empty construction simple() = default; // default-insert rows*cols values simple(size_type rows, size_type cols) : m_rows(rows), m_cols(cols), m_data(rows*cols) {} // copy initialized masortingx rows*cols simple(size_type rows, size_type cols, const_reference val) : m_rows(rows), m_cols(cols), m_data(rows*cols, val) {} // 1d-iterators iterator begin() { return m_data.begin(); } iterator end() { return m_data.end(); } const_iterator begin() const { return m_data.begin(); } const_iterator end() const { return m_data.end(); } const_iterator cbegin() const { return m_data.cbegin(); } const_iterator cend() const { return m_data.cend(); } reverse_iterator rbegin() { return m_data.rbegin(); } reverse_iterator rend() { return m_data.rend(); } const_reverse_iterator rbegin() const { return m_data.rbegin(); } const_reverse_iterator rend() const { return m_data.rend(); } const_reverse_iterator crbegin() const { return m_data.crbegin(); } const_reverse_iterator crend() const { return m_data.crend(); } // element access (row major indexation) reference operator() (size_type const row, size_type const column) { return m_data[m_cols*row + column]; } const_reference operator() (size_type const row, size_type const column) const { return m_data[m_cols*row + column]; } reference at() (size_type const row, size_type const column) { return m_data.at(m_cols*row + column); } const_reference at() (size_type const row, size_type const column) const { return m_data.at(m_cols*row + column); } // resizing void resize(size_type new_rows, size_type new_cols) { // new masortingx new_rows times new_cols simple tmp(new_rows, new_cols); // select smaller row and col size auto mc = std::min(m_cols, new_cols); auto mr = std::min(m_rows, new_rows); for (size_type i(0U); i < mr; ++i) { // iterators to begin of rows auto row = begin() + i*m_cols; auto tmp_row = tmp.begin() + i*new_cols; // move mc elements to tmp std::move(row, row + mc, tmp_row); } // move assignment to this *this = std::move(tmp); } // size and capacity size_type size() const { return m_data.size(); } size_type max_size() const { return m_data.max_size(); } bool empty() const { return m_data.empty(); } // dimensionality size_type rows() const { return m_rows; } size_type cols() const { return m_cols; } // data swapping void swap(simple &rhs) { using std::swap; m_data.swap(rhs.m_data); swap(m_rows, rhs.m_rows); swap(m_cols, rhs.m_cols); } private: // content size_type m_rows{ 0u }; size_type m_cols{ 0u }; data_type m_data{}; }; template void swap(simple & lhs, simple & rhs) { lhs.swap(rhs); } template bool operator== (simple const &a, simple const &b) { if (a.rows() != b.rows() || a.cols() != b.cols()) { return false; } return std::equal(a.begin(), a.end(), b.begin(), b.end()); } template bool operator!= (simple const &a, simple const &b) { return !(a == b); } } 

Notez plusieurs choses ici:

  • T doit répondre aux exigences des fonctions membres std::vector utilisées
  • operator() ne vérifie pas "of of range"
  • Pas besoin de gérer les données vous-même
  • Aucun destructeur, constructeur de copie ou opérateur d'affectation requirejs

Donc, vous n'avez pas à vous soucier de la gestion de la mémoire pour chaque application, mais une seule fois pour la classe que vous écrivez.

Ressortingctions

Il peut y avoir des cas où une structure dynamic "réelle" bidimensionnelle est favorable. C'est par exemple le cas si

  • la masortingce est très grande et rare (si certaines des lignes n'ont même pas besoin d'être allouées mais peuvent être traitées en utilisant un nullptr) ou si
  • les lignes n'ont pas le même nombre de colonnes (c'est-à-dire si vous n'avez pas de masortingce à part une autre construction à deux dimensions).

À moins que vous ne parliez de tableaux statiques, 1D est plus rapide .

Voici la disposition mémoire d’un tableau 1D ( std::vector ):

 +---+---+---+---+---+---+---+---+---+ | | | | | | | | | | +---+---+---+---+---+---+---+---+---+ 

Et voici la même chose pour un tableau 2D dynamic ( std::vector> ):

 +---+---+---+ | * | * | * | +-|-+-|-+-|-+ | | V | | +---+---+---+ | | | | | | | | +---+---+---+ | V | +---+---+---+ | | | | | | +---+---+---+ V +---+---+---+ | | | | +---+---+---+ 

Il est clair que le cas 2D perd la localité du cache et utilise plus de mémoire. Il introduit également une indirection supplémentaire (et donc un pointeur supplémentaire à suivre), mais le premier tableau a le surcroît de calcul des indices, donc ceux-ci sont plus ou moins égaux.

Tableaux statiques 1D et 2D

  • Taille: les deux nécessitent la même quantité de mémoire.

  • Vitesse: vous pouvez supposer qu’il n’y aura pas de différence de vitesse car la mémoire de ces deux baies doit être contiguë (le tableau 2D complet devrait apparaître sous forme de bloc en mémoire plutôt que sous forme de blocs répartis dans la mémoire). (Cela pourrait cependant dépendre du compilateur.)

Tableaux dynamics 1D et 2D

  • Taille: Le tableau 2D nécessitera un peu plus de mémoire que le tableau 1D en raison des pointeurs nécessaires dans le tableau 2D pour pointer vers l’ensemble des tableaux 1D alloués. (Ce minuscule n’est que minuscule lorsque nous parlons de très grands tableaux. Pour les petits tableaux, le tout petit peut être assez gros, relativement parlant.)

  • Vitesse: la masortingce 1D peut être plus rapide que la masortingce 2D car la mémoire pour la masortingce 2D ne serait pas contiguë, de sorte que les échecs de cache deviendraient un problème.


Utilisez ce qui fonctionne et semble le plus logique, et si vous rencontrez des problèmes de vitesse, alors refactorez.

Une autre différence entre les tableaux 1D et 2D apparaît dans l’allocation de mémoire. Nous ne pouvons pas être sûrs que les membres du tableau 2D soient séquentiels.

Les réponses existantes ne comparent toutes que les tableaux 1-D aux tableaux de pointeurs.

En C (mais pas en C ++), il existe une troisième option; vous pouvez avoir un tableau 2D contigu alloué dynamicment et ayant des dimensions d’exécution:

 int (*p)[num_columns] = malloc(num_rows * sizeof *p); 

et on y accède comme p[row_index][col_index] .

Je m’attendrais à ce que cela ait des performances très similaires à celles du tableau 1-D, mais cela vous donne une syntaxe plus agréable pour accéder aux cellules.

En C ++, vous pouvez obtenir quelque chose de similaire en définissant une classe qui gère un tableau 1-D en interne, mais qui peut l’exposer via une syntaxe d’access à un tableau 2D utilisant des opérateurs surchargés. Encore une fois, je m’attendrais à ce que les performances soient similaires ou identiques à celles du tableau unidimensionnel ordinaire.

Cela dépend vraiment de la manière dont votre tableau 2D est implémenté.

 int a[200], b[10][20], *c[10], *d[10]; for (ii = 0; ii < 10; ++ii) { c[ii] = &b[ii][0]; d[ii] = (int*) malloc(20 * sizeof(int)); // The cast for C++ only. } 

Il y a 3 implémentations ici: b, c et d Il n'y aura pas beaucoup de différence pour accéder à b [x] [y] ou à [x * 20 + y] puisque vous faites le calcul et que l'autre est le compilateur le faire pour vous c [x] [y] et d [x] [y] sont plus lents car la machine doit trouver l'adresse vers laquelle c [x] pointe, puis accéder à l'élément yth à partir de là. Ce n'est pas un calcul simple. Sur certaines machines (par exemple, AS400 qui dispose de pointeurs de 36 octets (pas de bits)), l'access au pointeur est extrêmement lent. Tout dépend de l'architecture utilisée. Sur les architectures de type x86, a et b ont la même vitesse, c et d sont plus lents que b.

J’aime la réponse complète fournie par Pixelchemist . Une version plus simple de cette solution peut être la suivante. Tout d’abord, déclarez les dimensions:

 constexpr int M = 16; // rows constexpr int N = 16; // columns constexpr int P = 16; // planes 

Ensuite, créez un alias et obtenez et définissez des méthodes:

 template using Vector = std::vector; template inline T& set_elem(vector& m_, size_t i_, size_t j_, size_t k_) { // check indexes here... return m_[i_*N*P + j_*P + k_]; } template inline const T& get_elem(const vector& m_, size_t i_, size_t j_, size_t k_) { // check indexes here... return m_[i_*N*P + j_*P + k_]; } 

Enfin, un vecteur peut être créé et indexé comme suit:

 Vector array3d(M*N*P, 0); // create 3-d array containing M*N*P zero ints set_elem(array3d, 0, 0, 1) = 5; // array3d[0][0][1] = 5 auto n = get_elem(array3d, 0, 0, 1); // n = 5 

La définition de la taille du vecteur lors de l’initialisation offre des performances optimales . Cette solution est modifiée à partir de cette réponse . Les fonctions peuvent être surchargées pour prendre en charge des dimensions variables avec un seul vecteur. L’inconvénient de cette solution est que les parameters M, N, P sont implicitement transmis aux fonctions get et set. Cela peut être résolu en implémentant la solution dans une classe, comme l’a fait Pixelchemist .