Discussion :

[ceugniet]

Bonjour à tous,

Je travaille avec de gros tableaux. Comme il m'arrive fréquemment d'être un peu limite question mémoire, je souhaite pouvoir créer des tableaux dans le stack.

Enfin, c'est ce que j'ai compris, mais je n'en suis pas certain ; il semble qu'il y a deux sortes de mémoires. Si l'on crée un tableau avec des dimensions connues à la compilation par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
char table[1000000][2]

par exemple, on utilise une sorte de mémoire. Si au contraire on crée le tableau à l'exécution par :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
char **table_dyn;
...
   table_dyn = new char*[dim1];
   for (int j=0;j<dim1;j++)
      table_dyn[j] = new char[dim2];

on utilise alors une autre sorte de mémoire, qui est moins limitée que la première, et surtout qui en tous cas vient en complément de la première. Il me semble que c'est celle-là que l'on appelle le "stack". L'autre avantage est bien entendu d'avoir la possibilité d'ignorer les dimensions du tableau à la compilation : on peut utiliser une variable pour dimensionner à l'exécution.
Mais peut-être n'ai-je rien compris ! Suis-je complètement à côté de la plaque ?

Je connais dès la compilation les dimensions de mes tableaux, donc cette possibilité de les dimensionner à l'exécution seulement ne m'est pas indispensable.

Ma question concerne la mémoire occupée, d'une part, les performances du programme, d'autre part.

Avec :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
char table[1000000][2]

l'occupation mémoire est exactement de 2000000 octets (logique !). sizeof(table) me renvoie bien 2000000. Et la différence d'adresse entre le dernier octet et le premier octet de mon tableau est bien 1999999.

Ce qui me gêne c'est que dans le cas d'une définition dynamique avec "new",

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
char **table_dyn;
...
   table_dyn = new char*[dim1];
   for (int j=0;j<dim1;j++)
      table_dyn[j] = new char[dim2];

je constate que les deux octets table_dyn[0][0] et table_dyn[0][1] étant bien dans deux adresses consécutives, l'octet suivant (table_dyn[1][0]) est situé après un saut de 14 octets. De même, les octets table_dyn[1][0] et table_dyn[1][1] sont consécutifs, et table_dyn[2][0] saute à nouveau 14 octets. Et ainsi de suite (je pense que C++ utilise systématiquement une adresse multiple de 16 à chaque utilisation de "new"). Il me semble clair qu'à chaque utilisation de "new" le système place le nouveau tableau là où il trouve de la place, ce qui ne me gêne nullement) mais surtout, qu'il perd systématiquement des octets (ici, 14) à vouloir placer les nouveau tableaux à des adresses multiples de 16 (et ça, ça ma gêne car cela multiplie par 8 (dans mon cas) la place occupée).

sizeof(table_dyn) me donne 4 !! Bah, cela ça m'est égal, mais bon !

Le deuxième problème est qu'avec une telle organisation, les performances du programme risquent fort d'être dégradées à cause d'une double référence mémoire pour localiser chaque élément du tableau - ceci étant dû à la non régularité des emplacements.

Mes questions est donc :

Y-a-t-il moyen de créer un tableau à deux dimensions en une seule commande avec new, de manière à créer un bloc de 2000000 octets consécutifs sans gaspillage de mémoire et en optimisant les performances ?

Et :

Y-a-t-il moyen de créer un tableau de dimensions connues à la compilation, mais dans cette deuxième mémoire utilisée par "new" (c'est-à-dire dans le "stack, n'est-ce pas ?), possibilité qui elle aussi résoudrait mon problème ?


Merci d'avance pour vos réponses !

[Sylvain Togni]

Le plus simple dans ton cas est surement d'allouer dynamiquement des char[2] :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
typedef char Row[2];
Row* table = new Row[1000000];
 
table[999][1] = 42;
 
delete [] table;

[befalimpertinent]

