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,

[Arzar]

J'esayerais ce soir avec VS2008.

[3DArchi]

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,

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

[3DArchi]

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

Code :

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

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 :

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

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"

[Benoit_T]

merci, je vais essayer de nouveau à mon tour.

[Benoit_T]

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:

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... ?

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

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

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

[Benoit_T]

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

Code :

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

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 Dans le doute je recompile boost avec bjam

[3DArchi]

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.

[Arzar]

Ayé, j'ai fait quelques tests

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)

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.

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 :

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

[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 !

[Goten]

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