C++

intérêt de boost::multi_array ?

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : intérêt de boost::multi_array ?

boulgakov

Bonjour,

J'ai tout un tas de données qui se stockent dans des tableaux pleins à plusieurs dimensions (disons par exemple : un prix qui dépend du pas de temps, du client, du fournisseur, du produit et du pays).

Solution C :

Code :

double *****prix

Beurk. En outre il faut allouer et détruire, j'ai une vingtaine de types de données du même genre : impossible.

Solution STL :

Code :

vector<vector<vector<vector<vector<double> > > > prix

Re-beurk. Allocation à peine plus chouette qu'en C.

Je précise qu'il y a plusieurs types de données différentes, certaines entières d'autres réelles, et pouvant dépendre de 0 à 5 dimensions. Mon exemple du prix ci-dessus correspond au "pire" cas.

Solution Boost :

Code :

multi_array<double,5> prix

Bien ! Problème : j'ai fait quelques tests sous VC++ 2005 (toutes optimisations à fond, "checked iterators" désactivés). Je fait des boucles pour stocker et lire 10^8 fois soit a) un rand() b) une constante.

* Résultats sur les rand() :

En 1 dimension (10 éléments), STL ~ Boost.
En 2 dimensions (10*10 = 100 éléments), Boost 2 fois plus lent que STL. :heink:

* Résultats sur 1 constante :

En 1 dimension, Boost 2 fois plus lent que la STL. Là OK, un conteneur multi-dimensions n'est pas forcément super adapté pour un tableau simple.
En 2 dimensions, Boost 8 fois plus lent que la STL :ouch: :ouch: Bon, si je teste avec 2*10^6 éléments, l'écart se ressert (Boost 3 fois plus lent) mais bof quoi.

Donc je ne comprends pas. boost::multi_array me semblait justement fait pour moi : données dont je connais a priori le nombre de dimensions mais pas la taille de chaque dimension + pas envie d'écrire des horreurs comme vector<vector<vector<... Quel est l'intérêt s'il m'explose mon temps de calcul ? Je ne suis pas en train de me défouler dessus, hein, je voudrais vraiment savoir à quoi sert cette librairie, j'ai sûrement raté quelque chose. En plus je peux écrire :

Code :

template<class T> struct Types
{
typedef vector<vector<vector<vector<vector<T> > > > tab5Dim;
};

et garder les perfs de la STL + une syntaxe relativement concise.

Message édité par boulgakov le 14-04-2007 à 17:26:16

Publicité

0x90

→

Spa forcément la meilleure solution, mais pour te réduire l'écriture d'empilement de vecteurs tu peut faire ça :

Code :

#include <vector>
#include <iostream>
 
/* Template de base */
template <typename T, int depth>
class metavector : public std::vector<metavector<T, depth-1> > {};
/* Specialisation partielle pour le dernier tableau */
template <typename T>
class metavector<T, 1> : public std::vector<T> {};
 
int main(void) {
/* Tadam ! */
metavector<double, 4> bidule;
bidule.resize(1);
bidule[0].resize(1);
bidule[0][0].resize(1);
bidule[0][0][0].resize(1);
bidule[0][0][0][0] = 42.1337;
std::cout << bidule[0][0][0][0] << std::endl;
}

Evidemment faut voir si ton compilo supporte bien la spécialisation partielle, j'utilise que gcc ici, je peut pas test
Après peut-être que les valarray peuvent t'aider aussi...

Message cité 1 fois
Message édité par 0x90 le 14-04-2007 à 18:29:09

---------------
Me: Django Localization, Yogo Puzzle, Chrome Grapher, C++ Signals, Brainf*ck.

el muchacho

Comfortably Numb

Et en quoi le couple classe + conteneur classique serait inapproprié au problème ?

Message cité 1 fois

boulgakov

el muchacho a écrit :

Et en quoi le couple classe + conteneur classique serait inapproprié au problème ?

