QuoteOriginally posted by: outrunQuoteOriginally posted by: PolterQuotein the first link, VS2010 C++ has the same performance as C#, right? That shows that both might be optimized now.Negative, "With an occasional exception, C# wins by a landslide! One particular C++ scenario, x86 VC10 with SSE2, runs better than the others and when handling strings, outperforms C#. However, in most situations VC++ loses big time. The first test, for example, runs over 9 times faster in .NET4 x64 compared to C++ VC10 SSE2."He only got an improvement when he used his own implementation instead of the standard (std::unordered_map) one:"Anyway, I can say with certainty that it's not the C++ compiler's fault. I know this because I wrote my own version of hash_map for my company, and my implementation runs roughly ten times faster (with int keys). I knew I got better performance from my hashtable, but I didn't realize how dramatic the difference could be until I saw the numbers. Here are the results based on my implementation: [...]As you can see, C++ is much more competitive now. It wins some races, and loses others. My hash_map is heavily inspired by the design of .NET's Dictionary, and I am unable to guess why my version outperformed C# while doing int queries and removals, yet not inserts."QuoteHowever, in the google groups like shows the performance gain of unordered_map 0.6sec vs map 17sec.Yes -- which emphasizes that it wasn't the C++ compiler's fault per se, but rather the particular implementation (std::unordered_map). Consequently, when switching to better implementations, the problem is addressed: both the custom implementation ("my hash_map") and another reference implementation (boost::unordered_map) have no performance problems. However, that still means that std::unordered_map has performance problems, and they appear to be rather serious on as recent version as MSVC 2010.ok, that's clear. So suppose we have a *good* implementation, then a sparse matrix should benefit from it because an ordered map does unneeded ordening.It's still interesting even then! I'm assuming you're referring to hopefully-constant (and hopefully-avoiding worst-case linear) complexity instead of logarithmic in some of the operations (inserting, erasing, searching) -- and to that extent I agree with you, if those are the kinds of operations that are most common for the application (sparse matrices) and we hope to avoid the kind of data that could cause the worst-case complexity, then I expect unsorted to be faster.However, in general it's hard to tell in advance, without profiling:Complexity guarantees -- depends on the operation, e.g., construction of empty container is O(1) for (sorted) associative containers, but O(n) for unordered associative containers (hash maps)Interface -- also depends, e.g., iterator invalidation is never possible for the (sorted) ones:See tables comparing (ordered)map with unordered map here:http://www.boost.org/doc/libs/release/d ... son.htmlIn
particular, even O(1) vs. O(log N) is not always as clear cut as it might seem, those constants can get pretty large, in particular in case of associative containers:http://lanzkron.wordpress.com/2010/06/0 ... utzes/From
the section "Hash map":Quote"std::map has logarithmic complexity, a no-brainer would be to use a constant time cache, luckily Visual Studio 9 supplies std::tr1::unordered_map, that's bound to improve things.Nope, 26.22, things are just going from bad to worse (317%), how can a constant speed algorithm do worse than a logarithmic one? Well it all depends on your constants, it's easy to forget that as programmers we mostly use bounded numbers; even logarithmic complexity on a 32 bit number is constant if you take the big view. Anyway things aren't that bad, if we try using boost::unordered_map instead of the Visual Studio's implementation we "only" take 14.57 seconds (176%).Lesson 1: I wouldn't go so far to say that MS's implementation of unordered_map is inferior but you should remember that you depend on the quality of the implementation you're using and some implementations will work better with some data sets."