Y-a-t-il moyen de créer un tableau de dimensions connues à la compilation, mais dans cette deuxième mémoire utilisée par "new" (c'est-à-dire dans le "stack, n'est-ce pas ?), possibilité qui elle aussi résoudrait mon problème ?

pile et tas

FAQ C
La pile et le tas sont 2 parties dans lesquelles sont stockées les variables.
La pile, de taille plus réduite, contient les variables automatiques, les variables locales des fonctions, .... Elles sont détruites automatiquement.
Par opposition, le tas est d'une taille plus importante et contient les variables allouées dynamiquement. Elles doivent êtré détruites explicitement.

new = allocation dynamique = tas (heap)

[ceugniet]

Le plus simple dans ton cas est surement d'allouer dynamiquement des char[2]

Super ! Ca marche au poil ! Ma méconnaissance de la syntaxe de C++ me plonge souvent dans un abîme de perplexité. En fait je ne savais pas utiliser "typedef", tout simplement. J'ai recopié ton code. Effectivement, avec cette méthode, les octets utilisés sont au nombre de 2000000 exactement, bien rangés.

De plus, en attendant une réponse, j'ai fait des tests de performance. Avec la méthode que j'utilisais (faire m1 fois "new" et ainsi créer m1 tableaux non régulièrement répartis) le petit test de rapidité que j'ai fait montre qu'il faut plus trois fois plus de temps pour accéder à un élément de mon tableau que dans le cas d'une définition initiale sans "new". Je viens de refaire le test avec ta méthode et ça paie. Cela prend le même temps que dans le cas d'une définition initiale sans "new".

Merci mille fois ! C'est exactement la réponse que je cherchais !

[ceugniet]

pile et tas

new = allocation dynamique = tas (heap)

OK ! Je te remercie de ces précisions de vocabulaire ! Effectivement, je mélangeais un peu tout ! Ma question était donc de pouvoir créer dynamiquement dans le tas de gros tableaux à deux dimensions même si je connaissais d'avance la taille de ces tableaux, de manière à ne pas être limité par la taille de la pile. Si j'ai bien compris, les tableaux créés dans le programme par "char table[1000000][2]" sont créés dans la pile, et ceux créés par un ou plusieurs "new" sont créés dans le tas.

La réponse de Sylvain Togni est donc parfaite pour résoudre mon problème.

Merci encore de vos réponses très rapides !

[r0d]

Bonjour,

juste une remarque:
en c++ on utilisera plutôt un vector d'objet plutôt qu'un tableau "C style". Par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <vector>
 
struct Row
{
    char c1;
    char c2;
};
 
size_t nbRow = 100000;
std::vector<Row> table(nbRow);
if ( table.capacity() < nbRow )
{
// erreur: allocation impossible
}

En utilisant cette façon de procéder, tu es assuré que chaque élément (ici Row) est contigü en mémoire, et que chaque c1 et c2 le sont également.

[ceugniet]

Bonjour,

juste une remarque:
en c++ on utilisera plutôt un vector d'objet plutôt qu'un tableau "C style". Par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <vector>
 
struct Row
{
    char c1;
    char c2;
};
 
size_t nbRow = 100000;
std::vector<Row> table(nbRow);
if ( table.capacity() < nbRow )
{
// erreur: allocation impossible
}

En utilisant cette façon de procéder, tu es assuré que chaque élément (ici Row) est contigü en mémoire, et que chaque c1 et c2 le sont également.

Merci à toi aussi ! Mais là je ne suis pas partant ! En effet, l'exemple que j'ai donné n'est qu'un exemple parmi d'autres. Une rangée pourrait avoir 3, 4, ou 10 valeurs et pas seulement deux. Par conséquent, le fait de ne pas pouvoir indexer me gêne énormément. Je peux faire référence à table[5000].c1 ou table[5000].c2 mais pas au "i-ième élement" de table[5000] i étant une variable entière !

