Discussion :

[ickis69]

Bonjour.

J'ai un problème avec la taille maximale d'un tableau de char.
Je programme en C avec le compilateur Bloodshed Dev-C++

Contexte:
Je travaille sur un programme de traitement de données.
Je dois lire un fichier entier et le stocker dans un tableau pour le traiter.

J'ai
maximum 300.000 paragraphes,
maximum 200 lignes par paragraphe
maximum 1.000 caractères par ligne
Ce sont des tailles maximales idéales, m'assurant de lire 100% des données.
Edit : en pratique, le fichier ne fait que 800Mo.

J'ai donc imaginé de le stocker dans un tableau :

Code :

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

1
2
char [numéro de paragraphe] [numéro de ligne] [nombre de caractère de la ligne]
char [300000][200][1000]

A la compilation -> size of array is too large :-(


Il me serait difficile de re-écrire tout le programme pour travailler " à la vollée" et donc éviter de charger le fichier entier.

Donc je cherche une solution alternative. Comme en moyenne, les paragraphes sont beaucoup plus petits que 200 lignes et 1000 caractères par lignes, j'ai pensé à utiliser une allocation dynamique, mais je ne sais pas comment m'y prendre.

Merci de votre aide.

[gerald3d]

Honnêtement le traitement à la volée ne doit pas être la mer à boire. La modification de ton code ne doit pas être si importante que ca.

Quel type de traitement effectues-tu sur ces données pour qu'on comprenne un peu mieux tes soucis?

[souviron34]

J'ai un problème avec la taille maximale d'un tableau de char.
Je programme en C avec le compilateur Bloodshed Dev-C++
...
J'ai donc imaginé de le stocker dans un tableau :

Code :

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

1
2
char [numéro de paragraphe] [numéro de ligne] [nombre de caractère de la ligne]
char [300000][200][1000]

A la compilation -> size of array is too large :-(

300 000 * 200 = 60 000 000

* 1000 = 60 000 000 000 = environ 70 Giga octets..

En C ou pas en C tu auras un problème sur la majoirité des machines

[gangsoleil]

environ 70 Giga octets..

En C ou pas en C tu auras un problème sur la majoirité des machines

Oui, et j'ajouterai surtout que tu auras des problemes en allocation statique comme en allocation dynamique.

Tu as un probleme de "passage a l'echelle", c'est a dire que l'algorithme que tu as concu s'applique bien sur un petit volume de donnees, mais pas sur un gros volume.
Il est necessaire de repenser ton algorithme si tu veux pouvoir traiter tes donnees, par exemple en faisant un traitement par lots, en travaillant sur une base de donnees, ...

[diogene]

Tu dois malgré tout avoir une idée sur le nombre total de caractères que tu dois lire, en regardant la taille du plus gros fichier à traiter.
Si il fait 60Go, il faut revoir ta copie.
Si il a une taille de disons 1Go, tu peux effectivement envisager de passer par de l'allocation dynamique ajustée au contenu du fichier pour stocker l'intégralité du fichier. Dans ce cas, le code de chargement et d'exploitation des données sera à revoir, car la structure de données utilisée ne sera pas un tableau à 3 dimensions.

[ickis69]

Bonjour et merci de vos réponses.

Effectivement, re-structurer mes algorithmes pour travailler par lot à la volée c'est la solution noble.

Mais je me demandais si il n'y avait pas une autre solution, plus simple et rapide. Comme je viens de le spécifier dans le post d'origine, le fichier ne fait en pratique "que 800 Mo".

[ickis69]

Bonsoir.

Quelques heures de travail plus tard, j'ai refondu l’algorithme, tout marche super

Mais par curiosité, comment on aurait pu faire autrement (char *, malloc, etc ?!)

Merci.

[gangsoleil]

Mais par curiosité, comment on aurait pu faire autrement (char *, malloc, etc ?!)

Tu veux dire pour utiliser 60 Go de memoire ? Ca semble difficilement possible avec des machines et des librairies standard.

[Obsidian]

Bonsoir. Quelques heures de travail plus tard, j'ai refondu l’algorithme, tout marche super Mais par curiosité, comment on aurait pu faire autrement (char *, malloc, etc ?!)

D'une manière générale, les tableaux locaux définis de la sorte vont dans la pile. Il est donc important de veiller à ce qu'il aient toujours une taille réduite et, si possible, une durée de vie limitée. Si tu as besoin de beaucoup de mémoire, il vaut mieux la demander au système avec malloc() mais, même dans ce cas, tu ne peux pas réclamer autant en une seule fois.

Je pense que la manière la plus élégante de faire cela consiste à mapper le fichier en mémoire. C'est à la fois plus simple du côté de ton logiciel et du système, à qui tu laisses toute lattitude pour organiser les choses proprement.

De toutes façons, si tu veux voir l'intégralité de tes 60 Go alloués en un seul morceau, il te faut une architecture 64 bits pour pouvoir les placer dans le plan mémoire.

[diogene]

maximum 300.000 paragraphes,
maximum 200 lignes par paragraphe
maximum 1.000 caractères par ligne
Ce sont des tailles maximales idéales, m'assurant de lire 100% des données.
Edit : en pratique, le fichier ne fait que 800Mo.

Avec
Npara = nombre total de paragraphes (< 300 000)
NLignes = nombre total de lignes (< 300 000* 200 = 60 10^6)
NCar = nombre total de caractères (< 800 10^6)
on peut envisager par allocation dynamique d'utiliser au maximum
- un tableau de ~ NPara pointeurs pour les paragraphes
- Des tableaux de pointeurs pour les lignes. Au total ~ NLignes pointeurs
- Des tableaux pour stocker les caractères. Au total ~ NCar bytes

Avec des pointeurs sur 4 bytes, cela donne au total (NPara+NLignes)*4 +NCar bytes. Le nombre de paragraphe intervient peu car NPara<< NLignes et le surcoût mémoire sera inférieur à ~ NLignes*4 = 240 Mbytes.
Au total, la quantité memoire maximum sera de 240+800 Mbytes
Si on est peut allouer 1.1Gbytes de mémoire, il est possible d'envisager une telle solution.

[souviron34]

Admettons, mais :

• si c'est pour du traitement, on ne trate pas tout un bouquin d'un coup. Vraisemblablement au max 1 paragraphe
  
• si c'est pour de la lecture, c'est kif-kif.. il suffit de ne charger que +/- x pages, c.a.d. +/- y paras ou +/- z caracs, et de charger par incréments suivant qu'on va vers l'avant ou l'arrière

Sinon, le problème de cette approche, même si cela peut être faisable sir le fichie ne fait "que" 800, c'est quand mêm les limites que cela impose sur la machine..

Faire des choses rusées pour économiser les ressources, c'est quand même bien

[diogene]

Je me suis livré à ce petit calcul parce que cette solution avait été rejetée a priori sans avoir vraiment été considérée.
Il me semble naturel dans ce genre de choses de se poser la question préalable : combien me faut-il de mémoire ? (question que le PO ne s'était d'ailleurs pas posée !)
- réponse 1 : 60Go! impossible
- et en organisant au mieux les données ? réponse 2 : 1.1Go! envisageable
- puis-je m'affranchir de cette limite et envisager de traiter des fichiers plus gros ? réponse 3 : modifier l'algorithme

La 3ieme réponse était la meilleure (surtout que cette modification de l'algo a été ici facilement exécutée). La faille dans le projet du PO était liée à l'algorithme utilisé pas aux données.

[jlliagre]

60 000 000 000 = environ 70 Giga octets..

Je dirais plutôt exactement 60 Giga octets (= 55.8 "Gibioctets").

[jlliagre]

combien me faut-il de mémoire ? (question que le PO ne s'était d'ailleurs pas posée !)
- réponse 1 : 60Go! impossible

Pourquoi pas. A part le compilateur, on ne connait pas la quantité de RAM installée, la taille du swap, si la mémoire peut être "over-committée" ou pas avec le système d'exploitation utilisé (que l'on ne connait pas non plus), si la cible est du 32-bit ou 64-bit, etc...

Bien sûr, ce serait un énorme gaspillage de mémoire physique et virtuelle mais techniquement, ce n'est pas forcément impossible, pas portable sûrement, mais pas impossible.

[Bktero]

Pourquoi n'aurait-il pas un To de RAM pendant qu'on y est ?

Faut être réaliste des fois, aucun ordinateur personnel ne possèd une telle quantité de RAM. Pour ce qui est des ordinateurs pro, c'est une quantité tellement énorme qu'elle est peu probable. De plus, tu ne mets pas une telle quantité de mémoire sur une machine en te disant "tiens je vais juste faire tourner un programme que je n'ai pas encore fait et qui chargera 60 Go de données en mémoire vive comme un gros bourin alors qu'il y a des méthodes bien moins consommatrices et plus élégantes".

Soyons sérieux.

[jlliagre]

Faut être réaliste des fois, aucun ordinateur personnel ne possèd une telle quantité de RAM.

C'est vrai, mais rien n'indique dans la question qu'il s'agit d'un ordinateur personnel. On prête à Bill Gates la citation qu'aucun ordinateur personnel n'aurait jamais besoin de plus de 640 ko lorsque la norme était 64 ko. Aujourd'hui, on trouve facilement des laptops avec 6 ou 8 Go de RAM, le rapport est exactement le même.

Pour ce qui est des ordinateurs pro, c'est une quantité tellement énorme qu'elle est peu probable.

Je suis d'accord pour dire qu'il est peu probable qu'ickis69 dispose d'une machine qui permette d'allouer 60 Go. J'ai juste réagi à la réponse "impossible" qui est incorrecte, spécialement dans un forum de professionnels en informatique. 64 Go de RAM n'est pas "énorme", c'est assez banal sur un serveur aujourd'hui. Les serveurs haut de gamme supportent souvent plusieurs To de RAM.
De toute façon, on n'a pas besoin de 60 Go de RAM pour s'allouer 60 Go de mémoire (virtuelle) et il est vraisemblable que le fichier de 800 Mo n'occupera qu'une faible partie des pages mémoire.

De plus, tu ne mets pas une telle quantité de mémoire sur une machine en te disant "tiens je vais juste faire tourner un programme que je n'ai pas encore fait et qui chargera 60 Go de données en mémoire vive comme un gros bourin

je me répète, il y a peu de risque que 60 Go de RAM soient nécessaires pour charger ces données.

alors qu'il y a des méthodes bien moins consommatrices et plus élégantes".

Sur ce dernier point, tout à fait d'accord. C'est d'ailleurs ce que j'ai aussi écrit.

[diogene]

J'ai juste réagi à la réponse "impossible" qui est incorrecte, spécialement dans un forum de professionnels en informatique.

Moi, j'ai juste répondu à la question posée. Peu importe au PO qu'il existe des configurations qui permettent de le faire, pour lui ce n'est pas possible. Et il le dit dès son premier message :

A la compilation -> size of array is too large :-(

Fin de la polémique.

[jlliagre]

Ce message d'erreur ne signifie pas forcément que c'est impossible.
Peut-être que le PO compile en 32 bits alors que 64 bits est bien sûr un prérequis pour une telle taille, peut-être qu'il alloue son tableau dans la pile et pas dans le heap, ...

[souviron34]

Ce message d'erreur ne signifie pas forcément que c'est impossible.

Nous sommes bien d'accord, mais nous sommes dans le sous-forum "Débutez"

Et au vu du PO et de "l'idée" d'origine, c'est bien une idée a priori de débutant. Point.


(j'avais d'ailleurs dit "sur la plupart des machines", ce qui laissait une marge si on le souhaitait )

[jlliagre]

L'idée d'utiliser un tableau beaucoup plus grand que ce que ne permet en théorie le matériel est sans doute celle d'un débutant mais sa mise en œuvre n'est pas nécessairement absurde ou impossible.

C'est un type de programmation que l'on peut rencontrer dans des applications scientifiques, de bases de données et dans le domaine de la virtualisation.

Voici un programme qui démontre la faisabilité de la solution sur mon laptop sous Gnu/Linux et qui dispose de 4 Go de RAM et 1 Go de swap.

Il déclare un tableau statique de "60 Go", le remplit avec des longueur de ligne et nombre de paragraphes aléatoires et stoppe quand le tableau contient environ 1 Go de données (un peu plus donc que les 800 Mo anticipés).

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
#include <stdio.h>
#include <stdlib.h>
#include <sys/types.h>
#include <unistd.h>
 
char tableau[300000][200][1000];
 
#define rnd(max) (rand()%max)
 
main()
{
  char c=0;
  int i,j,k;
  int maxi,maxj,maxk;
  long size=0;
  long max=1000000000;
  srand(time(NULL));
  for(i=0;i<300000;i++)
  {
    maxj=rnd(200);
    for(j=0;j<maxj;j++)
    {
      maxk=rnd(1000);
      for(k=0;k<maxk;k++)
      {
        tableau[i][j][k]=c++;
        size++;
      }
    }
    if(size>max)
      break;
  }
  printf("[%d] %ld\n",i,size);
  system("set -x;free");
}

La compilation en 32 bit provoque la même erreur que celle observée par ickis69

Code :

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

1
2
# gcc -m32 a.c -o a
a.c:6: error: size of array 'tableau' is too large

En 64-bit, pas d'erreur à la compilation.

Code :

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

# gcc -m64 a.c -o a

En mode d'overcommiting par défaut, le programme sort en erreur au démarrage:

Code :

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

1
2
# ./a
Killed

En activant l'overcommiting sans limite, le programme fonctionne correctement:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
# echo 1 > /proc/sys/vm/overcommit_memory
# ./a
[20026] 1000019094
+ free
             total       used       free     shared    buffers     cached
Mem:       3989296    2601708    1387588          0       4096      76596
-/+ buffers/cache:    2521016    1468280
Swap:      1052220     519924     532296
# free
             total       used       free     shared    buffers     cached
Mem:       3989296     579384    3409912          0       4280      79832
-/+ buffers/cache:     495272    3494024
Swap:      1052220     518412     533808

La commande top montre bien que le processus s'est alloué 55,9 Go de mémoire dès le démarrage du programme:

Code :

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

1
2
3
4
5
6
7
8
top - 22:12:50 up  1:12,  3 users,  load average: 2.52, 2.70, 1.24
Tasks: 193 total,   3 running, 190 sleeping,   0 stopped,   0 zombie
Cpu(s): 19.6%us,  6.9%sy,  0.0%ni, 72.8%id,  0.6%wa,  0.0%hi,  0.0%si,  0.0%st
Mem:   3989296k total,  1118844k used,  2870452k free,     4088k buffers
Swap:  1052220k total,   520000k used,   532220k free,    76392k cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
 5070 root      20   0 55.9g 535m  340 R   47 13.7   0:01.45 a

En fin d'exécution, on voit une augmentation significative de l'utilisation de la RAM, mais rien de délirant et rien qui n'impacte les performances car il n'y a pas de pagination (l'utilisation du swap n'a pas augmenté).

Code :

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

1
2
3
4
5
6
7
8
top - 22:12:53 up  1:12,  3 users,  load average: 2.40, 2.67, 1.24
Tasks: 193 total,   2 running, 191 sleeping,   0 stopped,   0 zombie
Cpu(s): 37.5%us, 12.9%sy,  0.0%ni, 48.6%id,  0.2%wa,  0.0%hi,  0.8%si,  0.0%st
Mem:   3989296k total,  2291428k used,  1697868k free,     4088k buffers
Swap:  1052220k total,   519980k used,   532240k free,    76492k cached

  PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
 5070 root      20   0 55.9g 1.6g  340 R   99 43.0   0:04.50 a

En conclusion, sur un PC standard, avec certes un tuning spécifique, il ne m'a fallu que 2,03 Go de RAM pour gérer un tableau de 56 Go contenant 953 Mo de données effectives, ce qui donne un overhead de 112% environ comparé à celui de 30% calculé par diogène avec des pointeurs de 32-bit, et donc de 60% avec des pointeurs de 64-bit.

C'est certes moins optimisé mais un code beaucoup plus simple et aussi à priori plus performant (car moins d'indirections).