Boost multi-index with slow insertion performance

Question

I have the following code (which largely follows the first example here: http://www.boost.org/doc/libs/1_42_0/libs/multi_index/doc/examples.html)). For some reason, with only 10000 insertations to the multi-index, it takes several minutes to run the program. Am I doing something wrong or is this expected?

struct A  
{  
  int id;  
  int name;  
  int age;  
  A(int id_,int name_,int age_):id(id_),name(name_),age(age_){}  
};  


/* tags for accessing the corresponding indices*/  
struct id{};  
struct name{};  
struct age{};  

typedef multi_index_container<  
  A,  
  indexed_by<  
    ordered_unique<  
      tag<id>,  BOOST_MULTI_INDEX_MEMBER(A,int,id)>,  
    ordered_non_unique<  
      tag<name>,BOOST_MULTI_INDEX_MEMBER(A,int,name)>,  
    ordered_non_unique<  
      tag<age>, BOOST_MULTI_INDEX_MEMBER(A,int,age)> >  
> A_set;  



int main()  
{  
  A_set es;  

  for (int a = 0; a != 10000; a++) {  
    es.insert(A(a,a+1,a+2));  
  }  
  return 0; 
}

Answer 1

From my own experience with the boost::bi_map (which is to my best knowledge based on the multi-index containers), I have to say that those multi-index containers are unfortunately relatively slow. That is not for inserting performance, however. So I don't really understand why it is so slow in your case.

I did a small benchmark comparing a boost::bi_map to two boost::unordered_maps. Insertion of 100'000 unique values is around 1 second for both approaches. However, querying of 50000000 values is 10 seconds for the unordered_map and 26 second for the ordered map (that is using integer keys). (Our best in-house data structure performs the lookups in around 1 second).

Answer 2

Are you by any chance compiling in debug mode? It finishes near instantly with the default release configuration in Visual Studio 2008. If you're compiling in debug mode and you almost followed the example to the letter, including the pre-processor stuff and still had this part:

#ifndef NDEBUG
#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
#endif

Then removing/disabling these defines will also significantly speed up execution time. (By at least 180x on my machine, didn't bother letting it finish.) What the consequences of disabling or removing these things in a debug build is, I don't know.

Answer 3

Several minutes seems very slow - I'd expect seconds at the most for a modern CPU. Boost tends to use many small functions that in a debug build run significantly slower than an optimized release build.

Also verify that BOOST_MULTI_INDEX_ENABLE_SAFE_MODE and BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING are not set. These both perform additional runtime checking.