Allocation de mémoire supérieur à 4294967295 bytes

**Rodrigue** · 10/05/2006, 16h43

Bonjour,

Dans ma classe Matrix, je dois créer un buffer d'une taille de n x n (n=100288)=10057682944 double (4 bits). Bien évidemment ça plante!

---------------------------
Microsoft Visual C++ Debug Library
---------------------------
Debug Error!

Program: ...

Invalid allocation size: 4294967295 bytes.

(Press Retry to debug the application)
---------------------------
Abandonner Recommencer Ignorer
---------------------------

Bon je dois sauver toutes ses valeurs et y accéder facilement (rapidement si possible), ça ne me dérange pas que ma matrice soit sauvegarder dans un fichier. Comment dois-je faire?

Cordialement,
Rodrigue

**Matthieu Brucher** · 10/05/2006, 16h52

100 000², ce qui donne environ 40Go - 4 octets -, ce que peu de PCs peuvent supporter.
La seule solution : faire autrement. Par exemple en gérant la matrice comme un proxy qui va en fait chercher et calculer sur le disque dur.

**Rodrigue** · 10/05/2006, 17h08

Purée

! Oui j'ai calculé, cela fait: 37.47Go

Donc en gros, je vais me créer un fichier de 37.47Go sur le disque dur

(rien que ça)... et inscrire mes données dedans. Puis je me déplace à un certains offset pour écrire ou relire mes valeurs.
Note: tout ça en NTFS, parce que le FAT32 ne supporte pas plus de 2Go/fichier, donc dans ce cas il faudrait que je segmente ma matrice en plusieurs fichiers

