I don't see anything strange with your definitions... In order to try to elucidate what's going on, I'd need some more information:

* Are you using the safe mode and/or the invariant-checking mode described at http://www.boost.org/libs/multi_index/doc/tutorial/debug.html ?

Perfect!!!... Just I had #if !defined(NDEBUG) #define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING #define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE #endif and I haven't defined NDEBUG!!! Now, time is much better than before, but still continues slow than manually.

* You say you're comparing against manual management: can you please explain what this manual management consists in?

I wanted to refer manual management as without using multi-index library. The code I used is as follows: -----------------BEGIN CODE----------------- // Record definition struct TProcessRec { std::string text; u32 inputTimestamp; // Constructors... }; enum PRIORITY_LEVEL { PRIORITY_NULL, PRIORITY_LOW, PRIORITY_DEFAULT, PRIORITY_HIGH, PRIORITY_EXPRESS }; // Key definition struct QueueMsgKey { std::string msg_key; PRIORITY_LEVEL priority; // Constructors.... }; struct QueueMsgKeyLess { bool operator()(const QueueMsgKey k1, const QueueMsgKey k2) const { return k1.priority!=k2.priority ? k1.priority>k2.priority : k1.msg_key<k2.msg_key; } }; struct MsgKeyLess { bool operator()(const std::string k1, const std::string k2) const { return k1<k2; } }; // Container types definition typedef std::map< QueueMsgKey, TProcessRec*, QueueMsgKeyLess > :: iterator TProcessListIterator; typedef std::map< std::string, TProcessListIterator, MsgKeyLess > :: iterator TRefListIterator; // Class definition class TOutProcessList { private: TInProcessList process_list; TRefList ref_list; public: bool insert(const QueueMsgKey &qmsg_key, TProcessRec* const data) { TRefListIterator itr = ref_list.find( qmsg_key.msg_key ); if ( itr == ref_list.end() ) { std::pair< TProcessListIterator, bool > result = process_list.insert( std::make_pair( qmsg_key, data) ); if(result.second == true) { ref_list[qmsg_key.msg_key] = result.first; return true; } else return false; } return false; }; }; // Testing manual form... TOutProcessList elContainer; for ( int i=0; i<10000; i++ ) { QueueMsgKey key( "A0000" + boost::lexical_cast<std::string>( i ) ); elContainer.insert( key, new( "...", time(NULL) )); } // Here prints total time 1 // Testing with Multi-index library TElementsMIContainer elMIContainer; for ( int i=0; i<10000; i++ ) { elMIContainer.insert( elMIContainer.template get<TMainIndexTag>().end(), TElementRec( priority, key, content, inputTimestamp, 0 )); } // Here prints total time 2 RESULT: time 2 > time 1 -----------------END CODE-----------------

* Are you building in release or debug mode? Any difference if you change this?

No. And I use the same program for comparing both forms (insertions with Multi-index and without).

* What's your environment (compiler, OS)?

I'm using g++ 4.3.0 with Boost library 1.35.0 in Linux

* Are you able to isolate this odd behavior in a complete program that you can send to me so that I can reproduce the problem locally?

Copied before Thanks a lot for your time Angel Suñe Marti

...

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 ×tamp, int µSeconds ) { 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í

...

À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.

Perfect, now multi-index version is quite faster, specially with -O3 flag. Thank you very much Àngel Suñé Martí