[boost] Please Help: Experienced very bad performance with Multi-index

Subject: [boost] Please Help: Experienced very bad performance with Multi-index
From: Jarolin, Robert (Robert.Jarolin_at_[hidden])
Date: 2009-07-29 16:12:27

Below is a sample program that I am running.  If I create a multi-index
as defined below, the performance as the number of entries increases
gets to the point of being unusable.

Examples: 
Num Entries   Time to insert last entry     Time to insert all entries 
100                 452 usecs                        30.4 millisecs 
1000               4.6 millisecs                     2.4 seconds 
10000              52.2 millisecs                   266.92 seconds (over
4.5 minutes) 

This performance does not seem to be correct to me.  Deletions from a
multiindex based on a key, were taking super long as well (not shown in
the below program).  To delete all 1000 entries based on being below a
certain ordered value was taking over 2 minutes.

Is there something that is wrong with the below program that is causing
these issues?  Thanks for any help. 

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX Cut Here
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX 

#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 <boost/multi_index/hashed_index.hpp> 
#include <algorithm> 
#include <iostream> 
#include <iterator> 
#include <string> 
#include <sys/time.h> 

using boost::multi_index_container; 
using namespace boost::multi_index; 
using namespace std; 

struct ErRecord 
{ 
  int         value1; 
  std::string value2; 
  int         value3; 
  int         value4; 

  ErRecord() 
    : value1(0), 
      value2(""), 
      value3(0), 
      value4(0) 
  { 
  } 

  ErRecord(int _value1, const std::string& _value2, const int _value3,
int _value4) 
    : value1(_value1), 
      value2(_value2), 
      value3(_value3), 
      value4(_value4) 
  { 
  } 

}; 

//@@== Tags 
struct value1 {}; 
struct value2 {}; 
struct value4 {}; 
struct value3 {}; 

typedef multi_index_container < 
  ErRecord, 
  indexed_by < 
    ordered_non_unique < 
      tag<value1>, BOOST_MULTI_INDEX_MEMBER(ErRecord, int, value1) 
    >, 
    ordered_non_unique < 
      tag<value2>, BOOST_MULTI_INDEX_MEMBER(ErRecord, std::string,
value2) 
    >, 
    ordered_non_unique < 
      tag<value3>, BOOST_MULTI_INDEX_MEMBER(ErRecord, int, value3) 
    >, 
    ordered_non_unique < 
      tag<value4>, BOOST_MULTI_INDEX_MEMBER(ErRecord, int, value4) 
    > 
  > 
> ErRecordMap; 

int main(int argc, char* argv[]) 
{ 
  int numloops = 100; 
  if (argc > 1) 
    numloops = atoi(argv[1]); 

  ErRecordMap em; 

  char buf[50]; 
  int i = 0; 
  int sec; 
  int usec; 
  unsigned long long u64; 
  
  struct timeval tv_start, tv_end; 
  struct timeval tv_before, tv_after; 
  
  gettimeofday( &tv_start, 0 ); 

  while (1) 
  { 
    sprintf(buf, "value2-%d", i); 

    gettimeofday( &tv_before, 0 ); 
    em.insert(ErRecord(i, string(buf), i, i)); 
    gettimeofday( &tv_after, 0 ); 

    if( i == numloops ) 
    { 
      sec =  tv_after.tv_sec - tv_before.tv_sec; 
      usec = tv_after.tv_usec - tv_before.tv_usec; 
      if (usec < 0) 
      { 
        sec--; 
        usec += 1000000; 
      } 

      u64 = sec * 1000000 + usec; 
      cout << "Time to insert last entry: " << sec << ":" << usec <<
endl; 
    } 
    ++i; 

    if( i > numloops ) 
    { 
      break; 
    } 
  } 

  gettimeofday( &tv_end, 0 ); 
  sec =  tv_end.tv_sec - tv_start.tv_sec; 
  usec = tv_end.tv_usec - tv_start.tv_usec; 
  if (usec < 0) 
  { 
    sec--; 
    usec += 1000000; 
  } 

  u64 = sec * 1000000 + usec; 
  cout << "total: " << numloops << "," << sec << ":" << usec << endl; 
  cout << "average: " << numloops << "," << u64/numloops << "usec" <<
endl; 
  
  return 0; 
} 

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX Cut Here
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX