limite des tableaux en c++ ?

Version imprimable

14/12/2017, 09h23
Legro

limite des tableaux en c++ ?
Bonjour
J'ai un problème de taile de tableau, mais les réponses plus haut ne m'aident pas.
Je cherche à déclarer un tableau 2 dimensions de 50000*50000 mais ça ne marche pas.
La limite semble se trouver un peu après 32000*32000.
Au départ c'était la mémoire qui faisait défaut, mais maintenat je me suis mis sur un ordinateur
avec 16GB de RAM, et en plus j'ai rempli mon tableau de tout petits trucs (un ou deux bits
par case) en faisant :
Code:

1 2 3 4 5 struct Truc { unsigned un : 1 ; unsigned deux :1; }; Truc truc [50000][50000];
Avec codeblooks ça compile et ça plante.
Avec visual studio ça fait une erreur de compilation en précisant qu'un tableau ne doit pas dépasser
une certaine taille (en hexa, avec tout plein de f)
Si quelqu'un sait me dire si on peut contourner ce problème... Merci
14/12/2017, 09h46
ternel

taille de truc = 2 * taille de unsigned = 2 * 64bits = 16 octets.
16 * 50 000 * 50 000 = 16 * 25 * 100 000 000 = 4 * 10 000 000 000 soit 40 giga.
Plus drole, cette taille est prise dans la pile, qui est généralement beaucoup plus petite.

As-tu besoin de tous ces 2,5 milliards d'éléments?

Regarde du coté des matrices creuses.
Sinon, un std::vector que tu encapsules dans une classe de "double tableau", avec value_type const& operator() (size_type i, size_type j) const { return inner[i + j * row_size]; }.
14/12/2017, 09h56
dalfab
Bonjour,

La taille ici est plutôt 50000*50000*sizeof(unsigned)
On peut la diviser par 8 en écrivant
Code:

1 2 3 4 struct Truc { unsigned char un : 1 ; unsigned char deux :1; };
La demande devient 50000*50000*sizeof(char)=2.3G

Citation:

Envoyé par ternel

As-tu besoin de tous ces 2,5 milliards d'éléments?

Regarde du coté des matrices creuses.
Sinon, un std::vector que tu encapsules dans une classe de "double tableau", avec value_type const& operator() (size_type i, size_type j) const { return inner[i + j * row_size]; }.

Très bon conseil :plusser:. Pour aller plus loin, je suggèrerais à OP d'encapsuler une std::map<std::pair<size_type, size_type>, value_type> afin d'avoir une vrai matrice éparse. Voici l'exemple minimal que vous pourrez enrichir selon vos besoins :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include <map> template<class T> class ParseMatrix { public: using size_type = std::size_t; using value_type = T; using container_type = std::map<std::pair<size_type, size_type>, value_type>; private: container_type _data; public: // EDIT : version const de l'opérateur() supprimé, voir dans les messages suivant value_type& operator()(size_type line, size_type col) { return _data[{line, col}]; } };
Et une petite démo live sur coliru.

14/12/2017, 11h59
ternel

Sauf que dans ton implémentation, la fonction const créé des 0 dans la map. Il vaut mieux avoir un 0 à coté, et le retourner.
14/12/2017, 13h22
prgasp77

~~C'est une amélioration possible, comme tant d'autres.~~

EDIT : ce qui précède est faux. Voir mon message suivant.

Citation:

Envoyé par ternel

Sauf que dans ton implémentation, la fonction const créé des 0 dans la map. Il vaut mieux avoir un 0 à coté, et le retourner.

J'aimerais revenir là dessus. Vous avez en réalité parfaitement raison, et ma première approche ("c'est une optimisation possible") est complètement erronée. En effet, _data.operator[] est non-const et ne devrait pas être invoqué dans une fonction const. Une implémentation correcte ne définiraient pas de version constante de l'opérateur d'accès, mais définirait une fonction find à l'instar des conteneurs de la bibliothèque standard.

***

Ce qui suit est complètement théorique, si vous n'êtes pas intéressé par les méandres du standard ISO C++, passez votre chemin. Notez: lorsque j'utilise le vocabulaire du standard, je l'utilise en anglais car je ne connais pas sa traduction. Suggestions bienvenues.

La définition suivante :
Code:

