Hi,
I've got a performance problem during a test I've done with multi_index
on MSVC 6.0 SP 6.
I'm using BOOST 1.32.0 .
The search performance is comparable with several maps, but
insertion is dramatically slow : 5mn 30s for 10 000 employees.
Here is my test code :
===
/* Boost.MultiIndex basic example.
*
* Copyright 2003-2004 Joaquín M López Muñoz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
*
* See http://www.boost.org/libs/multi_index for library home page.
*/
#include "stdafx.h"
#if !defined(NDEBUG)
#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
#endif
#include
#include
#include
#include <algorithm>
#include <iostream>
#include <iterator>
#include <string>
#include <cstdlib>
#include <map>
#include <vector>
#include <ctime>
#include <sstream>
#include <iomanip>
using boost::multi_index_container;
using namespace boost::multi_index;
/* an employee record holds its ID, name and age */
struct employee
{
int m_id;
std::string m_name;
int m_age;
employee(int id_,const std::string& name_,int
age_):m_id(id_),m_name(name_),m_age(age_){}
void set(int id_,const std::string& name_,int age_) { m_id=id_;
m_name=name_; m_age=age_; }
const employee& operator =(const employee& e) { set(e.m_id, e.m_name,
e.m_age); return *this; }
employee(const employee& e) { set(e.m_id, e.m_name, e.m_age); }
int id() const { return m_id; } // impossible d'appeler la fonction
et l'index "id"
const std::string& name() const { return m_name; }
int age() const { return m_age; }
friend std::ostream& operator<<(std::ostream& os,const employee& e)
{
os<,
ordered_non_unique<
tag<name>,BOOST_MULTI_INDEX_MEMBER(employee,std::string,m_name)>,
ordered_non_unique<
tag<age>, BOOST_MULTI_INDEX_MEMBER(employee,int,m_age)> >
employee_set;
template
void print_out_by(
const MultiIndexContainer& s,
Tag* =0 /* fixes a MSVC++ 6.0 bug with implicit template function parms */
)
{
/* obtain a reference to the index tagged by Tag */
const typename
boost::multi_index::index::type& i=
get<Tag>(s);
typedef typename MultiIndexContainer::value_type value_type;
/* dump the elements of the index to cout */
std::copy(i.begin(),i.end(),std::ostream_iterator(std::cout));
}
// Un conteneur qui permet de contenir des employee
// triés sur 3 index.
class EmployeeMapper
{
std::map m_byId;
std::map m_byName;
std::map m_byAge;
typedef std::map::iterator EMIdIt;
typedef std::map::iterator EMNameIt;
typedef std::map::iterator EMAgeIt;
public:
EmployeeMapper() {}
~EmployeeMapper()
{
// Deux lignes pour éviter que ces objets ne contiennent
// des pointeurs invalides pendant la destruction va un
// autre conteneur.
m_byName.clear();
m_byAge.clear();
std::map::iterator it;
while ((it=m_byId.begin()) != m_byId.end())
{
delete it->second;
m_byId.erase(it);
}
}
void add(const employee& e)
{
employee * e2 = NULL;
try
{
e2 = new employee(e);
}
catch(...)
{
delete e2;
throw;
}
m_byId[e2->id()] = e2;
m_byName[e2->name()] = e2;
m_byAge[e2->age()] = e2;
}
employee* byId(int id)
{
EMIdIt it = m_byId.find(id);
if (it == m_byId.end())
return NULL;
else
return it->second;
}
employee* byName(const std::string& name)
{
EMNameIt it = m_byName.find(name);
if (it == m_byName.end())
return NULL;
else
return it->second;
}
employee* byAge(int age)
{
EMAgeIt it = m_byAge.find(age);
if (it == m_byAge.end())
return NULL;
else
return it->second;
}
private:
// fonctions inhibées
EmployeeMapper(const EmployeeMapper&);
const EmployeeMapper& operator=(const EmployeeMapper&);
};
// Retourne un entier tq : 0 <= entier < maximum
int alea(int maximum)
{
return int(std::min(maximum, RAND_MAX) * rand() / (RAND_MAX + 1.0));
}
int main()
{
// Init aléatoire
srand( (unsigned)time( NULL ) );
employee_set es;
EmployeeMapper em;
const int tailleEnsemble = 10000;
const int tailleEchantillon = 10;
const int moduloEchantillon = tailleEnsemble / tailleEchantillon;
const int nbRecherches = 10000;
std::vectorstd::string noms;
noms.push_back("Alphonse");
noms.push_back("Éléonore");
noms.push_back("Gaston");
noms.push_back("Séverine");
noms.push_back("Zorglub");
std::vector<employee> jeuDeDepart;
std::vector<employee> jeuARechercher;
int i=0;
for (i=0; i < tailleEnsemble; ++i)
{
std::ostringstream os;
// Construction d'un nom unique avec un caractère aléatoire
// Cela reflète le type de données gérées en réalité.
// L'ajout de i implique l'unicité.
os << noms[alea(5)] << std::setw(5) << std::setfill('0') << alea(30000)
<< std::setw(5) << std::setfill('0') << i;
employee e(i, // index numérique unique
os.str(), // nom, chaîne unique
alea(100)); // valeur potentiellement dupliquée
jeuDeDepart.push_back(e);
// On conserve un échantillon à rechercher plus tard
if (0 == i % moduloEchantillon)
{
//employee_set::iterator it=get<id>(es).find(i);
//if (it != es.end())
jeuARechercher.push_back(jeuDeDepart[i]);
}
}
clock_t tes1, tes2;
tes1 = clock();
for (i=0; i < tailleEnsemble; ++i)
{
es.insert(jeuDeDepart[i]);
}
tes2 = clock();
clock_t tem1, tem2;
tem1 = clock();
for (i=0; i < tailleEnsemble; ++i)
{
em.add(jeuDeDepart[i]);
}
tem2 = clock();
clock_t t1_1, t2_1;
t1_1 = clock();
// Accède à un certain nombre d'éléments précis selon
// plusieurs index
for (i=0; i < nbRecherches; ++i)
{
for (std::vector<employee>::iterator it = jeuARechercher.begin();
it != jeuARechercher.end();
++it)
{
// Les fonctions membres template qui permette de trouver les
// index par tag ne fonctionnent pas avec MSVC 6
employee_set::iterator eit = get<id>(es).find(it->id());
nth_index_iterator::type eit2 =
get<1>(es).find(it->name());
nth_index_iterator::type eit3 =
get<2>(es).find(it->age());
}
}
t2_1 = clock();
clock_t t1_2, t2_2;
t1_2 = clock();
// Deuxième méthode : avec des maps et des news.
for (i=0; i < nbRecherches; ++i)
{
for (std::vector<employee>::iterator it = jeuARechercher.begin();
it != jeuARechercher.end();
++it)
{
em.byId(it->id());
em.byName(it->name());
em.byAge(it->age());
}
}
t2_2 = clock();
double d1, d2;
d1 = t1_2 - t1_1;
d2 = t2_2 - t2_1;
std::cout << "Insertion" << std::endl;
std::cout << "multi = " << (tes2-tes1) << std::endl
<< "STL = " << (tem2-tem1) << std::endl;
std::cout << "Recherche" << std::endl;
std::cout << "multi = " << d1 << std::endl
<< "STL = " << d2 << std::endl;
return 0;
}
===
Here are the results displayed :
===
Insertion
multi = 329125
STL = 156
Recherche
multi = 735
STL = 625
===
Am I doing something wrong ?
Note that I do not instanciate anything explicitely during insertion
loop.
Regards
--
Stanislas RENAN
