Performance difference between std::unordered_map and boost::unordered_map

[gas...@hotmail.com]

Hello all

we use here Visual Studio 2010 and notice quite an impressive
performance difference between the boost and std unordered_map: about
a factor 10 in favor of the boost implementation. Is there something
specified in the std which makes them slower?

boost::unordered_map 0.574148
stl::unordered_map 5.758360
stl::map 17.927353


Test code is quite simple (it uses a value of std::pair<int,
std::string>):

int g_n = 0;

void f()
{
std::map<int, std::string> mapStl;
std::unordered_map<int, std::string> umapStl;
boost::unordered_map<int, std::string> umapBoost;

const int nMaxSize = 500000;
const int nMaxFind = 100000000;

//create maps with 500000 elements

//find
{
DBG_PRF_PROFILE_FUNCTION_TEXT("_stl_map_find");

for (int n = 0; n < nMaxFind; ++n)
{
g_n += mapStl.count(n % nMaxSize);
}
}

etc...
}


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

[Dave Abrahams]

on Thu Oct 20 2011, "gast128-AT-hotmail.com" <gast128-AT-hotmail.com> wrote:

> Hello all
>
> we use here Visual Studio 2010 and notice quite an impressive
> performance difference between the boost and std unordered_map: about
> a factor 10 in favor of the boost implementation. Is there something
> specified in the std which makes them slower?
>
> boost::unordered_map 0.574148
> stl::unordered_map 5.758360
> stl::map 17.927353

Only a great deal of flexibility left to the implementor w.r.t. how to
implement the map. The Dinkumware version of the hash containers (which
is shipped in a modified form by Microsoft) IIUC uses a scheme of
incremental rehashing and keeps everything in a doubly-linked list,
which has certain functionality benefits but also some intrinsic costs.
Then there's also the question of whether you are using VS2010 in
"secure" mode, which does a lot of potentially-expensive error checking
that Boost does not, at least by default.

--
Dave Abrahams
BoostPro Computing
http://www.boostpro.com

[Daniel Krügler]

Am 20.10.2011 19:56, schrieb gas...@hotmail.com:
> we use here Visual Studio 2010 and notice quite an impressive
> performance difference between the boost and std unordered_map: about
> a factor 10 in favor of the boost implementation. Is there something
> specified in the std which makes them slower?

Not that I am aware of. But I think that your test isn't properly
set-up, because in addition to the implementation differences of the
maps it also measures the quality of the hasher to an unknown degree.
The proper solution is to ensure that these are equal for all tests.

> boost::unordered_map 0.574148
> stl::unordered_map 5.758360
> stl::map 17.927353

I cannot reproduce the exact ratios, but similar ones. I'm getting a
ratio of

2.4 : 9.2 : 12.5

If I'm using std::unordered_map<int, std::string>::hasher for both
std::unordered_map and boost::unordered_map, I get

9.9 : 9.2 : 12.5

To be on the safe side I used boost::unordered_map<int,
std::string>::hasher for both std::unordered_map and
boost::unordered_map, and get:

2.3 : 2.3 : 12.7

This seems to be a clear answer to your question: The observable
difference is due to the quality of the default hasher.

HTH & Greetings from Bremen,

Daniel Krügler

[Zeljko Vrba]

On 2011-10-20, gas...@hotmail.com <gas...@hotmail.com> wrote:
>
> we use here Visual Studio 2010 and notice quite an impressive
>

VS implementation has extensive debugging checks; some of them are enabled
even in release mode. Read about iterator debugging and secure STL; all
of that is described in detail on MSDN if you search a bit.

[Vyacheslav Lanovets]

Hello!

On 20.10.2011 21:56, gas...@hotmail.com wrote:
> Hello all
>
> we use here Visual Studio 2010 and notice quite an impressive
> performance difference between the boost and std unordered_map: about
> a factor 10 in favor of the boost implementation. Is there something
> specified in the std which makes them slower?

boost::unordered_map uses much simpler hash function for integers (just
integer value itself).

I've got about 1.5x difference instead of 6x after I used same hash as
in boost.

struct myhash : public std::unary_function<int, size_t>
{
size_t operator()(const int a) const
{
return a;
}
};
std::unordered_map<int, std::string, myhash> stlmap1;


And it's interesting to know if VS2010's hash implementation can ever be
more useful for unordered map.

Regards,
Vyacheslav

[Goran]

On Oct 20, 7:56 pm, "gast...@hotmail.com" <gast...@hotmail.com> wrote:
> Hello all
>
> we use here Visual Studio 2010 and notice quite an impressive
> performance difference between the boost and std unordered_map: about
> a factor 10 in favor of the boost implementation. Is there something
> specified in the std which makes them slower?