1 2 3 4 value_type const& operator()(size_type line, size_type col) const { return _data[{line, col}]; }
rendrait le programme ill-formed si cette fonction était odr-used. En effet, _data.operator[] est non-const (comme nous l'avons vu ci-dessus). Pourtant, ce code compile parfaitement avec la dernière version de GCC ... pourquoi ?

Il semblerait que cela soit une conséquence des points suivants :

[temp.inst]/2

Citation:

The implicit instantiation of a class template specialization causes the implicit instantiation of the declarations, but not of the definitions [...] of the class member functions [...].

et

[temp.res]/1

Citation:

Knowing which names are type names allows the syntax of every template to be checked. The program is ill-formed, no diagnostic required, if:
- no valid specialization can be generated for a template [...] and the template is not instantiated, or
- [...]

Du fait que ParseMatrix::operator()(size_type line, size_type col) const n'est jamais appelée dans le programme exemple, [temp.inst]/2 assure seulement l'implicit instantiation de sa déclaration (qui est valide) mais pas de sa définition (qui, elle, est invalide) lors de l'explicit instantiation de ParseMatrix<std::string>. En revanche, si cette fonction était appelée, le programme serait effectivement ill-formed mais sans obligation de diagnostique.

Ce qui est amusant, c'est que si le type de ParseMatrix::_data n'était pas dépendant de l'argument template de ParseMatrix, tous les compilateurs ne réagirraient pas de la même manière. Tenez, prenez le programme suivant simplifié :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 // ill-formed program (as expected) // build with: g++ -std=c++17 -Wall -Wextra -Werror -pedantic struct Data { void f() {} }; template<class T> struct Wrapper { Data _data; void f() const { _data.f(); } // to err or not to err? }; int main() { Wrapper<void> w; (void) w; }
La ligne marquée // to err or not to err? génère une erreur de compilation avec certains compilateurs (implementations) et pas avec d'autre. En effet [temp.inst]/2 "no diagnostic required". Et ce n'est pas un bug :

gcc : ERREUR : https://godbolt.org/g/rw7Ufb
clang : OK : https://godbolt.org/g/9HkF3a
icc : OK https://godbolt.org/g/rfjdi4
msvc : OK : https://godbolt.org/g/5tChCL

Merci de votre aide à tous.
Pour ce qui est de la taille en mémoire j'ai quand même l'impression qu'avec mon code ça ne devrait pas prendre plus que (50000*50000*2)/8
Donc 2.5 G.
Et en fait n'ayant pas besoin de tous les élément mais que de la moitié, mais qu'ils soient tout de même dans une matrice de largeur et hauteur
de 50000, j'avais codé
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 struct Truc {unsigned un :1; unsigned deux :2; }; int main () { int taille =50000; Truc ** truc = new Truc* [taille]; for (int i=0;i<taille;i++) truc [i] = new Truc [taille-i]; // et tous les delete qui s'en suivent évidemment return 0; }
Et malgré tout ça plantait, alors que c'était dans le tas, et que je dispose de 16 G de RAM et que tout cela ne devrait pas prendre
plus de 1 Giga et quelques...
En tout cas encore une fois merci de vos réponses.

Ton code consomme beaucoup plus que 2.5G

Code:

1
2
3
4
5
6
7
8
9
10
11
struct Truc 
{unsigned un :1;   // 8 octets car basé sur int
unsigned deux :2;
};
int main ()
{
int taille =50000;
Truc ** truc = new Truc* [taille];  // 50000 pointeurs => 50000*8+24
for (int i=0;i<taille;i++)
truc [i] = new Truc [taille-i]; // [50000*8+24+49999*8+24+...+1*8+24]
// total : 9.31G

celui-là fait 2.3G

Code:

1
2
3
4
5
6
struct Truc { 
 unsigned char un : 1 ;  // 1 octet car basé sur char
 unsigned char deux :1;
 };
Truc  (*truc )[50000] = new Truc[50000][50000]; // utilise 50000*50000*1+24
// total: 2.3G et la moitié ne sert à rien

17/12/2017, 08h53
Legro

Ok c'est très clair, et en plus j'ai maintenant l'embaras du choix pour résoudre mon problème. Je pense que je vais tout tester
il ne me reste plus qu'a me mettre au boulot

:pc:

Merci beaucoup à tous

:merci:

Salut,
Citation:
Envoyé par prgasp77
La définition suivante :
Code:

1 2 3 4 value_type const& operator()(size_type line, size_type col) const { return _data[{line, col}]; }
rendrait le programme ill-formed si cette fonction était odr-used. En effet, _data.operator[] est non-const (comme nous l'avons vu ci-dessus).
Ca, tu peux le contourner assez facilement, grace au const_cast.

Car, après tout, c'est une fonctionnalité qui existe et, même s'il ne faut pas l'utiliser avec énormément de précautions, elle peut régulièrement nous sortir de l'embarras ;)

C'est le cas ici, car, a priori, tu auras une version constante et une version non constante de ton opérateur (). Tu peux donc, grâce au const_cast, en utiliser la version non constante dans la version constante sous une forme proche de
Code:

1 2 3 4 5 6 7 /* permet à l'utilisateur de changer la valeur de l'élément */ value_type & operator()(size_type line, size_type col){ return data[{line, col}]; } value_type /* const & */ operator()(size_type line, size_type col) const{ return const_cast<ParseMatrix &>(*this)[line, col]; }
grâce auquel le programme sera tout à fait bien formé ;) Avec une assertion, si possible, sur l'existence même de l'élément, ce sera parfait ;)

Il n'y a que le détail du type de retour: il serait pas mal d'avoir un trait de politique pour déterminer si la version constante doit renvoyer l'élément par valeur ou par référence constante, en fonction de la taille des données maintenues :D

Citation:

Envoyé par koala01

Ca, tu peux le contourner assez facilement, grace au const_cast.

Car, après tout, c'est une fonctionnalité qui existe et, même s'il ne faut pas l'utiliser avec énormément de précautions, elle peut régulièrement nous sortir de l'embarras ;)