. Dans un premier temps, supposons que je suis en NTFS.
Je pense que je vais utiliser une propriété de symétrie de ma matrice (même si ça va me demander plus de calcul, ça ira toujours plus vite que d'aller lire sur le disque dur). Je n'aurais alors plus qu'un fichier de 18.733Go. Cela reste honorable

!

Hum

! Quelques questions:

Comment créer un fichier sur le disque dur et lui allouer directement une certaine taille (~20Go) ? Je pense que c'est mieux de lui allouer directement sa taille... comme ça s'il n'y a pas assez de place sur le disque dur je génère une erreur!
Je connais la fonction fseek en C pour me déplacer dans un fichier mais est-ce que c'est la fonction à utiliser en C++ (STL)?
Comment remplacer x octets par d'autres octets à un endroit quelconque d'un fichier?

Et merci beaucoup!

**Rodrigue** · 10/05/2006, 17h31

Bon après le choc que j'ai eu j'ai réfléchis!
Je vais utiliser un std::stream (je ne sais pas si je dois utiliser un ofstream et ifstream ou si je peux m'en passer et n'utiliser qu'un std::stream?).
Celui-ci à des fonctions seekg, seekp et tellg (il faut que je regarde laquelle utiliser).
Pour écrire à un endroit du fichier:

Code :

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

1
2
3
4
5
6
7
 
double x[10];
double y;
ofstream f("rodrigue.bin",ios::binary);
f.write((const char*)x, 10*sizeof(double));
f.write((const char*)&y,sizeof(double));
f.close();

Pour lire:

Code :

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

1
2
3
4
5
 
ifstream g("rodrigue.bin",ios::binary);
g.read((char*)x,10*sizeof(double));
g.read((const char*)&y, sizeof(double));
g.close();

Voilà je ne sais toujours pas comment aller placer le pointeur à un endroit donner de mon fichier, ni comment lui allouer une taille prédéterminée (20Go). Je pense également que fstream ne sait gérer que des fichiers de 2Go car son pointeur est un long.

**Matthieu Brucher** · 10/05/2006, 17h48

Pour aller à un endroit donné, il faut aller un peu plus loin dans la doc et aller à seekg.
Ensuite, je ne suis pas sûr que streampos ne puisse pas aller au-delà des 2Go, c'est un objet, pas un long, à priori.

**Laurent Gomila** · 10/05/2006, 17h53

Il y a je crois des fonctions de l'API Windows pour faire des accès aléatoires dans de gros fichiers et en récupérer des morceaux.

**Rodrigue** · 10/05/2006, 20h55

Oui Laurent, il faut utiliser les FileMapping. Je suis en train de me renseigner mais bon jouer avec les API windows ce n'est pas très portable. En plus

CreateFile
CreateFileMapping
MapiewOfFile
MapViewOfFileEx
OpenMappedFile
UmpapViewOfFile
FlushViewOfFile

ce n'est pas vraiment user friendly !

**Rodrigue** · 10/05/2006, 21h01

Il y a la possibilité de mapper le fichier sur 64 bits au lieu de 32 bits.
Taille maximale pour 32 bits: 4Go; tandis que pour 64 bits: 1,718 10^10 Go. J'ai de la marge

...

**Rodrigue** · 10/05/2006, 22h39

Purée je bosse

!
C'est génial les FileMappings: 4Go alloués en une fraction de seconde... terrible, niveau performance je pense pas qu'on puisse faire mieux!
Je ne me suis pas encore frotté au mode 64 bits (il faudra quand même que j'y pense... vu que mon fichier va dépasser les 4Go).

Petit problème à moitié résolu:
j'obtiens un pointeur sur mes données brutes de type void*. Pour pouvoir écrire sur le disque, j'ai créé une structure:

Code :

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

1
2
3
4
5
struct MEMORYDATA
{
   float data[MAXMEMORY/4];
};

où MAXMEMORY est la taille de mon fichier.

après je caste mon pointeur void*:

Code :

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

1
2
MEMORYDATA* ptr_data = (struct MEMORYDATA*)FMappingPtr;

et j'écris (ou je lis), les données de cette manière:

Code :

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

1
2
for(int i=0;i<MAXMEMORY/4;i++)
   ptr_data->data[i] = 3.1415926535897932384626433832795f;

N'y-a-t'il pas plus propre comme méthode?

Je ne le dirai jamais assez: Merci!

**Luc Hermitte** · 11/05/2006, 01h55

Elle n'est pas creuse ta matrice?

**Rodrigue** · 11/05/2006, 09h24

Non, je n'ai que quelques valeurs à 0 (10% grand maximum). Pourquoi sinon, comment aurais-je dû procéder?

**Rodrigue** · 11/05/2006, 09h39

Après mûres réflexions et réécriture de mon système, j'en suis arrivé à la conclusion qu'effectivement je pourrais travailler avec une matrice présentant beaucoup de 0... Il me semble que j'avais déjà eu/lu une remarque à propos de ce type de matrice. Je pense qu'il fallait se tourner vers un std::map<,> mais je n'en sais pas plus!

**Aurelien.Regat-Barrel** · 11/05/2006, 11h28

J'ai croisé une fois un projet de STL basé sur l'utilisation de fichiers, mais je ne me souviens plus de son nom

Sinon en Win32 NTFS supporte les sparse file, tu alloues instantanément 40Go en faisant un seek (SetFilePointerEx) + SetEndOfFile, et partout où tu n'écris pas, NTFS considère que c'est des zéros et il optimise le stockage. De ton point de vue, c'est comme si le fichier faisait effectivement 40 Go, rempli de zéros.
http://msdn.microsoft.com/library/en...arse_files.asp
les file mapping, c'est juste un procédé où l'OS gère la mise en cache et la synchronisation sur disque du fichier pour toi.

**Rodrigue** · 11/05/2006, 11h33

Voilà, donc je dois implémenter une classe de matrice creuse de grandes tailles. Je compte utiliser comme mémoire un FileMappings (cela revient à écrire sur un espace limité en mémoire de 0 à max à l'aide d'un pointeur void*). J'ai vu deux possibilités pour la matrice, la baser sur un std::map<pair<unsigned long, unsigned long>,T> (comme on me l'avait suggéré dans mon précédant post sur les "matrix") ou alors un pointeur de pointeur... Je ne vois vraiment pas comment synchroniser l'une ou l'autre de ces méthodes avec un FileMapping?

**Aurelien.Regat-Barrel** · 11/05/2006, 13h44

Y'a pas de magie avec les file mapping. Ca ne fait que copier en mémoire un bout du fichier. C'est comme si tu le lisais dans un buffer.
Si tu veux pointer des données dans un fichier, il te faut un mécanisme d'adressage à toi, parce que les pointeurs classiques pointent en RAM. J'ai l'impression que tu demandes comment adresser 40Go avec des pointeurs 32 bits, donc comment faire tenir 2L d'eau dans une bouteille d'1L...

**Rodrigue** · 11/05/2006, 14h44

J'ai l'impression que tu demandes comment adresser 40Go avec des pointeurs 32 bits

Non, ce n'est pas ce que je veux faire. Je voudrais créer une classe de matrice creuse (donc bien inférieur à 40Go). La sauvegarde des éléments de cette matrice se ferait dans un ou plusieurs fichiers "mappés" (FileMapping) pour éviter de déborder en mémoire. Donc en gros, j'ai plusieurs fichiers de 4Go max., un pointeur 64 bits (les 32 bits Haut me permettent de savoir dans quel fichier sont sauvegardées mes données tandis que les 32 bits bas me permettent de connaître l'offset dans ce fichier).
L'utilisation serait de ce type:

Code :

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

1
2
3
4
5
 
Matrix M(100000,100000);
M(5,4) = 3.14;
std::cout << M(5,4) << '\n';
std::cout << M(3,2) << '\n'; //cet élément n'existe pas donc je renvoie 0

J'ai déjà une classe de matrice (cf. mon post à ce sujet - recherche: matrix) mais au lieu de créer ma mémoire:

Code :

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

1
2
 
data* double = new double[rows*cols];

Je souhaiterais que mes données soient sauvegardées dans un fichier mappé (oui je me répète).

De le même façon lorsque je lis une valeur avec l'opérateur () (j'ai déjà le code pour le surcharger), au lieu de retourner:

Code :

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

1
2
3
4
5
6
7
8
9
template<class T>
inline T& Matrix<T>::operator() (unsignedlonglong row, unsignedlonglong col)
{
if (row >= rows_ || col >= cols_)
throw ("Matrix subscript out of bounds");
return data_[cols_*row + col];
}

Je souhaiterais aller rechercher ma valeur sauvegardée dans mon fichier mappé. Si cette valeur n'existe pas alors je renvoie 0.

Ce n'est pas un problème de créer/gérer l'ensemble des fichiers mappés (ni de les redimensionner etc), la où ça bloque c'est au niveau du format à adopter: Comment sauvegarder mes données? comment aller les lire?
J'ai réfléchi! Voici comment je vois ça:
Je veux vraiment faire qqchose de générique. Donc on se fixe que:
- n'importe quel type numérique peut être sauvegardé dans la matrice (mais dans un premier temps, on ne considèrera que des doubles!)
- les lignes et les colonnes sont codées sur 32 bits (ce qui me permet de gérer des matrix immenses : 4.10^9 x 4.10^9), soit 64 bits à sauvegarder pour chaque élément (un long long).

Je sauvegarde mes données dans un fichier mappé d'une taille maximale de 4Go (soit 67.108.864doubles, tjrs inférieur à 100.000 x 100.000 !). Chaque fichier mappé à son index. Les éléments dans cet index sont codés sur 64 bits. Donc mes entrées dans l'index, sont au même offset lorsque j'utilise des doubles

.
A chaque fois que je calcule une valeur, si elle est non-nulle j'ajoute cette valeur dans mon dernier fichier mappé (s'il n'y a plus de place, j'en crée un nouveau + un nouvel index associé). Je retiens l'adresse où je l'ai copiée et je vais le marquer dans son index associé. Si j'ai créé un nouveau fichier, je dois l'ajouter dans l'index général (pour être capable de retrouver l'index associé qui me menera à la valeur).

