Boost logo

Boost Users :

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;
}


Boost-users list run by williamkempf at hotmail.com, kalb at libertysoft.com, bjorn.karlsson at readsoft.com, gregod at cs.rpi.edu, wekempf at cox.net