Re: [Boost-users] [Multi-index container] Why insertions into my Multi-index container are so slow?

Subject: Re: [Boost-users] [Multi-index container] Why insertions into my Multi-index container are so slow?
From: Angel Sunye (angelsunye_at_[hidden])
Date: 2008-09-05 04:31:06

> > OK, this seems to explain most of the issue.
> > What's the ratio t(multi_index)/t(manual) in debug and
> > release modes after suppresing safe mode and invariant-
> > checking?

In both cases the ratio is more or less the same. So, it is
between 3.28 and 3.62, depending of execution.

I have tested with only a ordered-unique index and the ratio
was 2.59, and also with only a hashed-unique index and the
result was 1.10.

[...]
> > Other than this I can't be much more helpful. If you're
> > in a position to provide me with a complete example program
> > that I can play with I'll sure have a deeper look.

Here you have it....

#include <boost/lexical_cast.hpp>
#include <sys/time.h>
#include <unistd.h>
#include <iostream>

#if defined(NDEBUG)
#define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING
#define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE
#endif

#include <map>
#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 <boost/multi_index/composite_key.hpp>

using namespace boost::multi_index;

//////////////////////////////////////
// Types declarations
//////////////////////////////////////
enum PRIORITY_LEVEL {
  PRIORITY_EXPRESS,
  PRIORITY_HIGH,
  PRIORITY_DEFAULT,
  PRIORITY_LOW,
  PRIORITY_NULL
};

struct TElementRec {
  PRIORITY_LEVEL  priority;
  std::string     key;
  std::string     content;

  TElementRec():
    priority(PRIORITY_DEFAULT){}
  TElementRec( const PRIORITY_LEVEL &priority, const std::string &key, const
std::string &content ):
    priority(priority), key(key), content(content){}
  TElementRec( const TElementRec &rec ) {
    priority        = rec.priority;
    key             = rec.key;
    content         = rec.content;
  }
  TElementRec & operator = ( const TElementRec &rec ) {
    priority        = rec.priority;
    key             = rec.key;
    content         = rec.content;
    return( *this );
  }
};

// Tags
struct TMainIndexTag{};
struct TKeyIndexTag{};

// Multi index container definition
typedef multi_index_container<
  TElementRec,
  indexed_by<
    ordered_unique<
      tag<TMainIndexTag>,
      composite_key<
        TElementRec,
        BOOST_MULTI_INDEX_MEMBER(TElementRec,PRIORITY_LEVEL,priority),
        BOOST_MULTI_INDEX_MEMBER(TElementRec,std::string,key)
      >
    >,
    hashed_unique<
      tag<TKeyIndexTag>,
      BOOST_MULTI_INDEX_MEMBER(TElementRec,std::string,key)
    >
  >
> TElementsMIContainer;

// MANUAL DECLARATIONS
//////////////////////
struct TProcessRec {
   std::string content;

   TProcessRec() {
   };
   TProcessRec( const std::string &msg ) {
      this->content           = msg;
   };
   TProcessRec( const TProcessRec &pRec ) {
      content              = pRec.content;
   }
   TProcessRec & operator = ( const TProcessRec &pRec ) {
      content              = pRec.content;
      return( *this );
   }
};

struct QueueMsgKey {
  std::string     key;
  PRIORITY_LEVEL  priority;

  QueueMsgKey(const std::string &_key, const PRIORITY_LEVEL &_priority) {
    key   = _key;
    priority  = _priority;
  }
  QueueMsgKey(const std::string &_key) {
    key   = _key;
    priority  = PRIORITY_DEFAULT;
  }
  QueueMsgKey() {
    priority = PRIORITY_DEFAULT;
  }
  QueueMsgKey & operator = ( const  QueueMsgKey &pRec ) {
     priority              = pRec.priority;
     key               = pRec.key;
     return( *this );
  }
};

struct QueueMsgKeyLess {
    bool operator()(const  QueueMsgKey k1, const  QueueMsgKey k2) const
    {  return k1.priority!=k2.priority ? k1.priority>k2.priority :
k1.key<k2.key; }
};

struct MsgKeyLess {
    bool operator()(const  std::string k1, const  std::string k2) const
    {  return k1<k2; }
};

typedef std::map< QueueMsgKey, TProcessRec, QueueMsgKeyLess >
TInProcessList;
typedef std::map< QueueMsgKey, TProcessRec, QueueMsgKeyLess > :: iterator
TProcessListIterator;
typedef std::map< std::string, TProcessListIterator, MsgKeyLess > TRefList;
typedef std::map< std::string, TProcessListIterator, MsgKeyLess > ::
iterator TRefListIterator;

//////////////////////////////////////
// Code
//////////////////////////////////////
int getMicroSecondsPassed( int &timestamp, int &microSeconds )
{
  int lTimestamp = time(NULL);
  struct timeval tv;
  gettimeofday(&tv, NULL);
  char msecs[ 20 ];
  sprintf( msecs, "%d", tv.tv_usec );
  std::string strMSecs = msecs;
  int lMicroSeconds = boost::lexical_cast<int>( strMSecs );

  if ( !timestamp ) {
    timestamp     = lTimestamp;
    microSeconds  = lMicroSeconds;
    return 0;
  }
  return (lTimestamp-timestamp)* 1000000 + (lMicroSeconds-microSeconds);
}

bool insert(const QueueMsgKey  &qkey, const TProcessRec &data)
{
  TInProcessList process_list;
  TRefList ref_list;

  TRefListIterator itr = ref_list.find( qkey.key );
  if ( itr == ref_list.end() ) {
    std::pair< TProcessListIterator, bool > result = process_list.insert(
std::make_pair( qkey, data) );
    if(result.second == true) {
      ref_list[qkey.key] = result.first;
      return true;
    }
    else {
      return false;
    }
  }
  return false;
}

int main( int argc, char** argv ){
  int firstTime         = 0;
  int firstMicroSeconds = 0;
  TElementsMIContainer  elMIContainer;
  PRIORITY_LEVEL priority = PRIORITY_DEFAULT;
  std::string content     = "...";
  std::string key;

  // Multi-index container performance test
  ////////////////////////////////////////////
  getMicroSecondsPassed( firstTime, firstMicroSeconds );
  for ( int i=0; i<100000; i++ ) {
    // Changing only the key
    key = "A0000" + boost::lexical_cast<std::string>(i);
    elMIContainer.insert( TElementRec( priority, key, content ));
  }
  int multiindexTime = getMicroSecondsPassed( firstTime, firstMicroSeconds
);
  std::cout << "<TQueueScheduler> Total microseconds : " << multiindexTime
<< std::endl;

  firstTime         = 0;
  firstMicroSeconds = 0;
  // Manual containers performance test
  ////////////////////////////////////////////
  getMicroSecondsPassed( firstTime, firstMicroSeconds );
  for ( int i=0; i<100000; i++ ) {
    // Changing only the key
    QueueMsgKey qack_key( "A0000" + boost::lexical_cast<std::string>(i) );
    insert( qack_key, TProcessRec( "..." ) );
  }
  int manualTime = getMicroSecondsPassed( firstTime, firstMicroSeconds );
  std::cout << "<TOutProcessList> Total microseconds : " << manualTime <<
std::endl;

  std::cout << "RATIO=" << (float)multiindexTime / manualTime << std::endl;
}

Thanks a lot for your time

Àngel Suñé Martí