[Boost-users] multi_index : performance issue

From: Stanislas RENAN (stanislas.renan_at_[hidden])
Date: 2004-12-20 05:35:54

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 <boost/multi_index_container.hpp>
#include <boost/multi_index/member.hpp>
#include <boost/multi_index/ordered_index.hpp>
#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<<e.m_id<<" "<<e.m_name<<" "<<e.m_age<<std::endl;
     return os;
   }
};

/* tags for accessing the corresponding indices of employee_set */

struct id{};
struct name{};
struct age{};

/* see Advanced topics: Use of member_offset for info on
  * BOOST_MULTI_INDEX_MEMBER
  */

/* Define a multi_index_container of employees with following indices:
  *   - a unique index sorted by employee::int,
  *   - a non-unique index sorted by employee::name,
  *   - a non-unique index sorted by employee::age.
  */

typedef multi_index_container<
   employee,
   indexed_by<
     ordered_unique<
       tag<id>,  BOOST_MULTI_INDEX_MEMBER(employee,int,m_id)>,
     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<typename Tag,typename MultiIndexContainer>
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<MultiIndexContainer,Tag>::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<value_type>(std::cout));
}

// Un conteneur qui permet de contenir des employee
// triés sur 3 index.
class EmployeeMapper
{
   std::map<int, employee *> m_byId;
   std::map<std::string, employee *> m_byName;
   std::map<int, employee *> m_byAge;
   typedef std::map<int, employee *>::iterator EMIdIt;
   typedef std::map<std::string, employee *>::iterator EMNameIt;
   typedef std::map<int, employee *>::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<int, employee *>::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::vector<std::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<employee_set,1>::type eit2 = 
get<1>(es).find(it->name());
       nth_index_iterator<employee_set,2>::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