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 8 Apr 2010 02:17
于 2010-4-8 17:31, Martin B. 写道:
> 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?

release 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
>

i tried _SECURE_SCL option, and the latest result is:

MAP INSERT LOOKUP
std::map 7.09s 2.00s
boost::unorder_map 5.05s 0.81s
std::unorder_map 9.86s 2.86s

but i can not see that much difference.

the latest test code changed nothing except putting `#define _SECURE_SCL
0` at the very beginning of the cpp file.


jimzshi


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

From: Nemanja Trifunovic on 8 Apr 2010 08:00
> 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.
>

Checked iterators are now turned off by default in VC++ 2010:
http://www.eggheadcafe.com/software/aspnet/35253121/stl-container-performance.aspx

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

From: Alexander Ivaniuk on 9 Apr 2010 06:17
On Apr 8, 12:33 pm, Ulrich Eckhardt <eckha...(a)satorlaser.com> wrote:
> Jim Z. Shi wrote:
> 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.
>

Maps are implemented with red-black trees in MSVS version of STL, so
they are balanced.


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

From: Stephen Howe on 9 Apr 2010 12:18
On Thu, 8 Apr 2010 00:56:34 CST, "Jim Z. Shi" <jim.z.shi(a)gmail.com> wrote:

>I use map a lot in my daily work, so the performance of map is very
>important to me.

Well if it is, I would not use

imap[i] = "test";

to insert in a map. For std::map

imap.insert(std::map<int,string>::value_type(i, "test"));

is better, and best still might be

imap.insert(imap.end(), std::map<int,string>::value_type(i, "test"));

or a better hint.

I once tested on Visual C++ (I think 2001 version), std::map insert and with an
instrumented key, I found

>>
i) use map.insert(make_pair(key,value));
(ii) use map.insert(pair(key,value));
(iii) use map.insert(map::value_type(key,value));
(iv) use map.insert(p); where p is a pre-built pair
(v) use map[key] = value;
(vi) use map.insert(p); where p is a pre-built pair and there is
already a key in the map
(vii) use map[key] = value; where there is already a key in the map


I see operations (view using fixed-width font)


key value
ctor cctor dtor ctor cctor dtor assign op
(i) - 4 3 - 4 3 -
(ii) - 3 2 - 3 2 -
(iii) - 2 1 - 2 1 -
(iv) - 2 1 - 2 1 -
(v) - 2 1 1 2 2 1
(vi) - 1 1 - 1 1 -
(vii) - - - - - - 1


So there is no difference between inserting doing (iii) or (iv) but using
(v) there is extra constructor, assignment operator and destructor for the
value.


For the "successful insertion" cases (i) to (v), the total number of ctors -
dtors is always 1 as of course you wind up with a key,value pair in the map.


(iii) and (iv) are the most efficient (and best still with a good iterator
hint)
>>

I have not used unordered_map, but again, I would use insert.

Stephen Howe

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

From: Stephen Howe on 9 Apr 2010 12:16
On Thu, 8 Apr 2010 03:33:00 CST, Ulrich Eckhardt <eckhardt(a)satorlaser.com> wrote:

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

No it doesnt. The trees used are self-balancing like Red-Black trees, AVL trees,
Scapegoat Trees
If they were not self-balancing, the complexity requirements for std::map would
not be met.

>This doesn't help performance at
>all.

Nonsense. He should be able enter key-values pairs in montonically increasing
order, decreasing order, random order and it
should make no real difference to speed of std::map.find(). The only increase of
speed whould be a suitable hint for insert().

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

The are implemented using hashing.

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

This can happen if keys hash to the same collision point.
But unordered_map should at some point grow and rehash.

Stephen Howe

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

First  |  Prev  |  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