Discussion :

[souviron34]

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

Plus simple et performant que quoi ??

Quand je lis :

Code :

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

       tableau[i][j][k]=c++;

je compte 3 * (1 multiplication + 1 addition) pour calculer une adresse... Alors qu'en utilsant 1 pointeur on a une addtion.

Quand on mulptiplie par 60G, ça fat une sacrée différence en performance...

[jlliagre]

Plus simple et performant que quoi ??

Je ne parlais pas de mon code d'exemple qui n'avait pour but que de démontrer qu'il n'est pas forcément nécessaire d'avoir un super-calculateur pour déclarer un tableau de 60 Go. Le principe et la gestion de la mémoire virtuelle par un système d'exploitation sont souvent très mal compris par les débutants (et moins débutants).

J'ai écrit "plus simple et plus performant" pour qualifier en général le code utilisant des tableaux par rapport à du code utilisant des pointeurs de pointeurs de pointeurs,
Le fait de ne pas avoir a gérer les allocations/libérations/réallocations simplifie le développement et permet d'éviter de fait les bugs courants associés (ex: fuites mémoire).

Quand je lis :

Code :

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

       tableau[i][j][k]=c++;

je compte 3 * (1 multiplication + 1 addition) pour calculer une adresse... Alors qu'en utilsant 1 pointeur on a une addtion.

Oui, bien sûr, mon code n'est pas optimisé. On peut faire exactement la même chose dans mon exemple, c'est à dire remplacer:

Code :

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

1
2
3
4
5
  for(k=0;k<maxk;k++)
  {
    tableau[i][j][k]=c++;
    size++;
  }

par:

Code :

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

1
2
3
4
5
6
  char *p=&tableau[i][j];
  for(k=0;k<maxk;k++)
  {
    *p++=c++;
  }
  size+=maxk;

[Bktero]

J'ai trouvé la démonstration intéressante sur le principe, ça m'a permis de découvrir l'overcommiting, de revoir des notions de gestions de la mémoire sous Linux qui accepte d'allouer plus de mémoire qu'il n'en existe, ...

Je dis bien "sur le principe" car après quelques lectures sur le net, j'ai l'impression que la situation que tu as créée ressemble à :
"Hey les mecs ! J'ai construit un couloir de 100m de long pour tester l'étirement de mon élastique.
Par contre, comme l'élastique pète si on l'étire de plus de 5m, on ne l'étirera pas de plus de 3m pour ne pas prendre de risque..."

Parlons du principe d'overcommiter la mémoire. Si j'ai bien compris, tu désactives juste la protection de l'OS servant à contrôler la taille de la mémoire allouée. Ainsi, la quantité de mémoire n'est pas vérifiée et ton programme n'est pas tué au démarrage. Ce n'est qu'une réserve potentielle, puisque la limite réelle est donnée par la RAM et le swap. Tant que la mémoire réellement disponible n'est pas entièrement consommée, il n'y a pas de soucis ; dans le cas contraire, l'OOM killer s'active et tue des programmmes.

http://www.tin.org/bin/man.cgi?section=5&topic=proc --> /proc/sys/vm/overcommit_memory
http://www.win.tue.nl/~aeb/linux/lk/lk-9.html --> 9.6 Overcommit and OOM
http://opsmonkey.blogspot.fr/2007/01...vercommit.html

Parlons maintenant du programme. Tu alloues un espace gigantesque (nécessitant à un adressage sur 64 bits et non 32 bits) sachant pertinemment que tu ne pourras pas l'utiliser. Ça tombe bien que le fichier utilisé soit, pour le coup, seulement de 800 Mo. Si le fichier grossi, cela étant probable puisqu'il y a un pire cas qui n'est pas atteint, alors le programme plantera (d'autres programmes pour être OOM-killed ?).

Si j'ai bien tout compris, tu as fait un programme plus performant qui plantera de façon plus ou moins aléatoire en fonction de la taille du fichier d'entrée et de l'occupation mémoire du système..... Cool.

Au final, je te dis merci de m'avoir montré le principe de l'overcommitting (ce n'est pas ironique hein ! ça m'aura appris des choses ! ) mais qui ne me semble absolument pas être une solution adaptée au problème.

[kwariz]

Salut,

