[Multi-index container] Why insertions into my Multi-index container are so slow?

newer
Boost.Multiindex namespace problem

older
boost::logging rolling files prefix

Angel Sunye

4 Sep 2008 4 Sep '08

12:58 p.m.

Hi everyone, I'm using a multi_index_container with 1 composite ordered_unique index and 1 hashed unique index. It have passed the unit tests perfectly, but when I have made the performance test, insertions into multi-index container went much slower than with a manual management. That grows exponentially with the number of insertions: 1000 insertions take 1.5 seconds, almost twice that without Multi-index library 10000 insertions take 160 seconds, thousands of times that without Multi-index library Below you can see my multi_index_container definition, and the insert calls that i have used. -----------------BEGIN CODE----------------- // TElementRec is a struct with its contructors // // Tags struct TMainIndexTag{}; struct TKeyIndexTag{}; 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,int,inputTimestamp), BOOST_MULTI_INDEX_MEMBER(TElementRec,TKey,key) > >, hashed_unique< tag<TKeyIndexTag>, BOOST_MULTI_INDEX_MEMBER(TElementRec,TKey,key) > >

...

TElementsMIContainer;

// Using... TElementsMIContainer elMIContainer; elMIContainer.insert( elMIContainer.template get<TMainIndexTag>().end(), TElementRec( priority, key, content, inputTimestamp, 0 )); elMIContainer.insert( TElementRec( priority, key, content, inputTimestamp, 0 )); -----------------END CODE----------------- Is this boost implementation correct? Thanks a lot for your time Angel Suñe Marti

Attachments:

attachment.html (text/html — 3.0 KB)

Show replies by date

joaquin＠tid.es

4 Sep 4 Sep

1:27 p.m.

New subject: [Multi-index container] Why insertions into my Multi-index container are so slow?

Hi Àngel, Angel Sunye escribió:

...

Hi everyone,

I'm using a multi_index_container with 1 composite ordered_unique index and 1 hashed unique index. It have passed the unit tests perfectly, but when I have made the performance test, insertions into multi-index container went much slower than with a manual management. That grows exponentially with the number of insertions:

1000 insertions take 1.5 seconds, almost twice that without Multi-index library 10000 insertions take 160 seconds, thousands of times that without Multi-index library

Below you can see my multi_index_container definition, and the insert calls that i have used.[...]

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 ? * Are you building in release or debug mode? Any difference if you change this? * You say you're comparing against manual management: can you please explain what this manual management consists in? * What's your environment (compiler, OS)? * 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? Hopefully some of these points can shed some light on the problem. Looking fwd to your answer, Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Angel Sunye

3:19 p.m.

...

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 :: 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_caststd::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

Joaquin M Lopez Munoz

4:44 p.m.

Angel Sunye writes:

...

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.

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? [...]

...

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

Unfortunately, the snippet you pasted above is not a complete program that I can compile and run, and it is not obvious how to fill in the missing parts. So, I can only speculate after visually inspecting the code. In general, using a multi_index_container with two indices should be faster than relying in two synced containers: the manual version differs quite a bit from the multi_index variation, so I don't know whether they are really equivalent. In the multi_index version you're providing end() as an insertion hint: this is probably a misguided hint and omitting it should speed things up a little, though I don't think it'll make a dramatic difference. 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. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo

Angel Sunye

5 Sep 5 Sep

8:31 a.m.

...

...
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 #include #include #include <iostream> #if defined(NDEBUG) #define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING #define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE #endif #include <map> #include #include #include #include #include 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 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_caststd::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_caststd::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í

joaquin＠tid.es

9:37 a.m.

New subject: [Multi-index container] Why insertions into my Multi-index container are so slow?

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 #include #include #include <iostream> #if defined(NDEBUG) #define BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING #define BOOST_MULTI_INDEX_ENABLE_SAFE_MODE #endif #include <map> #include #include #include #include #include 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 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( 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_caststd::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_caststd::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; }

Angel Sunye

1:56 p.m.

...

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

5930

Age (days ago)

5931

Last active (days ago)

List overview

Download

6 comments

3 participants

participants (3)

Angel Sunye
Joaquin M Lopez Munoz
joaquin＠tid.es