grâce auquel le programme sera tout à fait bien formé ;) Avec une assertion, si possible, sur l'existence même de l'élément, ce sera parfait ;)

Non, surtout pas ! On tombe allègrement dans l'undefined behaviour qui vous sautera au visage à la première occasion.
Citation:
Envoyé par N4713
[dcl.type.cv]/3&4

3. A pointer or reference to a cv-qualified type need not actually point or refer to a cv-qualified object, but it
is treated as if it does; a const-qualified access path cannot be used to modify an object even if the object
referenced is a non-const object and can be modified through some other access path.

4. Except that any class member declared mutable (10.1.1) can be modified, any attempt to modify a const
object during its lifetime (6.6.3) results in undefined behavior. [Example: [...]
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 struct X { mutable int i; int j; }; struct Y { X x; Y(); }; const Y y; y.x.i++; // well-formed: mutable member can be modified y.x.j++; // ill-formed: const-qualified member modified Y* p = const_cast<Y*>(&y); // cast away const-ness of y p->x.i = 99; // well-formed: mutable member can be modified p->x.j = 99; // undefined: modifies a const subobject
—end example ]
(la page de cppreference est plus accessible)

Si operator() est appelé sur un objet constant (on a défini la version constante à cette fin), [dcl.type.cv]/4 est applicable => undefined behaviour. Mieux vaut, comme l'a suggéré ternel retourner une référence vers un zero constant interne, ou comme la stl le fait, ne pas fournir de version const mais une fonction membre find.

19/12/2017, 11h11
Bousk

La version const de Koala retourne une copie, tu peux bien la modifier autant que tu veux, ça ne touchera jamais l'objet et son membre. :roll:
Utiliser const_cast pour écrire le getter d'une fonction membre const & non const en en implémentant une seule (la non-const) et const_cast l'autre est un pattern des plus classiques. :calim2:
19/12/2017, 11h20
prgasp77

Citation:

Envoyé par Bousk

La version const de Koala retourne une copie, tu peux bien la modifier autant que tu veux, ça ne touchera jamais l'objet et son membre. :roll:

const_cast<ParseMatrix &>(*this)(line, col) (j'ai corrigé ce que je suppose être une faute de frappe) appelle std::map::operator[] qui est non const. Quand l'objet recherché n'existe pas, il est créé (modification explicite d'un objet const) ; quand il existe on peut supposer qu'il n'y a pas de modification, mais on ne peut en être certain : imagine une implémentation dans laquelle l'index de recherche de la map serait construit juste à temps.

Vous me direz que c'est pinailler. Que koala suggérait lui-même de vérifier l'existence de l'objet. C'est que nous ne pensons pas dans le même contexte : j'ai entamé cette discussion dans le contexte du standard C++, donc très à cheval sur ces détails. En prenant du recul, ou en se limitant aux bonnes pratiques de l'industrie, mon discourt aurait été tout à fait différent.

Cependant, ma conclusion reste la même, mieux vaut dans un tel cas ne pas définir d'accesseur constant, mais une fonction membre find.

Citation:

Envoyé par Bousk

Utiliser const_cast pour écrire le getter d'une fonction membre const & non const en en implémentant une seule (la non-const) et const_cast l'autre est un pattern des plus classiques. :calim2:

Dans ce cas, oui, j'approuve la factorisation du code. Mais la subtilité de l'exemple avec ParseMatrix c'est que le getter a un effet de bord, et c'est cette subtilité qui a engendré mon erreur initiale et la discussion entamée par ternel.
20/12/2017, 13h58
koala01

Citation:

Envoyé par prgasp77

const_cast<ParseMatrix &>(*this)(line, col) (j'ai corrigé ce que je suppose être une faute de frappe) appelle std::map::operator[] qui est non const. Quand l'objet recherché n'existe pas, il est créé (modification explicite d'un objet const) ; quand il existe on peut supposer qu'il n'y a pas de modification, mais on ne peut en être certain : imagine une implémentation dans laquelle l'index de recherche de la map serait construit juste à temps.