Ce ne serait pas inapproprié à strictement parler, mais je trouverais quand même assez bizarre d'ajouter une classe à mon code qui encapsulerait juste un tableau multidimensionnel. Si les dimensions n'étaient connues qu'à l'exécution, je ne dis pas (je l'ai déjà fait), mais là... Ajouter des conteneurs propriétaires qui n'encapsulent que l'existant me paraît à éviter. Je n'aime pas trop tomber sur des codes où les gens ont commencé par redéfinir des class Queue et des Pile, par exemple.

0x90 a écrit :

Spa forcément la meilleure solution, mais pour te réduire l'écriture d'empilement de vecteurs tu peut faire ça :

[...]

Evidemment faut voir si ton compilo supporte bien la spécialisation partielle, j'utilise que gcc ici, je peut pas test
Après peut-être que les valarray peuvent t'aider aussi...

Pas mal du tout. Je n'ai jamais écrit de templates récursifs, je ne risquais pas de trouver ça tout seul. Ta solution m'évite aussi de définir les N types avec des noms comme 'tabNDims', 'tab(N-1)Dims', etc..., ce qui aurait été très moche. Merci !

Sinon, j'ai réfléchi et faut avouer qu'il y a quelques trucs pas mal dans boost::multi_array. Genre, on peut définir des vues sur un tableau. Par exemple "vue à 2 dimensions, où les indices 2,3 et 4 de mon tableau X à 5 dimensions sont fixés et où je ne prends que les éléments d'indices pairs sur la 5ème dimension" : comme les itérateurs sont définis sur les vues, c'est compatible avec les algos de la STL et je peux très bien trier ces éléments par ordre croissants en une ligne avec un std:sort, etc etc... Bref, l'intérêt est plutôt de se conformer au modèle de programmation générique de la STL, ce qui ne m'intéresse pas dans le cas présent.

Message cité 1 fois

el muchacho

Comfortably Numb

boulgakov a écrit :

Non, ce que je dis, c'est qu'à première vue, si on prend ton exemple de tuple hétérogène (un prix qui dépend du pas de temps, du client, du fournisseur, du produit et du pays), on peut/doit faire une classe de ça. Et on met les objects instanciés dans un conteneur standard.

Message cité 1 fois

boulgakov

el muchacho a écrit :

Euh... bah non. J'ai pas dû être clair. C'est un code numérique, hein, j'ai un peu instancié pour que ça parle aux gens mais mon temps, mes clients,... ce sont juste des indices entiers. Pourquoi je créerais une classe ?

Code :

class Prix {
private :
metavector<double, 5> valeurs;
public :
getPrix(const unsigned int client, const unsigned int fournisseur, ...)
{
return valeurs[client][fournisseur]...;
}
};

Pas super utile, voire même nuisible.

el muchacho

Comfortably Numb

Mais non. C'est du n'importe quoi, là.

Ce à quoi je pensais, c'était plutôt qq chose comme:

Code :

class truc {
int client, fournisseur, produit, pays;
}
vector<pair<int prix, truc maStruc> >

par exemple.

Mais si ça se trouve, ça n'est pas ce que tu veux faire. Tu veux p-ê faire des recherches sur d'autres colonnes ? Pour l'instant, tout ce que je vois, c'est un problème extrêmement mal modélisé, l'équivalent d'une base de données avec toutes les données en bordel dans une seule table, et donc une solution qui ne marchera probablement pas avec un nombre conséquent de données.
Mais comme tu n'es pas disert sur ce que tu veux réellement faire, on ne peut pas vraiment aider, on ne peut que faire des supputations.

Message édité par el muchacho le 15-04-2007 à 13:01:55

Taz

bisounours-codeur

On peut avoir ton code de benchmark ?

Message cité 1 fois

boulgakov

Taz a écrit :

On peut avoir ton code de benchmark ?

Ouaip, avec plaisir, si ça se trouve je tire les mauvaises conclusions du mauvais test. J'ai la flemme de mettre au propre, par contre. Le test 1 dim et le test 2 dims se suivent dans le main(). En 2 dimensions, je sais que t'attaque toujours la diagonale de la matrice ce qui pourrait être un biais, mais j'ai fait quelques variantes et cela ne change rien.

Code :

#include <iostream>
#include <ctime>
#include <vector>
#include <exception>
#include <algorithm>
#include <cstdlib>
#include "boost/multi_array.hpp"
using namespace boost;
using namespace std;
const unsigned int NB_TESTS = 10;
const long unsigned int NB_ITERATIONS = 10000000;
const unsigned int LONGUEUR = 10;
double recipient = 0.0;
// Test 1 dim
template<typename T> double test(T &tableau)
{
long unsigned int i = 0;
unsigned int indiceTab = 0;
time_t time1 = clock();
for ( i = 0; i < NB_ITERATIONS; i++ )
{
indiceTab = i % LONGUEUR;
tableau[indiceTab] = 10.0; // Ecriture
recipient = tableau[indiceTab]; // Lecture
}
time_t time2 = clock();
return (time2 - time1) / 1000.0;
}
// Test 2 dim
template<typename T> double test2(T &tableau)
{
long unsigned int i = 0;
unsigned int indiceTab = 0;
time_t time1 = clock();
for ( i = 0; i < NB_ITERATIONS; i++ )
{
indiceTab = i % LONGUEUR;
tableau[indiceTab][indiceTab] = 10.0; // Ecriture
recipient = tableau[indiceTab][indiceTab]; // Lecture
}
time_t time2 = clock();
return (time2 - time1) / 1000.0;
}
int main()
{
try
{
srand( (unsigned)time( NULL ) );
cout << " *** Tests 1 Dimension " << endl << endl;
vector<vector<double>> resultats(3);
multi_array<double, 1> tabBoost(extents[LONGUEUR]);
vector<double> tabSTL(LONGUEUR);
double *tabC = new double[LONGUEUR];
for (unsigned int iTest = 0; iTest < NB_TESTS; iTest++ )
{
double resSTL = test(tabSTL);
double resC = test(tabC);
double resBoost = test(tabBoost);
resultats[0].push_back(resSTL);
resultats[1].push_back(resC);
resultats[2].push_back(resBoost);
cout << "STL : " << resSTL << " s." << endl;
cout << "C : " << resC << " s." << endl;
cout << "multiarray : " << resBoost << " s." << endl;
cout << endl;
}
delete [] tabC;
cout << "Moyenne STL : " << accumulate(resultats[0].begin(), resultats[0].end(), 0.0) / NB_TESTS << endl;
cout << "Moyenne C : " << accumulate(resultats[1].begin(), resultats[1].end(), 0.0) / NB_TESTS << endl;
cout << "Moyenne Boost : " << accumulate(resultats[2].begin(), resultats[2].end(), 0.0) / NB_TESTS << endl;
cout << endl << " *** Tests 2 Dimensions " << endl;
vector<vector<double> > resultats2(3);
multi_array<double, 2> tabBoost2(extents[LONGUEUR][LONGUEUR]);
vector<vector<double> > tabSTL2(LONGUEUR, vector<double>(LONGUEUR));
double **tabC2 = new double *[LONGUEUR];
for ( unsigned int l = 0; l < LONGUEUR; l++ )
{
tabC2[l] = new double[LONGUEUR];
}
for (unsigned int iTest2 = 0; iTest2 < NB_TESTS; iTest2++ )
{
double resSTL2 = test2(tabSTL2);
double resC2 = test2(tabC2);
double resBoost2 = test2(tabBoost2);
resultats2[0].push_back(resSTL2);
resultats2[1].push_back(resC2);
resultats2[2].push_back(resBoost2);
cout << "STL : " << resSTL2 << " s." << endl;
cout << "C : " << resC2 << " s." << endl;
cout << "multiarray : " << resBoost2 << " s." << endl;
cout << endl;
}
cout << "Moyenne STL : " << accumulate(resultats2[0].begin(), resultats2[0].end(), 0.0) / NB_TESTS << endl;
cout << "Moyenne C : " << accumulate(resultats2[1].begin(), resultats2[1].end(), 0.0) / NB_TESTS << endl;
cout << "Moyenne Boost : " << accumulate(resultats2[2].begin(), resultats2[2].end(), 0.0) / NB_TESTS << endl;
for ( unsigned int l = 0; l < LONGUEUR; l++ )
{
delete [] tabC2[l];
}
delete [] tabC2;
}
catch(exception &e)
{
cout << e.what() << endl;
}
}

Edit - Les résultats sur les 2 dimensions :

**
Moyenne STL : 0.0972
Moyenne C : 0.0828
Moyenne Boost : 1.0731
**

Message édité par boulgakov le 15-04-2007 à 13:53:26

Taz

bisounours-codeur

Code :

#include <iostream>
#include <ctime>
#include <vector>
#include <exception>
#include <algorithm>
#include <cstdlib>
#include <boost/multi_array.hpp>
#include <boost/timer.hpp>
using namespace boost;
using namespace std;
const unsigned int NB_TESTS = 100;
const long unsigned int NB_ITERATIONS = 10000000;
const unsigned int LONGUEUR = 10;
template<typename Array>
double do_test(Array &a, double (&f)(Array &a))
{
timer t;
for (unsigned i = 0; i != NB_TESTS; ++i)
f(a);
return t.elapsed();
}
// Test 1 dim
template<typename T> double test(T &tableau)
{
timer t;
long unsigned int i = 0;
unsigned int indiceTab = 0;
for ( i = 0; i < NB_ITERATIONS; i++ )
{
indiceTab = i % LONGUEUR;
tableau[indiceTab] *= 10.0;
}
return t.elapsed();
}
// Test 2 dim
template<typename T> double test2(T &tableau)
{
timer t;
long unsigned int i = 0;
unsigned int indiceTab = 0;
for ( i = 0; i < NB_ITERATIONS; i++ )
{
indiceTab = i % LONGUEUR;
tableau[indiceTab][indiceTab] *= 10.0;
}
return t.elapsed();
}
int main()
{
try
{
srand( (unsigned)time( NULL ) );
multi_array<double, 1> tabBoost(extents[LONGUEUR]);
vector<double> tabSTL(LONGUEUR);
double *tabC = new double[LONGUEUR];
cout << "[1] STL " << do_test(tabSTL, test) << '\n'
<< "[1] C " << do_test(tabC, test) << '\n'
<< "[1] Boost " << do_test(tabBoost, test) << '\n';
delete [] tabC;
multi_array<double, 2> tabBoost2(extents[LONGUEUR][LONGUEUR]);
vector<vector<double> > tabSTL2(LONGUEUR, vector<double>(LONGUEUR));
double **tabC2 = new double *[LONGUEUR];
for ( unsigned int l = 0; l < LONGUEUR; l++ )
{
tabC2[l] = new double[LONGUEUR];
}
cout << "[2] STL " << do_test(tabSTL2, test2) << '\n'
<< "[2] C " << do_test(tabC2, test2) << '\n'
<< "[2] Boost " << do_test(tabBoost2, test2) << '\n';
for ( unsigned int l = 0; l < LONGUEUR; l++ )
{
delete [] tabC2[l];
}
delete [] tabC2;
}
catch(exception &e)
{
cout << e.what() << endl;
}
}

en nettoyant un peu et en simplifiant :
[1] STL 15.89
[1] C 15.88
[1] Boost 18.51
[2] STL 21.45
[2] C 20.45
[2] Boost 24.43

Message cité 1 fois

Publicité

Taz

bisounours-codeur

et pour la petite histoire, avec une allocation dynamique de tableau (vrai tableau contigüe), ça donne :
[2] STL 21.44
[2] C 20.42
[2] Ca 19.44
[2] Boost 23.51

Taz

bisounours-codeur

petite analyse de l'assembler ppc du code précédent, et plus précisément sur la boucle :

Code :

_Z4testIN5boost11multi_arrayIdLj1ESaIdEEEEdRT_
double test<boost::multi_array<double, 1u, std::allocator<double> > >(boost::multi_array<double, 1u, std::allocator<double> >&
882 .L141:
883 mulhwu 0,9,10
884 srwi 0,0,3
885 mulli 0,0,10
886 subf 0,0,9
887 addi 9,9,1
888 mullw 0,0,8
889 slwi 0,0,3
890 lfdx 0,11,0
891 fmul 0,0,13
892 stfdx 0,11,0
893 bdnz .L141
_Z4testIPdEdRT_
test<double*>(double*& )
1392 .L207:
1393 mulhwu 9,11,0
1394 srwi 9,9,3
1395 mulli 9,9,10
1396 subf 9,9,11
1397 addi 11,11,1
1398 slwi 9,9,3
1399 lfdx 0,29,9
1400 fmul 0,0,13
1401 stfdx 0,29,9
1402 bdnz .L207
_Z4testISt6vectorIdSaIdEEEdRT
double test<std::vector<double, std::allocator<double> > >(std::vector<double, std::allocator<double> >& )
1528 .L219:
1529 mulhwu 9,11,0
1530 srwi 9,9,3
1531 mulli 9,9,10
1532 subf 9,9,11
1533 addi 11,11,1
1534 slwi 9,9,3
1535 lfdx 0,29,9
1536 fmul 0,0,13
1537 stfdx 0,29,9
1538 bdnz .L219
double test2<boost::multi_array<double, 2u, std::allocator<double> > >(boost::multi_array<double, 2u, std::allocator<double> >& )
_Z5test2IN5boost11multi_arrayIdLj2ESaIdEEEEdRT
1669 .L231:
1670 mulhwu 0,10,6
1671 srwi 0,0,3
1672 mulli 9,0,10
1673 subf 0,9,10
1674 addi 10,10,1
1675 mullw 9,0,7
1676 mullw 11,0,5
1677 slwi 9,9,3
1678 slwi 11,11,3
1679 add 9,8,9
1680 lfdx 0,9,11
1681 fmul 0,0,13
1682 stfdx 0,9,11
1683 bdnz .L231
double test2<double (*) [10]>(double (*& ) [10])
_Z5test2IPA10_dEdRT_
1809 .L243:
1810 mulhwu 0,10,8
1811 srwi 0,0,3
1812 mulli 9,0,10
1813 subf 0,9,10
1814 addi 10,10,1
1815 mulli 9,0,80
1816 slwi 11,0,3
1817 add 9,29,9
1818 lfdx 0,11,9
1819 fmul 0,0,13
1820 stfdx 0,11,9
1821 bdnz .L243
double test2<double**>(double**& )
_Z5test2IPPdEdRT_
1947 .L255:
1948 mulhwu 0,8,7
1949 srwi 0,0,3
1950 mulli 9,0,10
1951 subf 0,9,8
1952 addi 8,8,1
1953 slwi 9,0,2
1954 slwi 10,0,3
1955 lwzx 11,9,29
1956 lfdx 0,10,11
1957 fmul 0,0,13
1958 stfdx 0,10,11
1959 bdnz .L255
double test2<std::vector<std::vector<double, std::allocator<double> >, std::allocator<std::vector<double, std::allocator<double> > > > >(std::vector<std::vector<double, std::allocator<double> >, std::allocator<std::vector<double, std::allocator<double> > > >& )
_Z5test2ISt6vectorIS0_IdSaIdEESaIS2_EEEdRT_
2086 mulhwu 0,8,7
2087 srwi 0,0,3
2088 mulli 9,0,10
2089 subf 0,9,8
2090 addi 8,8,1
2091 mulli 9,0,12
2092 slwi 10,0,3
2093 lwzx 11,9,29
2094 lfdx 0,10,11
2095 fmul 0,0,13
2096 stfdx 0,10,11
2097 bdnz .L267

On constate que les codes sont extrêment voisins quand ils ne sont pas rigoureusement identiques. La seule différence est sur le calcul d'index : tantôt des shift quand c'est possible, tantôt des multiplication.

Dans le test a 2D, cette différence slwi/mulli est la seule entre les méthodes STL et et C. La différence de vitesse de cette instruction se sent sur 10**8 exécutions.

Pour moi la différence est faible, le plus lent l'étant de 20% par rapport au plus rapide.

boulgakov

Taz a écrit :

en nettoyant un peu et en simplifiant :
[1] STL 15.89
[1] C 15.88
[1] Boost 18.51
[2] STL 21.45
[2] C 20.45
[2] Boost 24.43

J'ai dû instancier explicitement les fonctions pour que VC++ avale ton code

Code :

do_test(tabSTL, test<vector<double>> )
etc etc

et j'obtiens :

[1] STL 9.985
[1] C 68.796 :heink: (Là, j'ai relancé plusieurs fois et même installé le "Service Pack" en désespoir de cause mais rien n'y fait)
[1] Boost 17.375
[2] STL 11.515
[2] C 10.235
[2] Boost 43.515

Conclusion 1 : mon problème vient du compilo, pas de multi_array. Conclusion 2 : j'ai tous les éléments et je n'ai plus qu'à prendre une option, on verra ça plus tard. Il fait quand même un poil beau dehors, je vais pas passer mon WE là-dessus.

Merci bcp !

FORUM HardWare.fr

Programmation

C++

intérêt de boost::multi_array ?

Sujets relatifs
[résolu][boost::thread] thread à partir d'une fonction à argument?	Requête multi let join
Multi Requete Ajax	PHP 4/5 -> Array (pas de liste ?) [Résolu]
Double tri dans un Array pour un classement	[VBA pour Excel] Multi Filtre
index multi champ vs index simple champ	Aucun intérêt...
Boost::Spirit	WebBrowser en MTA (Multi Threaded apartment)
Plus de sujets relatifs à : intérêt de boost::multi_array ?

Page générée en 0.166 secondes