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: joaquin_at_[hidden]
Date: 2008-09-05 05:37:50

Angel Sunye escribió:
> Here you have it.... 
>
> [...]
> bool insert(const QueueMsgKey  &qkey, const TProcessRec &data)
> {
>   TInProcessList process_list;
>   TRefList ref_list;
>   [...]
> }

Àngel, you're inserting into locals TInProcessList and TRefList, so 
basically the
manual version always works against empty containers. I've changed the 
code so that
these containers are moved out of insert and into main just as is the 
case with
elMIContainer (code attached). With this change I compiled the code with 
GCC 3.2
for Cygwin and the following settings:

-O3 -DNDEBUG -finline-functions -Wno-inline -ftemplate-depth-128

and obtained a RATIO of ~0.28.

Joaquín M López Muñoz
Telefónica, Investigación y Desarrollo


#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(
  TInProcessList &process_list,TRefList &ref_list,
  const QueueMsgKey  &qkey, const TProcessRec &data )
{

  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;
  TInProcessList process_list;
  TRefList ref_list;
  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( process_list, ref_list, qack_key, TProcessRec( "..." ) );
  }
  int manualTime = getMicroSecondsPassed( firstTime, firstMicroSeconds );
  std::cout << "<TOutProcessList> Total microseconds : " << manualTime << std::endl;

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