sur ce coup j'ai beaucoup appris aussi. Un de mes collègues me disait que l'on pouvait créer jusqu'à 64GB de swap avec un kernel linux récent. Donc du coup (au détriment des performances) je me dis que l'on pourrait traiter (sans overcommit) jusqu'à "pas loin de" 64GB de données ?
Mais bon, en ce qui me concerne je trouve cette démarche "paresseuse" dans la majorité des cas, cela évite d'avoir à trop se creuser la tête (ou de remettre les solutions imaginées en question) pour trouver un algorithme plus adapté. J'ai souvent entendu des excuses du genre "ce n'est pas ma faute si le hard ne me permet pas de ...". Sans compter que dès que nous posséderons des ordinateurs avec 64GB de RAM on se trouvera face à des problèmes nécessitant 9TB de données ... et rebelote !

Merci pour vos idées et vos liens !

[denispir]

Je pense que la question n'est pas de la quantité absolue de mémoire utilisée dans l'algorithme initial, que ce soient des MO, GO, ou TO. Ca pourrait être des kO la question serait la même, à l'échelle près (mais mon premier programme fut sur un sinclair ZX81 où il y avait très exactement 1kO de mémoire utilisateur, prog et données ! ).

Pour moi le problème est que, apparemment, vue la façon dont est posé le sujet, le traitement ou l'usage des données se fait à l'échelle du paragraphe. Donc, charger plus en mémoire, en permanence et pour rien du tout, aucun gain, aucune raison, c'est d'une façon un crime (Et là, ce n'est pas un fan de l'optimisation qui parle... Mais c'est comme en écologie, à mon avis, la sur-consommation de ressources est à la fois de la nuisance et de la bêtise.)
Si on peut diviser par n la consommation de ressouces, il faut le faire; à moins que le coût en complexité, maintenabilité, plaisir, usabilité, pratique, etc... soit subjectivement plus lourd que le gain en ressources.

Denis

[jlliagre]

J'ai trouvé la démonstration intéressante sur le principe, ça m'a permis de découvrir l'overcommiting, de revoir des notions de gestions de la mémoire sous Linux qui accepte d'allouer plus de mémoire qu'il n'en existe, ...

L'overcommitting n'est pas spécifique à Linux mais existe avec à peu près tous les Unix. De plus, tous les OS classiques (hors exceptions exotiques donc) permettent d'allouer plus de mémoire que la mémoire physique.

Je dis bien "sur le principe" car après quelques lectures sur le net, j'ai l'impression que la situation que tu as créée ressemble à :
"Hey les mecs ! J'ai construit un couloir de 100m de long pour rester l'étirement de mon élastique.
Par contre, comme l'élastique pète si on l'étire de plus de 5m, on ne l'étirera pas de plus de 3m pour ne pas prendre de risque..."

Pas tout à fait. L'idée est bien de présenter un couloir de 100 m de long, mais dont on sait n'avoir besoin que de tronçons éparpillés sur les 100m et dont la longeur cumulée ne va pas dépasser quelques mètres.

Parlons du principe d'overcommiter la mémoire. Si j'ai bien compris, tu désactives juste la protection de l'OS servant à contrôler la taille de la mémoire allouée. Ainsi, la quantité de mémoire n'est pas vérifiée et ton programme n'est pas tué au démarrage. Ce n'est qu'une réserve potentielle, puisque la limite réelle est donnée par la RAM et le swap. Tant que la mémoire réellement disponible n'est pas entièrement consommée, il n'y a pas de soucis ; dans le cas contraire, l'OOM killer s'active et tue des programmmes.

C'est exactement cela. Pour être franc, je suis un farouche adversaire du principe de l'OOM killer.
D'ailleurs, je travaille le plus souvent sous Solaris où l'overcommiting est possible mais uniquement au niveau de l'allocation d'un bloc mémoire, pas de manière globale comme avec Linux. Il n'y a donc pas d'OOM killer avec Solaris. Ceci permet d'éviter qu'un processus qui n'a rien demandé se fasse tuer.

Parlons maintenant du programme. Tu alloues un espace gigantesque (nécessitant à un adressage sur 64 bits et non 32 bits) sachant pertinemment que tu ne pourras pas l'utiliser. Ça tombe bien que le fichier utilisé soit, pour le coup, seulement de 800 Mo.

Je n'alloue rien en fait, je déclare juste un tableau d'une taille gigantesque. La question initiale avait défini des limites en terme de paragraphes, lignes et caractères. Comme j'ai configuré l'OS pour overcommiter la mémoire je n'alloue (et ne réserve) rien du tout. C'est lors de l'écriture des données que quelques zones éparses du tableau gigantesque vont correspondre à de la "vraie" mémoire virtuelle.

Si le fichier grossi, cela étant probable puisqu'il y a un pire cas qui n'est pas atteint, alors le programme plantera (d'autres programmes pour être OOM-killed ?).

La question initiale ne dit pas que le fichier va grossir mais qu'il a une taille de 800 Mo, donc je ne m'inquiète pas trop car j'ai 4 Go de mémoire virtuelle disponible.
Bien sûr, rien ne m'empèche d'ajouter du swap pour être sûr que la totalité du tableau tiendra en mémoire virtuelle. Dans ce dernier cas, la version avec des pointeurs est (légèrement) moins optimisée en terme d'utilisation mémoire que le tableau, puisqu'en plus des données, il faudra aussi gérer les pointeurs vers les lignes et les paragraphes.

Si j'ai bien tout compris, tu as fait un programme plus performant qui plantera de façon plus ou moins aléatoire en fonction de la taille du fichier d'entrée et de l'occupation mémoire du système..... Cool.

Non, il suffit juste d'avoir un swap correctement dimensionné pour éviter les plantages. L'espace disque est beaucoup moins cher que la RAM. Rien n'interdit d'avoir 60 Go de swap.

Au final, je te dis merci de m'avoir montré le principe de l'overcommitting (ce n'est pas ironique hein ! ça m'aura appris des choses ! ) mais qui ne me semble absolument pas être une solution adaptée au problème.

Il s'agit d'un solution adaptée au problème décrit, qui est de mettre 800 Mo de données dans une tableau de 60 Go et envisageable avec un PC de base. C'est aussi une occasion d'utiliser l'overcommitment mais ce dernier n'est absolument pas un prérequis. Il suffit juste d'avoir suffisamment de swap (disque).

[jlliagre]

la sur-consommation de ressources est à la fois de la nuisance et de la bêtise.

La mémoire virtuelle est une ressource gratuite et "illimitée" dans le cas de l'overcommiting. Il ne peut y avoir de sur-consommation dans ce cas.

Sans overcommitting, il suffit d'avoir de l'espace disque pour assurer les réservations, mais le prix du Go de disque est environ 100 fois inférieur aux prix de la RAM donc là aussi, le gaspillage est limité.

Comme je l'ai montré, il y a quand même une surconsommation de RAM dans mon exemple, mais elle est due à l'inadéquation de longueurs de lignes variables avec une taille de pages fixe. Si le problème avait porté sur des blocs de donnée de taille égale ou multiple à la taille de page, il n'y aurait eu aucun gaspillage de RAM non plus.

[jlliagre]

Un de mes collègues me disait que l'on pouvait créer jusqu'à 64GB de swap avec un kernel linux récent.

Avec un noyau 64 bit, on peut installer au moins 512 Go de RAM et la taille du swap est "illimitée" (quelque chose comme 2048 To).

Donc du coup (au détriment des performances) je me dis que l'on pourrait traiter (sans overcommit) jusqu'à "pas loin de" 64GB de données ?

Bien plus que 64 Gigas en fait.

Mais bon, en ce qui me concerne je trouve cette démarche "paresseuse" dans la majorité des cas, cela évite d'avoir à trop se creuser la tête (ou de remettre les solutions imaginées en question) pour trouver un algorithme plus adapté.

Il existe sans doûte des cas de figure où un tableau gigantesque est la solution la plus adaptée comparé à une foultitude de malloc/realloc/memcpy/free.
Le programme le plus efficace n'est pas forcément celui qui a demandé le plus d'effort à écrire et deboguer.

[kwariz]

Avec un noyau 64 bit, on peut installer au moins 512 Go de RAM et la taille du swap est "illimitée" (quelque chose comme 2048 To).

Bien plus que 64 Gigas en fait.

Bonne nouvelle ? Certainement

Il existe sans doûte des cas de figure où un tableau gigantesque est la solution la plus adaptée comparé à une foultitude de malloc/realloc/memcpy/free.
Le programme le plus efficace n'est pas forcément celui qui a demandé le plus d'effort à écrire et deboguer.

Personnellement ça me fait penser aux assertions par défaut de beaucoup de programmeurs comme la bande passante est infinie, ça rame aujourd'hui mais demain tu auras un nouveau pc plus puissant, un réseau ça n'a pas de latence et jamais de coupures, je suis le seul à bosser sur le serveur, c'est vrai que c'est petit mais les users ont un écran 48 pouces non ? ...
C'est plus cette attitude que je reproche, je ne cherche certainement pas à retourner aux "640kb qui a besoin de plus ?"
Que ce soit en informatique ou ailleurs c'est toujours pareil, si on a des ressources à utiliser qui ne le sont pas encore on finit toujours par les utiliser même si on en a pas besoin.
Je trouve que ce genre d'exercice ne reste que ça : un exercice. Je ne vois pas comment une telle solution pourrait être appliquée en entreprise par exemple, ou avec tellement de précautions que ça devient rentable de chercher une solution alternative plus robiste. Pour autant, j'apprécie de genre de connaissances, celles que je catégorise dans "c'est faisable".

[souviron34]

Le programme le plus efficace n'est pas forcément celui qui a demandé le plus d'effort à écrire et deboguer.

Certes, mais il n'est pas en général celui qui a demandé le moins de temps de réflexion pour cerner le problème

C'est ce que je mentionnais par "post de débutant". Ce n'était pas une critique du niveau, mais de l'approche..

Comme l'a mentionné denispir , il est toujours préférable - et souhaitable - de prendre une tapette pour écraser une mouche plutôt quun bulldozer, même si le bulldozer rentre dans ton jardin et fait le boulot..

D'abord parce que tu peux déménager et avoir un jardin plus petit, et parce que c'est du gaspillage..

Dans ma (maintenant longue) carrière, je n'ai pas vu de problèmes - sauf 1 cas très spécifique de physique (le problème à N corps : collisions de galaxies et modélisation d' une atmosphère)) qui nécessiterait d'avoir des TO de mémoire parce que N millions/milliards d'objets interagissent. Il y a dans 99.9999999% du temps une réflexion qui amène au fait que le problème est soit découpable, soit récursif, c'est à dire d'échelle.