C'était effectivement une faute de frappe, merci de me l'avoir signalé ;)

Citation:

Vous me direz que c'est pinailler. Que koala suggérait lui-même de vérifier l'existence de l'objet. C'est que nous ne pensons pas dans le même contexte : j'ai entamé cette discussion dans le contexte du standard C++, donc très à cheval sur ces détails.

C'est bien pour cela que j'avais précisé qu'une assertion sur l'existence de l'objet serait parfaite, car on ne peut, effectivement, pas laisser passer cette erreur en production.

Or, ce serait typiquement une erreur de logique qui devra être corrigée au plus tôt ;)

Note d'ailleurs que, si je devais utiliser ce genre de code, l'assertion serait forcément présente, parce que, justement, cela pourrait facilement tourner au comportement indéfini à cause de l'effet de bord ;)

Quant à moi, j'ai fait l'erreur de reprendre "bêtement" du code, sans y réfléchir correctement et sans y apporter toute l'attention qu'il méritait :oops:
Et puis, je ferais sans doute encore différemment, pour, justement, éviter cet effet de bord:

Je ferais sans doute une fonction insert, qui n'ajouterait un élément que s'il n'existe pas (avec assertion sur ce point particulier), j'implémenterais l'opérateur () non constant à l'aide de find (et une assertion sur le fait que l'élément existe), et, bien sur, une fonction exists pour permettre à l'utilisateur de savoir quel comportement choisir.

Car, de manière générale, je me méfie toujours de ce qui fini par être des "sucres syntaxiques" qui permettent à l'utilisateur d'utiliser une fonction dans deux contextes totalement différents ;)

Citation:

En prenant du recul, ou en se limitant aux bonnes pratiques de l'industrie, mon discourt aurait été tout à fait différent.

Cependant, ma conclusion reste la même, mieux vaut dans un tel cas ne pas définir d'accesseur constant, mais une fonction membre find.

Ou d'éviter l'effet de bord de l'opérateur non constant. Ce qui, de mon point de vue, ne présente que des avantages, vu que, a priori, l'utilisateur de la classe est sensé distinguer dans son code la logique d'ajout d'éléments de la logique d'accès / modifications sur les éléments existants.

EDIT
En fait, au final:
tu avais tout à fait raison de hurler, en l'état actuel du code, à cause du comportement indéfini qu'il pouvait provoquer, mais, tu t'es trompé de cible en visant l'opérateur constant...

Ce sur quoi aurait du porter ton ire, c'est justement l'opérateur non constant à cause de son effet de bord ;)
22/12/2017, 10h26
prgasp77

Citation:

Envoyé par koala01

tu avais tout à fait raison de hurler, en l'état actuel du code, à cause du comportement indéfini qu'il pouvait provoquer, mais, tu t'es trompé de cible en visant l'opérateur constant...

Ce sur quoi aurait du porter ton ire, c'est justement l'opérateur non constant à cause de son effet de bord ;)

Avec du recul, je suis d'accord avec cette conclusion. Mais tant qu'à faire ainsi :

Citation:

Envoyé par koala01

j'implémenterais l'opérateur () non constant à l'aide de find (et une assertion sur le fait que l'élément existe)

Pourquoi ne définir des fonctions dont le nom est connu et évocateur : value_type& at(size_type line, size_type col) (const et non-const) qui throw si l'élément n'existe pas. Adjointes à iterator find(size_type line, size_type col) (const et non-const) ainsi qu'à std::pair<iterator, bool> insert(value_type const& value), une telle classe aurait tout l'arsenal d'un conteneur utile !
22/12/2017, 16h25
koala01

Parce que les exceptions ne devraient pas être utilisées en cas d'erreur de logique de la part du développeur.

La fonction at() de std::vector, par exemple, est une pure aberration, car le développeur est sensé s'assurer qu'il ne dépassera jamais le dernier élément existant ;)

Si le développeur décide de demander l'accès à un élément inexistant, ou s'il décide d'insérer un élément existant à une map, c'est clairement une erreur de logique, qui doit être corrigée au plus vite, car il s'agit de préconditions au bon fonctionnement des fonctions appelées.

Et ca, ca se traduit par une assertion (qui sera généralement remplacée par une noop en release) ;)
24/12/2017, 10h11
Médinoc

Sauf que les erreurs peuvent êtres difficiles à détecter par analyse et ne se produire que dans des circonstances rares qui auraient échappé au test...

Dans certains domaines (sécurité, médical etc.), on ne joue pas et on veut que le test soit là même en Release.
29/12/2017, 17h46
JolyLoic

Rien n'oblige à enlever les assert en mode optimisé... Ou à les remplacer par autre chose (une exception reste envisageable). Je reconnais qu'aujourd'hui, c'est assez rudimentaire comme système, mais ça marchotte quand même un peu...