Discussion :

[Benoit_T]

Bonjour, j'en avais déjà un peu parler dans d'autre topics, je manipule de très gros std::vector dans mon application. Du coup, régulièrement, je dépasse la limite de 2go (ou 3go moyennant bidouillage) en travaillant sur de gros jeux de données.

En 64 bits ça passe (du moins j'imagine, j'ai pas d'OS 64 bits sous la main pour l'instant).

En 32 bits par contre, concernant la taille des jeux de données, je suis vite limité par la quantité de mémoire par processus.

Est-il possible de contourner cette limitation en stockant mon vector sur le disque dur plutôt qu'en ram? Comment faire ? Quelle serait-la perte en terme de performance (énorme? Un facteur 500 ne me surprendrait pas...).

Existe-t-il des librairies qui pourrait m'être utiles ?

[JolyLoic]

stxxl ?

[Invité]

Bonjour,

Il y a deux problèmes distincts :

1- l'adressage : quand tu dépasses, en 32 bits, les 2 Go, toutes sortes de problèmes rigolos apparaissent parce que le système d'exploitation n'est pas fait pour gérer de tels volumes d'espace d'adressage. Il ne s'agit pas d'un problème de vitesse, ou de mémoire, mais de système.

Tu as alors deux solutions : utiliser un système 64 bits, ou réécrire ton code, de façon à ne jamais atteindre ce type de demande mémoire

2- la mémoire : quand tu dépasses la mémoire physique disponible de ta machine, le système doit avoir recours à la mémoire virtuelle, c'est à dire qu'il utilise le disque à la place. Et là c'est beaucoup plus lent... plusieurs ordres de grandeur en fait... (je pense qu'on doit avoir un facteur 1000, peut etre davantage...)

Donc, même si tu résous 1-, tu buteras sur 2-.

En termes de vitesse, la seule solution est de repenser ton programme de façon à ce qu'il utilise moins de mémoire, quitte à avoir des algorithmes plus compliqués (ou alors d'attendre quelques années, de façon à avoir plus de machines en 64 bits, et plus de mémoire par défaut...)

"The practical scientist is trying to solve tomorrow's problem with yesterday's computer; the computer scientist, we think, often has it the other way around". (W. Press, Numerical Recipes)

Francois

[Benoit_T]

En fait je risque de passer sur une station de travail 64 bits (xeon) avec 32 go de ram. Le truc c'est que je ne peux plus grappiller un bit de mémoire sur mes structures de données. Tout est bourrés au max dans des champs de bits. Les variables qui dépassent pas 511 sont codés sur 9 bits, celles qui ne dépassent pas 15 sur 5 bits et ainsi de de suite. Mes booléens sont dans une structure particulières pour qu'il ne soient codés que sur 1 bit et ainsi de suite...

Rien que ce codage a été un casse-tête de combinatoire pour à chaque fois grouper les variables par paquets de 32 bits ...

Dès que je peux décharger sur les disques, je décharge ...

Le truc c'est que je manipule des structures mathématiques d'aucun dirait complexes avec la bagatelle de 800 millions d'éléments ...
Chaque élément ayant bien entendu plusieurs champs.
Certains fichiers en entrée font 260 go

Je vais tout de même jeter un coup d'oeil à stxxl ! Bon si je perd un facteur 1000 l'algo va tourner quelques mois au lieu d'une heure

[Arzar]

Certains fichiers en entrée font 260 go

Bof.
Si l'on en croit la page d'accueil de STXXL

The library is able to handle problems of very large size (up to dozens of terabytes).

Y a de la marge !
(Par contre la dernière mise à jour date du 14 Aout 2008... Je me demande si la librairie est encore maintenue...)

Tu pourrais faire un petit retour si tu testes STXXL ? J'aurais surement le même problème assez prochainement (des fichiers > 4Go) et j'aimerais bien savoir à quel point les perfos en prennent un coup.

[loufoque]

1- l'adressage : quand tu dépasses, en 32 bits, les 2 Go, toutes sortes de problèmes rigolos apparaissent parce que le système d'exploitation n'est pas fait pour gérer de tels volumes d'espace d'adressage. Il ne s'agit pas d'un problème de vitesse, ou de mémoire, mais de système.

Personnellement, mon système d'exploitation me laisse monter jusqu'à 4 GB par processus 32 bits sans problème.

[Invité]

Personnellement, mon système d'exploitation me laisse monter jusqu'à 4 GB par processus 32 bits sans problème.

Ca dépend des systèmes...

