Prev: using operator++() without its side-effect
Next: const is an overrated concept that is a source of extra typing and mai
From: Jim Z. Shi on 7 Apr 2010 15:56
I use map a lot in my daily work, so the performance of map is very
important to me. today i did a very simple test on MSVC10b2, using
std::map, std::unordered_map and boost::unordered_map, and found that
the test result is suprise to me.

here comes test code first:
MSVC10b2, WinXP
//-----------------------------------------------
#include <iostream>
#include <string>
#include <map>
#include <unordered_map>

#include <boost/unordered_map.hpp>
#include <boost/progress.hpp>

using namespace std;

int main()
{
typedef std::unordered_map<int, string> map_t;
//typedef boost::unordered_map<int, string> map_t;
//typedef std::map<int, string> map_t;
const int size = 1E7;
map_t imap;
{
boost::progress_timer t1;
boost::progress_display prog_bar(size);
for(int i=0; i<size; ++i) {
imap[i] = "test";
++prog_bar;
}
}
{
boost::progress_timer t2;
string buff;
for(int i=0; i<size; ++i) {
buff = imap[i];
}
}
return 0;

}
//-----------------------------------------------------------

and the test result:

MAP INSERT FIND
std::map 7.73s 1.98s
boost::unorder_map 5.47s 0.80s
std::unorder_map 9.91s 2.98s


am i wrong with the usage? or something i didn't catch up here?

thanks,
jimzshi


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Ulrich Eckhardt on 7 Apr 2010 18:33
Jim Z. Shi wrote:
> I use map a lot in my daily work, so the performance of map is very
> important to me. today i did a very simple test on MSVC10b2,

I believe MSVC9 didn't turn off iterator debugging unless you specifically
told it to, not even when compiling for release. This might make a big
difference if they still do it. For Boost, you have to explicitly turn it
on instead.

> for(int i=0; i<size; ++i) {
> imap[i] = "test";
> ++prog_bar;
> }

Maps are trees, sorted by the key. Since your key increases monotonically,
every time you insert an element that insert takes place at the same branch
of the tree, so it becomes unbalanced. This doesn't help performance at
all. Suggestion: Unless this really represents your use case, I would
create a vector first, fill it like above and then shuffle the elements,
before using them as keys to insert.

I don't know enough about how the unordered_maps are implemented to make an
educated guess about their behaviour.

> for(int i=0; i<size; ++i) {
> buff = imap[i];
> }

This test is fine, unless of course the map stays unbalanced somehow, which
would mess up the lookup time. I don't think this happens though.

> MAP INSERT FIND
> std::map 7.73s 1.98s
> boost::unorder_map 5.47s 0.80s
> std::unorder_map 9.91s 2.98s

Interesting, thanks for these numbers!

Uli

--
Sator Laser GmbH
Geschäftsführer: Thorsten Föcking, Amtsgericht Hamburg HR B62 932