Or la base des maths et de la physique (et de l'informatique) est que ce qui est simple est beau et élégant, et ce qui est simple à de bonnes chances d'être correct..

"ce qui se conçoit bien s'énonce clairement et les mots pour le dire viennent aisément"

[jlliagre]

Je ne vois pas comment une telle solution pourrait être appliquée en entreprise par exemple, ou avec tellement de précautions que ça devient rentable de chercher une solution alternative plus robuste.

C'est justement en entreprise que ce type de solution a gros succès ces dernières années. La plupart des logiciels de virtualisation offrent la possibilité d'overcommiter la mémoire.

Il existe une technique très similaire pour l'espace disque qui consiste à utiliser des "sparse files" dans les sytèmes de fichier, ou, sur les baies de stockage, le "thin provisioning".

Dans les deux cas, il ne s'agit pas là d'un gaspillage de ressource mais bien au contraire d'une économie de ressources physiques.

La robustesse n'est pas en cause. D'autres approches qu'un "stupide" oom killer sont mises en oeuvre pour gérer les dépassements de capacité.

[kwariz]

C'est justement en entreprise que ce type de solution a gros succès ces dernières années. La plupart des logiciels de virtualisation offrent la possibilité d'overcommiter la mémoire.

Je ne parlais pas de l'overcommiting, je parlais d'implémenter une solution qui peut en plus d'être susceptible de monopoliser toutes les ressources peut en plus ne aboutir sachant qu'il existe une alternative non seulement plus économe mais plus robuste qui nécessitera tout compte fait moins de compétences humaines et moins de ressources pour fonctionner au pire mieux.

[souviron34]

C'est justement en entreprise que ce type de solution a gros succès ces dernières années. La plupart des logiciels de virtualisation offrent la possibilité d'overcommiter la mémoire.

ou comment pousser à la sur-consommation

Après on s'étonne...

Cette ligne de réflexion va droit dans le mur... Quelles que soient les limitations, il y en a.. forcément ..

Faire un truc qui utilise des TO pour quelque chose qui, en y réfléchissant proprement, prendrait 1 Mo, c'est une aberration....

ça me fait penser à la popularité des biblothèques de "grands nombres"... Qui, dans 99.999999999999999999999999% des cas, sont totalement inutiles, sauf pour la cryptographie..

[jlliagre]

ou comment pousser à la sur-consommation

C'est exactement le contraire. L'overcommitment de mémoire, de disque ou de CPU tel qu'utilisé dans la virtualisation permet de réduire, en général considérablement, la consommation de ressources.