De plus, c'est ce que je craignais, les performances s'écroulent. Il faut deux fois plus de temps de calcul pour faire référence à un élément que dans la méthode de Sylvain Togni, qui elle-même a les même performances que dans le cas d'une définition dans la pile par "char table[1000000][2]" ! Alors, ya pas photo !

Merci quand même de ta participation.

[Médinoc]

Pour être précis, il y a trois sortes de mémoire (+ le code) : La troisième sorte comprenant les variables globales et toutes les variables déclarées static.

[r0d]

Il y a au moins un autre type de mémoire, l'endroit où sont stockées les constantes. Je crois qu'il y en a un 5eme, mais je ne trouve pas de référence à ce sujet. Il me semble que dans le Exceptional C++ de Sutter il en parle.

Sinon, pour les performances sur les accès aux éléments d'un vector de structures, si c'est bien implémenté, elles sont équivalentes (les performances).

[Médinoc]

Je crois que les constantes sont en mémoire "statique", tout simplement. Par contre, elles sont sur des pages en lecture seule sur les systèmes qui gèrent ça (sous des vieux systèmes comme DOS, il n'y avait à ma connaissance pas de différence).

[r0d]

Haaa ayé j'ai trouvé

http://www.gotw.ca/gotw/009.htm

(encore une fois, c'est dans les gotw qu'il fallait chercher...)

Il y a donc bien 5 types de mémoire:
-> Const Data (kesskejdisais!!! )
-> Stack
-> Free Store (je n'ai pas trop compris ce que c'est que ça)
-> Heap
-> Global/Static (c'est ce dont tu parlais)

[ceugniet]

Sinon, pour les performances sur les accès aux éléments d'un vector de structures, si c'est bien implémenté, elles sont équivalentes (les performances).

Au temps pour moi ; je pense que j'avais mal mesuré. J'ai refait la manip ! Avec le code suivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
...
#include <vector>
char table[1000000][2];
int dim1,dim2;
 
struct Row2
{
    char c1;
    char c2;
};
 
int main(int argc, char* argv[])
{
   // Création dynamique tableau tablevec
   size_t nbRow = 1000000;
   std::vector<Row2> tablevec(nbRow);
   int n,k=2000000,i,j;
   srand(1);    // Initialisation racine random
   int NN=1000000000;
   // Mesure du temps de 1 000 000 000 appels random
   // avec incrémentation de table
   t00=topsuper();     // Appel chrono
   for (int ii=0;ii<NN;ii++)
   {
      n=random(k);
      i=n/2;
      j=n%2;
      table[i][j]++;
   }
   t01=topsuper();     // Appel chrono
   A=t01-t00;
   printf("test table                       A = %Lu tops\n",t01-t00);
   // Mesure du temps de 1 000 000 000 appels random
   // avec incrémentation de tablevec
   srand(1);    // Initialisation racine random
   t00=topsuper();
   for (int ii=0;ii<NN;ii++)
   {
      n=random(k);
      i=n/2;
      j=n%2;
      if (j)
         tablevec[i].c2++;
      else
         tablevec[i].c1++;
   }
   t01=topsuper();
   //int m;
   B=t01-t00;
   printf("test tablevec                    B = %Lu tops\n",t01-t00);
   int m=0;
   srand(1);    // Initialisation racine random
   t00=topsuper();     // Appel chrono
   for (int ii=0;ii<NN;ii++)
   {
      n=random(k);
      i=n/2;
      j=n%2;
      m++;
   }
   t01=topsuper();     // Appel chrono
   printf("m=%d\n",m);
   C=t01-t00;
   printf("Temps de calcul random + indices C = %Lu tops\n",t01-t00);
   printf("références à table :           A-C = %Lu tops\n",A-C);
   printf("références à tablevec :        B-C = %Lu tops\n",B-C);
   printf("%d\n",((B-A)*100)/(A-C));
   return 0;
}

Le résultat :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
test table                       A = 424857417360 tops
test tablevec                    B = 467380471065 tops
m=1000000000
Temps de calcul random + indices C = 192473514015 tops
références à table :           A-C = 232383903345 tops
références à tablevec :        B-C = 274906957050 tops
18

J'ignore pourquoi mes premières mesures étaient si différentes. Cette fois, j'ai supprimé toutes mes fenêtres et ma connexion à Internet, et j'ai pris une durée suffisamment longue pour que l'on puisse raisonnablement penser que les interruptions système (que je ne contrôle bien sûr absolument pas !) soient à peu près les mêmes pour les trois tests.
A mesure le temps pour table, B pour tablevec. Quant à C il refait les mêmes calculs en faisant référence à une seule variable, ceci pour évaluer le temps qui n'est pas "accès à un tableau". Par différence on peut ainsi comparer les temps d'accès aux deux types de tableaux.

Il y a quand même 18% de différence ! Ce qui, j'en conviens, n'est pas réellement catastrophique.

Reste malgré tout l'impossibilité d'indexer...

[ceugniet]

Il y a donc bien 5 types de mémoire:
-> Const Data (kesskejdisais!!! )
-> Stack
-> Free Store (je n'ai pas trop compris ce que c'est que ça)
-> Heap
-> Global/Static (c'est ce dont tu parlais)

Dans les options de C++ Builder, il y a deux nombres que l'on peut changer, la taille du tas max et la taille de la pile max.

Pour ce qui me concerne, c'est bien l'endroit où sont stockées les variables qui m'intéresse.

Ces 5 types de mémoire sont elles stockées dans cinq zones distinctes ? En d'autre termes, si une variable est stockée dans "const data", dans "free store" ou dans "Global static" elle ne me vole pas de l'espace dans la pile ni dans le stack ?

La plupart de mes tableaux sont globaux, définis en tête de programme, accessibles par tous. Il s'agit donc à mon sens de tableaux globaux statiques, non ? Eh bien il me semble bien qu'ils sont dans la pile, et c'est bien pour éviter qu'ils ne saturent la pile que je souhaitais connaître un moyen de les mettre ailleurs ! D'où l'idée d'utiliser le tas où l'on ne peut (si j'ai bien compris) créer des tableaux que dynamiques, c'est-à-dire via la commande new.

[Sylvain Togni]

Les 18% de différences viennent du if/else en plus, pas de l'accès, qui doit être aussi rapide. Tu peux le vérifier en utilisant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
struct Row2
{
    char c[2];
};
 
...
 
tablevec[i].c[j]++;

Ces 5 types de mémoire sont elles stockées dans cinq zones distinctes ? En d'autre termes, si une variable est stockée dans "const data", dans "free store" ou dans "Global static" elle ne me vole pas de l'espace dans la pile ni dans le stack ?

Ces 5 zones sont théoriques, en pratique tout est en général dans la RAM.

[Jean-Marc.Bourguet]

-> Free Store (je n'ai pas trop compris ce que c'est que ça)
-> Heap

Free store -> gere par new/delete
Heap -> gere par malloc/free

Ces 5 types de mémoire sont elles stockées dans cinq zones distinctes ?

Ce sont des zones qui sont generees differemment par le C++. Apres, l'implementation fait ce qu'elle veut. En particulier
- free store et heap peuvent etre la meme zone physique
- l'implementation peut introduire d'autres divisions (globales/statiques intialisees statiquement a autre chose que 0 est courant)

En d'autre termes, si une variable est stockée dans "const data", dans "free store" ou dans "Global static" elle ne me vole pas de l'espace dans la pile ni dans le stack?

Un process a un espace memoire total et celui-ci n'est pas extensible a l'infini. Donc ce qui est utilise par quelque chose ne peut pas l'etre pour l'autre.