[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Martin B. on 7 Apr 2010 18:31
Jim Z. Shi wrote:
> I use map a lot in my daily work, so the performance of map is very
> important to me. today i did a very simple test on MSVC10b2, using

What compiler are you using normally and is the performance there any
different?

> std::map, std::unordered_map and boost::unordered_map, and found that
> the test result is suprise to me.
>
> here comes test code first:
> MSVC10b2, WinXP
> (....)
>
> and the test result:
>
> MAP INSERT FIND
> std::map 7.73s 1.98s
> boost::unorder_map 5.47s 0.80s
> std::unorder_map 9.91s 2.98s
>
>
> am i wrong with the usage? or something i didn't catch up here?
>

* Release or debug version?

* Did you disable checked iterators? (I assume they won't affect the
boost version.)
.... Try adding #define _SECURE_SCL 0
and also see
http://msdn.microsoft.com/en-us/library/aa985965%28VS.100%29.aspx


br,
Martin

--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Goran on 7 Apr 2010 18:31
On Apr 8, 8:56 am, "Jim Z. Shi" <jim.z....(a)gmail.com> wrote:
> I use map a lot in my daily work, so the performance of map is very
> important to me. today i did a very simple test on MSVC10b2, using
> std::map, std::unordered_map and boost::unordered_map, and found that
> the test result is suprise to me.
>
> here comes test code first:
> MSVC10b2, WinXP
> //-----------------------------------------------
> #include <iostream>
> #include <string>
> #include <map>
> #include <unordered_map>
>
> #include <boost/unordered_map.hpp>
> #include <boost/progress.hpp>
>
> using namespace std;
>
> int main()
> {
> typedef std::unordered_map<int, string> map_t;
> //typedef boost::unordered_map<int, string> map_t;
> //typedef std::map<int, string> map_t;
> const int size = 1E7;
> map_t imap;
> {
> boost::progress_timer t1;
> boost::progress_display prog_bar(size);
> for(int i=0; i<size; ++i) {
> imap[i] = "test";
> ++prog_bar;
> }
> }
> {
> boost::progress_timer t2;
> string buff;
> for(int i=0; i<size; ++i) {
> buff = imap[i];
> }
> }
> return 0;
>
> }
>
> //-----------------------------------------------------------
>
> and the test result:
>
> MAP INSERT FIND
> std::map 7.73s 1.98s
> boost::unorder_map 5.47s 0.80s
> std::unorder_map 9.91s 2.98s
>
> am i wrong with the usage? or something i didn't catch up here?

Did you set _SECURE_SCL to 0? If not, MS implementation of STL uses
checked iterators whose use adds some overhead. I would guess that
would explain the difference between boost and std unordered map.

BTW, comparing std::map with these two is kinda apples to oranges
comparison, as std::map is based on order, your test does not seem to
be representative of an actual use-case, and you are factoring in
string copying which is tangential to container performance.
Goran.


--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

From: Jim Z. Shi on 8 Apr 2010 02:17
于 2010-4-8 17:33, Ulrich Eckhardt 写道:

>
> Maps are trees, sorted by the key. Since your key increases monotonically,
> every time you insert an element that insert takes place at the same branch
> of the tree, so it becomes unbalanced. This doesn't help performance at
> all. Suggestion: Unless this really represents your use case, I would
> create a vector first, fill it like above and then shuffle the elements,
> before using them as keys to insert.

i think you and Gordan are right, so i add 2 random_shuffle() in my new
test code, here comes the result:

MAP INSERT LOOKUP
std::map 26.59s 23.83s
boost::unorder_map 8.06s 3.77s
std::unorder_map 11.66s 5.95s


and the code is:

//---------------------------------------------------------
#define _SECURE_SCL 0

#include <iostream>
#include <string>
#include <map>
#include <unordered_map>
#include <algorithm>
#include <vector>

#include <boost/unordered_map.hpp>
#include <boost/progress.hpp>

using namespace std;

int main()
{
typedef std::unordered_map<int, string> map_t;
//typedef boost::unordered_map<int, string> map_t;
//typedef std::map<int, string> map_t;
const int size = 1E7;
vector<int> key_arr(size);
for(int i=0; i<size; ++i) {
key_arr[i] = i;
}
random_shuffle(key_arr.begin(), key_arr.end());

map_t imap;
{
boost::progress_timer t1;
boost::progress_display prog_bar(size);
for(int i=0; i<size; ++i) {
imap[ key_arr[i] ] = "test";
++prog_bar;
}
}

random_shuffle(key_arr.begin(), key_arr.end());
{
boost::progress_timer t2;
string buff;
for(int i=0; i<size; ++i) {
buff = imap[ key_arr[i] ];
}
}

return 0;

}




--
[ See http://www.gotw.ca/resources/clcm.htm for info about ]
[ comp.lang.c++.moderated. First time posters: Do this! ]

 |  Next  |  Last
Pages: 1 2 3
Prev: using operator++() without its side-effect
Next: const is an overrated concept that is a source of extra typing and mai