Did you make sure that you're measuring optimized release build, and,
for VS implementation, did you set SECURE_STL to 1?

Goran.

[gas...@hotmail.com]

> VS implementation has extensive debugging checks; some of them are enabled
> even in release mode. Read about iterator debugging and secure STL; all
> of that is described in detail on MSDN if you search a bit.

It is release mode and checked iterators are turned off in release
mode in vs2010 (they were turned on in vs2008).

[gas...@hotmail.com]

> Not that I am aware of. But I think that your test isn't properly
> set-up, because in addition to the implementation differences of the
> maps it also measures the quality of the hasher to an unknown degree.
> The proper solution is to ensure that these are equal for all tests.
>

> <snip>

>
> 2.3 : 2.3 : 12.7
>
> This seems to be a clear answer to your question: The observable
> difference is due to the quality of the default hasher.

Ah thx. I observed a similar problem years ago with stdext::hash_map
in combination with string as key. That one also performed dramatic
due to a faulty hasher. Ofc most people just instantiate a container,
without filling in the allocator, less functors or the hasher. So
maybe the discussion should be turned to the quality of the default
hasher then.

[gas...@hotmail.com]

> To be on the safe side I used boost::unordered_map<int,
> std::string>::hasher for both std::unordered_map and
> boost::unordered_map, and get:
>
> 2.3 : 2.3 : 12.7

I 've done the same now (using the hasher from Boost.UnorderedMap in
std) and I got the following results:

boost_umap_find 0.617196
stl_map_find 17.753042
stl_umap2_find 1.280430 (this one is std with Boost hasher)
stl_umap_find 5.820848

So the main problem is in the hashing and a smaller part in the
container itself. My pc is about 2 years old with 64 bits Windows 7
(but test compiled for 32 bits) and its processor is a quad core Xeon
(I thought similar to a Core i7). Form experience I know that Intel
keeps improving over the years even for single core applications (in
memory access, caching etc), so that could be an explanation for the
absolute difference.

[Stephan T. Lavavej]

[Dave Abrahams]

> Then there's also the question of whether you are using VS2010 in
> "secure" mode, which does a lot of potentially-expensive error checking
> that Boost does not, at least by default.

That was enabled by default in VC8/9 release mode (_SECURE_SCL=1), but
is disabled by default in VC10 release mode (_ITERATOR_DEBUG_LEVEL=0).

Our exhaustive correctness checks, including iterator invalidation,
are still enabled by default in debug mode (_HAS_ITERATOR_DEBUGGING=1
in VC8/9, _ITERATOR_DEBUG_LEVEL=2 in VC10). Of course, debug mode perf
is not interesting, except when it makes programs so slow as to be un-
debuggable. In related news, unordered_map sometimes had severe perf
problems under IDL=2; we believe we've entirely squashed them in VC11.

[Daniel Krügler]

> This seems to be a clear answer to your question: The observable
> difference is due to the quality of the default hasher.

Coincidentally, I just finished working on changes to clean up our
std::hash implementation. I'm measuring hash<int> as 2.2x faster than
VC10 SP1, and hash<unsigned long long> as 7.5x faster.

My new approach (which still has to be sent to Dinkumware for review
and integration) can be summarized as "throw FNV-1a at the problem".

[Goran]

> Did you make sure that you're measuring optimized release build, and,
> for VS implementation, did you set SECURE_STL to 1?

It's spelled _SECURE_SCL, and 1 means "enable slower security checks".
The default of 0 means "superspeed mode, absolutely no checking
(except integer overflow in memory allocation)".

Stephan T. Lavavej
Visual C++ Libraries Developer

[Michael]

On Oct 23, 4:13 pm, "Stephan T. Lavavej" <s...@nuwen.net> wrote:
> Coincidentally, I just finished working on changes to clean up our
> std::hash implementation. I'm measuring hash<int> as 2.2x faster than
> VC10 SP1, and hash<unsigned long long> as 7.5x faster.
>
> My new approach (which still has to be sent to Dinkumware for review
> and integration) can be summarized as "throw FNV-1a at the problem".

Are you are aware of this analysis:
http://home.comcast.net/%7Ebretm/hash/6.html

Quote:
"I don't recommend using 32-bit FNV as a general-purpose hash. It can
produce uniform output, but its suitability needs to be tested for
each
class of keys for which you intend to use it."

The author does suggest modification that improves the result
substantially.

See also http://sites.google.com/site/murmurhash/avalanche