gros std::vector: Quelle perte de perf ram -> dd ?

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 ?

stxxl ?

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

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 :aie:...

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 :mrgreen: ... :aie:
Chaque élément ayant bien entendu plusieurs champs.
Certains fichiers en entrée font 260 go :yaisse2:

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 :aie:

Citation:

---

Envoyé par Benoit_T

Certains fichiers en entrée font 260 go :yaisse2:

---

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

Citation:

---

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. :aie:

Citation:

---

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.

Citation:

---

Envoyé par loufoque

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

Citation:

---

Envoyé par Benoit_T

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

Citation:

---

Envoyé par fcharton

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.

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é... :aie:

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

Cordialement,

J'esayerais ce soir avec VS2008. :king:

Citation:

---

Envoyé par 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é... :aie:

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

Cordialement,

---

Typiquement le genre d'erreur quand il manque un define WINDOWS ou quelque chose de ce goût là. Rien dans la doc ?

Je n'ai pas vraiment réussi à identifier le problème. Cependant, on trouve ce genre de chose :

Code:

---

1 2 3 4 5 6

void ufs_file_base::lock() { #ifdef BOOST_MSVC // not yet implemented #else

---

(ufs_file.cpp/195) :?

En revanche, je réussi à faire aboutir la compilation en rajoutant l'inclusion explicite à windows.h pour toutes les compilations. Pas très propre, mais bon...
make.settings.msvc (ligne 69) :

Code:

---

1 2 3 4

MSVC_COMPILER_OPTIONS = /EHsc /EHs /wd4820 /wd4217 /wd4668 /wd4619 \ /wd4625 /wd4626 /wd4355 /wd4996 -D_SCL_SECURE_NO_DEPRECATE \ /F 16777216 /nologo /FI "windows.h"

---

merci, je vais essayer de nouveau à mon tour.

En incluant le windows.h, ça passe presque, en fait j'ai tout de même des erreurs à la compilation (liées à Boost). Voici la fin du fichier de log de la compilation avec les erreurs:

Citation:

---

cd ..
cd common
nmake /NOLOGO tools
cl -DSORT_OPTIMAL_PREFETCHING -DUSE_MALLOC_LOCK -DCOUNT_WAIT_TIME -I"C:\stxxl-1.2.1"/include -D_FILE_OFFSET_BITS=64 -D_LARGEFILE_SOURCE -D_LARGEFILE64_SOURCE /O2 /MD -D_RTLDLL -DBOOST_LIB_DIAGNOSTIC -DSTXXL_BOOST_TIMESTAMP -DSTXXL_BOOST_CONFIG -DSTXXL_BOOST_FILESYSTEM -DSTXXL_BOOST_THREADS -DSTXXL_BOOST_RANDOM -I"C:\stxxl-1.2.1\boosta" /EHsc /EHs /wd4820 /wd4217 /wd4668 /wd4619 /wd4625 /wd4626 /wd4355 /wd4996 -D_SCL_SECURE_NO_DEPRECATE /F 16777216 /nologo /FI "windows.h" -c stxxl_info.cpp
stxxl_info.cpp
Linking to lib file: libboost_thread-vc90-mt-1_38.lib
Linking to lib file: libboost_date_time-vc90-mt-1_38.lib
Linking to lib file: libboost_filesystem-vc90-mt-1_38.lib
Linking to lib file: libboost_system-vc90-mt-1_38.lib
link stxxl_info.obj /out:stxxl_info.exe /LIBPATH:"C:\stxxl-1.2.1"\lib\ libstxxl.lib /LIBPATH:"C:\stxxl-1.2.1\boosta"\lib\ /STACK:16777216 /NOLOGO
LINK : fatal error LNK1104: impossible d'ouvrir le fichier 'libboost_thread-vc90-mt-1_38.lib'
NMAKE : fatal error U1077: '"C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\link.EXE"'á: code retour '0x450'
Stop.
NMAKE : fatal error U1077: '"C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\nmake.EXE"'á: code retour '0x2'
Stop.
NMAKE : fatal error U1077: '"C:\Program Files\Microsoft Visual Studio 9.0\VC\bin\nmake.EXE"'á: code retour '0x2'
Stop.
Project : error PRJ0019: Un outil a retourné un code d'erreur à partir de "Actions de projet Makefile en cours"

---

A priori un soucis avec les libs de boost... ?

Tu n'as pas ajouté le répertoire de recherche pour les .lib dans ta configuration :
(toujours dans make.settings.msvc ligne 72)

Code:

---

1 2 3

MSVC_LINKER_OPTIONS = /LIBPATH:$(STXXL_ROOT)\lib\ libstxxl.lib \ /LIBPATH:"D:\boost_1_39_0\stage\lib" /STACK:16777216 /NOLOGO

---

Citation:

---

Envoyé par 3DArchi

Tu n'as pas ajouté le répertoire de recherche pour les .lib dans ta configuration :
(toujours dans make.settings.msvc ligne 72)

Code:

---

1 2 3

MSVC_LINKER_OPTIONS = /LIBPATH:$(STXXL_ROOT)\lib\ libstxxl.lib \ /LIBPATH:"D:\boost_1_39_0\stage\lib" /STACK:16777216 /NOLOGO

---

---

Euh si et elles sont bien au bon endroit :aie: Dans le doute je recompile boost avec bjam :?

Citation:

---

impossible d'ouvrir le fichier 'libboost_thread-vc90-mt-1_38.lib'

---

Ca veut dire que le linker ne les a pas trouvées. Donc soit elles n'existent pas soit tu n'as pas fourni le bon répertoire de recherche au linker.

Ayé, j'ai fait quelques tests :D

Bon globalement, ce qui me fait un peu peur, c'est que les auteurs semblent avoir développé la librairie principalement sous Linux sans porter une attention démesurée à Windows...
Entre le build de la librairie un peu casse-tête, les noms de fichier de config inadaptés à Windows, les "not yet implemented" dans le code et surtout la palanquée de warning généré par visual dès qu'on inclus "stxxl.h"... ça ne fait pas très sérieux...

Un petit résumé de la manœuvre pour installer et utiliser STXXL sous Windows:

• checkout du SVN
• ouvrir le fichier make.settings.msvc.
• Compléter les deux lignes STXXL_ROOT et BOOST_ROOT avec le path de STXXL et celui de boost (en absolu)
• Rajouter l'option /FI "windows.h" aux options du compilateur (ligne 70 environ)

Citation:

---

MSVC_COMPILER_OPTIONS = /EHsc /EHs /wd4820 /wd4217 /wd4668 /wd4619 \
/wd4625 /wd4626 /wd4355 /wd4996 -D_SCL_SECURE_NO_DEPRECATE \
/F 16777216 /nologo /FI "windows.h"

---

• Ouvrir la solution stxxl.sln
• Compiler dans le mode par défaut. ("library and tests")

La lib stxxl.lib est générée ! Mais aussi deux fichiers "compiler.options" et "linker.options" qui serviront plus tard.

Pour créer un projet impliquant stxxl :

• Créer son projet visual studio classique.
• Dans le répertoire STXXL_ROOT, ouvrir le fichier "compiler.options" et recopier-le dans les options du projet sous visual : configuration properties->C/C++->Command Line/Additional Option.
• Pareil pour le fichier "linker.options" à recopier dans Linker->Command Line/Additional Option.

Le seul petit problème de cette manœuvre, c'est que les options sont bien adaptées à une compilation en release, par contre je n'ai pas encore réussi à compiler en debug....

Ce n'est pas fini ! Le dernier point : le fichier de conf de stxxl. Par défaut, l'exe qui utilise stxxl a besoin d'un fichier dans le répertoire de démarrage pour configurer l'utilisation des disques durs. Il y a dans le répertoire de STXXL, un fichier template "config_example_win" qui donne un exemple. Le problème c'est que par défaut le fichier de conf doit se nommer ".stxxl"... Sauf que sous Windows il est impossible d'avoir un fichier nommé .qqchose. La solution c'est d'ajouter une variable d'environnement STXXLCFG=nom_du_fichier_de_conf. Par exemple si STXXLCFG="config" alors l'exe cherchera un fichier nommé config.stxxl.

Et pour finir, un petit test de perfo. :king:

L'idée c'est de comparer l'allocation, la génération et le trie d'un vecteur de 1Go de la STXXL(donc passant par le disque dur) à celle d'un vecteur de la STL classique (dans la RAM).

Code:

---

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 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97

#include <time.h> #include <windows.h> struct Chrono { LARGE_INTEGER liStart; LARGE_INTEGER liStop; void Start() { QueryPerformanceCounter(&liStart); } double Stop() { QueryPerformanceCounter(&liStop); LONGLONG llTimeDiff = liStop.QuadPart - liStart.QuadPart; // To get duration in milliseconds LARGE_INTEGER Frequency; QueryPerformanceFrequency(&Frequency); return llTimeDiff * 1000.0 / (double) Frequency.QuadPart; } }; #include <iostream> #include <fstream>   #include "stxxl.h"   // structure pénible, apparemment obligatoire pour stxxl::sort... struct CompInt : public std::less<int> { int min_value() const { return int((std::numeric_limits<int>::min)()); } int max_value() const { return int((std::numeric_limits<int>::max)()); } };   int main() { unsigned long long oneGo = 1024 * 1024 * 1024 / sizeof(int); double timeSTXXLResize; double timeSTXXLGenerate; double timeSTXXLSort; double timeSTLResize; double timeSTLGenerate; double timeSTLSort;   { stxxl::vector<int> vec; Chrono chrono;   chrono.Start(); vec.resize(oneGo); timeSTXXLResize = chrono.Stop();   chrono.Start(); stxxl::generate(vec.begin(), vec.end(), stxxl::random_number32(), 4); timeSTXXLGenerate = chrono.Stop();   unsigned memory_to_use = 128 * 1024 * 1024; chrono.Start(); stxxl::sort(vec.begin(), vec.end(), CompInt(), memory_to_use); timeSTXXLSort = chrono.Stop();   std::cout << "Time STXXL Resize " << timeSTXXLResize << std::endl; std::cout << "Time STXXL Generate " << timeSTXXLGenerate << std::endl; std::cout << "Time STXXL Sort " << timeSTXXLSort << std::endl; std::cout << std::endl; }   { std::vector<int> vec; Chrono chrono;   chrono.Start(); vec.resize(oneGo); timeSTLResize = chrono.Stop();   chrono.Start(); std::generate(vec.begin(), vec.end(), stxxl::random_number32()); timeSTLGenerate = chrono.Stop();   chrono.Start(); std::sort(vec.begin(), vec.end()); timeSTLSort = chrono.Stop(); std::cout << "Time STXXL Resize " << timeSTLResize << std::endl; std::cout << "Time STXXL Generate " << timeSTLGenerate << std::endl; std::cout << "Time STXXL Sort " << timeSTLSort << std::endl; std::cout << std::endl; }   std::cout << "Ratio STXXL / STL Resize " << timeSTXXLResize / timeSTLResize << std::endl; std::cout << "Ratio STXXL / STL Generate " << timeSTXXLGenerate / timeSTLGenerate << std::endl; std::cout << "Ratio STXXL / STL Sort " << timeSTXXLSort / timeSTLSort << std::endl; return 0;

---

Et les résultats...

Citation:

---

[STXXL-MSG] STXXL v1.2.1 + Boost 103800
[STXXL-MSG] 1 disks are allocated, total space: 7000 MB
Time STXXL Resize 0.0977643
Time STXXL Generate 16144.3
Time STXXL Sort 83114.9

Time STXXL Resize 792.068
Time STXXL Generate 548.512
Time STXXL Sort 48236.6

Ratio STXXL / STL Resize 0.000123429
Ratio STXXL / STL Generate 29.4328
Ratio STXXL / STL Sort 1.72307

---

Surprise !!!
Autant les performances du generate sont assez médiocres (comme prévu, x30...), autant le sort est presque aussi rapide que celui effectué entièrement dans la RAM !

Il serait d'ailleurs peut être intéressant de tester sous une distro linux. Je le ferais ce week end je pense, histoire de voir la différence linux/windows.

PS : y'a une erreur dans les mesures, enfin dans le texte qui précéde. Y'a deux fois STXXL

Oups, en effet. :oops:
Un copier-coller raté dans le code. En fait les mesures sont dans l'ordre STXXL/STL/ratio.

Un petite complément d'information:
Pendant toute la manipulation dans le bloc avec STXXL la consommation mémoire est à peu près constante et reste aux alentours de 150mo. Dans la partie STL la consommation mémoire est de 1Go.

Finalement, les performances ne sont pas si mauvaises...

Sinon j'ai identifié mon soucis. Je compilais boost avec gcc g++ du coup je n'ai pas les libs libboost_*****-vc90-mt-1_39.lib mais libboost_*****-mg43-mt-1_39.lib...

Du coup il faut que je compile boost avec Visual-Studio? La lib générée ne posera pas de problème si je l'utilise dans mon appli compilée avec gcc g++ ?

Citation:

---

Envoyé par Benoit_T

Finalement, les performances ne sont pas si mauvaises...

Sinon j'ai identifié mon soucis. Je compilais boost avec gcc g++ du coup je n'ai pas les libs libboost_*****-vc90-mt-1_39.lib mais libboost_*****-mg43-mt-1_39.lib...

Du coup il faut que je compile boost avec Visual-Studio? La lib générée ne posera pas de problème si je l'utilise dans mon appli compilée avec gcc g++ ?

---

Tu as des outils il me semble pour convertir d'un lib vers un autre.
Le mieux est peut être de compiler stxxl avec g++. Il y a un makefile Makefile.gnu qui doit pouvoir convenir modulo quelques modifs bien sûr...

A mon tour j'esaie de compiler stxxl sous VS2005:

Citation:

---

1>boostfd_file.cpp(278) : error C2248: 'boost::iostreams::file_descriptor::open' : cannot access private member declared in class 'boost::iostreams::file_descriptor'
1> C:\SOFT\boost/iostreams/device/file_descriptor.hpp(116) : see declaration of 'boost::iostreams::file_descriptor::open'
1> C:\SOFT\boost/iostreams/device/file_descriptor.hpp(40) : see declaration of 'boost::iostreams::file_descriptor'

---

Ça ne semble pas passer avec boost 1.42.

Si vous avez des expériences positives avec stxxl, je suis preneur :D

EDIT: un peu de svn pour récupérer les dernières source et ça marche.