Sous Windows (32 bits), au dessus de 2GB, ca se complique singulièrement. D'abord pour des raisons d'architecture (http://msdn.microsoft.com/en-us/library/aa366778.aspx), ensuite pour des raisons plus subtiles, liées à la façon dont certaines fonctions de l'API sont programmées.

Et comme Windows 32 bits représente aujourd'hui le gros du parc informatique installé, je ne parierai pas lourd sur le fonctionnement d'une application utilisant plus de 2 GB de mémoire à un instant donné...

Mais une fois de plus, dans deux ou trois ans, on pourra sans doute compter sur 4GB et plus.

(et là y'a une petite voix dans ma tête qui me dit 640K, déjà vu, déjà vu...)

Francois

[Invité]

Le truc c'est que je ne peux plus grappiller un bit de mémoire sur mes structures de données. Tout est bourrés au max dans des champs de bits. Les variables qui dépassent pas 511 sont codés sur 9 bits, celles qui ne dépassent pas 15 sur 5 bits et ainsi de de suite. Mes booléens sont dans une structure particulières pour qu'il ne soient codés que sur 1 bit et ainsi de suite...

Je ne connais pas tes données, donc je ne peux juger.

Néanmoins, il est rare qu'il n'y ait plus moyen de "chipoter" sur la taille des données. Si les valeurs prises par tes variables ont une distribution non uniforme sur l'ensemble de tes données, ou si elles sont corrélées entre elles, tu peux exploiter ce fait pour les coder de manière plus compacte. Par exemple, un booléen qui prend très rarement la valeur true peut être codé sur nettement moins d'un bit en moyenne (regarde du coté du codage arithmétique), une variable prenant en théorie 256 valeurs, mais statistiquement très souvent faible peut également être compactée, des champs corrélés entre eux (logiquement ou statistiquement) seront généralement mieux représentés ensemble que séparés, etc...

Cela peut représenter un gros gain en espace utilisé (un ordre de grandeur, parfois, si tes données sont "assez peu aléatoires"...) Et si tu utilises déjà des structures qui décodent des données bit à bit, il est même possible que ces méthodes ne ralentissement pas beaucoup ton code (la plupart de ces méthodes de compression reposent sur de l'arithmétique binaire, chose que les machines font généralement vite).

Maintenant, ce genre de chose est difficile à coder, et surtout à tester. A mon avis, il faut mettre le temps de développement en balance avec le cout (en argent et en temps) du passage à un système ayant davantage de mémoire...

Francois

[Benoit_T]

Je ne connais pas tes données, donc je ne peux juger.

Néanmoins, il est rare qu'il n'y ait plus moyen de "chipoter" sur la taille des données. Si les valeurs prises par tes variables ont une distribution non uniforme sur l'ensemble de tes données, ou si elles sont corrélées entre elles, tu peux exploiter ce fait pour les coder de manière plus compacte. Par exemple, un booléen qui prend très rarement la valeur true peut être codé sur nettement moins d'un bit en moyenne (regarde du coté du codage arithmétique), une variable prenant en théorie 256 valeurs, mais statistiquement très souvent faible peut également être compactée, des champs corrélés entre eux (logiquement ou statistiquement) seront généralement mieux représentés ensemble que séparés, etc...

Cela peut représenter un gros gain en espace utilisé (un ordre de grandeur, parfois, si tes données sont "assez peu aléatoires"...) Et si tu utilises déjà des structures qui décodent des données bit à bit, il est même possible que ces méthodes ne ralentissement pas beaucoup ton code (la plupart de ces méthodes de compression reposent sur de l'arithmétique binaire, chose que les machines font généralement vite).

Maintenant, ce genre de chose est difficile à coder, et surtout à tester. A mon avis, il faut mettre le temps de développement en balance avec le cout (en argent et en temps) du passage à un système ayant davantage de mémoire...

Francois

Merci pour ces précisions fort intéressantes. Le problème est que la distributions des valeurs est relativement uniforme dans l'intervalle que prennent les valeurs. Certaines sont effectivement corrélées ce que j'ai déjà exploité. exemple: deux variables u et v codées sur 32 bits mais |v-u|<= 255. Au lieu de stoquer u et v sur 64 bits, je stocke u sur 32 et v-u sur 8 bits.

[Benoit_T]

J'ai essayé de compiler la librairie STXXL avec visual studio express 2008, la compilation ne passe pas il me renvoie 69 erreurs, par exemple identificateur DWORD non déclaré...

Y a-t-il quelqu'un qui a compilé la librairie sans soucis ?

Cordialement,