Quand je cherche après une valeur, je parcours l'index général. Premier élément, j'arrive au premier index associé je regarde si mon élément est dedans... Bien sûr tout est classé, si je dépasse une position et que la valeur n'est pas dedans c'est qu'elle n'est pas sauvée (donc je renvoie 0). Si pas je reviens à mon index général, s'il existe, je vais au deuxième index associé et hop' jusqu'à avoir parcouru tout mon index général. Il faudrait que j'ajoute des points de contrôle pour aller plus vite peut-être...

Ou alors, je fais un fichier par ligne de ma matrice. Comme mes colonnes sont sauvegardées sur 32 bits. Mes fichiers de 4Go sont parfaits! Comme ma matrice est creuse, ils ne seront jamais aussi gros... (en plus ma matrice n'est pas aussi large). J'aurais donc au maximum 2^32 fichiers de 4Go. Bon avec des chiffres réalistes par ex. 1.10^6 x 1.10^6. Cela me donne 1000.000 de fichiers de max 1000.000 x 64 bits ~ 61 Mo. Certaines colonnes sont nulles donc les fichiers seront bcp plus petits et certaines lignes sont nulles donc le fichier n'existera pas non plus. Je pense que dans un dossier de windows, on peut créer au maximum 2^32 fichiers.

Bon j'espère ne pas avoir été trop long

, si c'est n'est pas clair, je peux réexpliquer. N'hésitez pas à critiquer parce que je vous l'accorde c'est une idée brute!
Index général (codé sur un short: 256x(4Go+4Go)!) => Index associés => Valeurs associées.

**Rodrigue** · 11/05/2006, 14h54

En gros, je veux faire une base de données optimisées à mon problème

Un premier index pour mes lignes, un deuxième index pour mes colonnes et la valeur sauvegardée. Le tout réparti sur plusieurs fichiers avec une fonction de recherche performante.
Je ne connais rien au sujet

!

**Aurelien.Regat-Barrel** · 11/05/2006, 16h29

J'ai pas tout lu, mais si tu cherches à contrôler la manière dont les conteneurs STL allouent de la mémoire, il faut coder un allocator que tu files à ta map, etc... elle allouera la mémoire via ton allocator, qui fera en sorte qu'elle se trouve dans le fichier mappé.
La STL dont je te parlais au début fonctionnait ainsi, mais en allouant sur disque directement.

**Rodrigue** · 11/05/2006, 16h35

Ah Ok! T'aurais pas un petit code d'exemple pour le std::map avec l'allocator() ?

**Luc Hermitte** · 12/05/2006, 00h30

Envoyé par Rodrigue

Après mûres réflexions et réécriture de mon système, j'en suis arrivé à la conclusion qu'effectivement je pourrais travailler avec une matrice présentant beaucoup de 0... Il me semble que j'avais déjà eu/lu une remarque à propos de ce type de matrice. Je pense qu'il fallait se tourner vers un std::map<,> mais je n'en sais pas plus!

Pour les matrices creuses, les maps ne me parraissent pas hyper adaptées. Je verrais plutôt le principe des deques appliqués à des index. Soit, une structure contigue stockant les données, et un tableaux d'index (vers les éléments) discontinus.

...
C'est certes un excellent exo, ... mais des projets come Blitz++ (qui implémentent des matrices creuses) sont tes amis.

Allocation de mémoire supérieur à 4294967295 bytes

C++

Discussions similaires

Partager

Partager