0

I was using an map with a map<long, X> For tuning performance I decided to experiment with unordered map too. I tried a 100k inserts using the operator[] with both. The map took ~140seconds whereas the unordered map tool ~230 seconds for the same code. I was expecting the unordered_map to be much faster! Am I wrong or is something fishy here?

Have searched for previous answers but they all point to unordered_map being faster. Hence the question. Can provide more details. Ran the below benchmark, first case takes ~0 seconds, 2nd one takes 8 seconds.

#include <map> #include <unordered_map> #include <iostream> #include <time.h> #include <stdlib.h> using namespace std; struct X{ long a, b, c, d, e, f; string x, y, z; }; struct mapZ{ long id; map<long, X> xMap; }; struct unmapZ{ long id; unordered_map<long, X> xUnMap; }; unmapZ & addUnMap(unmapZ & um, X & xtmp) { um.xUnMap[xtmp.a] = xtmp; return(um); } mapZ & addMap(mapZ & mp, X & xtmp) { mp.xMap[xtmp.a] = xtmp; return(mp); } int main() { int numItr = 10000; map<long, X> myMap; unordered_map<long, X> myUnMap; mapZ mp; unmapZ uz; uz.id = (long)1; uz.xUnMap = myUnMap; mp.id = (long)1; mp.xMap = myMap; time_t start = time(0); for(int i = 0; i < numItr; i++) { long id = (long)rand(); X tmp; tmp.a = id; tmp.b = id; tmp.c = id; tmp.d = id; tmp.e=id; tmp.f=id; tmp.x = "ABCDEF"; tmp.y = "WXYZS"; tmp.z = "UVGHJ"; mp = addMap(mp, tmp); } cout << "size of map: " << mp.xMap.size() << "\n"; time_t eof_map = time(0); for(int i = 0; i < numItr; i++) { long id = (long)rand(); X tmp; tmp.a = id; tmp.b = id; tmp.c = id; tmp.d = id; tmp.e=id; tmp.f=id; tmp.x = "ABCDEF"; tmp.y = "WXYZS"; tmp.z = "UVGHJ"; uz = addUnMap(uz, tmp); } cout << "size of unmap: " << uz.xUnMap.size() << "\n"; time_t eof_unmap = time(0); cout << "Map inset time: " << eof_map - start << "\n"; cout << "Unord Map insert time: " << eof_unmap - eof_map << "\n"; return(0); }

Here is the command line to run the benchmark:

g++ -O3 -std=c++0x -m64 -Wno-write-strings -fopenmp mapTest.cpp

running GCC 4.6 on Ubuntu.

Improve this question
8
  • Start with searching for previous answers. See here for example: stackoverflow.com/questions/2196995/… Commented Mar 5, 2014 at 13:37
  • "1.5 minutes more" - compared to what? no information here whatsoever. if you want to give a single figure, give a percentage Commented Mar 5, 2014 at 13:41
  • 2
    @Claptrap Not a duplicate. Commented Mar 5, 2014 at 13:41
  • @Karoly, added more details Commented Mar 5, 2014 at 13:44
  • en.cppreference.com/w/cpp/container/unordered_map/reserve Commented Mar 5, 2014 at 13:45

2 Answers 2

Reset to default
4

There are many, many problems with this benchmark code, rendering its output irrelevant.

Firstly, you've used a completely unreliable and terrible timing clock. Use std::high_performance_clock.

Secondly, you've padded the sample value types with many extra std::strings and you copy this type everywhere. The high variability of the memory allocator (and the fact that you unfairly ran one test from a non-fresh process) is very bad.

Thirdly, you've included things like I/O in the benchmark time- and no, it's still totally not fair at all when you output the same string.

Fourthly, rand() can only produce a small range of values, which is an unfair comparison for the unordered_map. If you have a use case that really is only a small range of values, you can get much better push out of a hash map with an appropriate hasher change.

But the whale here is that your test is unfair because you self-assigned. You assigned the map and unordered-map to themselves. This is an unfair test because the legacy map code has a self-assignment check in it making the assignment a no-op. The new unordered_map code follows the new best practices and doesn't. Effectively, you redundantly copied the unordered_map and only the unordered_map thousands of extra times just for fun, changing O(n) into O(n^2) or O(n^3). Of course nobody with any sanity self-assigns, so this completely blows all the results out of any kind of relevance.

Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

ok, i can correct 1,2,3,4 but don't understand the self-assign part. do you mean when I'm adding to the map and returning the same object? I thought that might be safer as passing by reference would reduce copying of variables.
You do uz = addUnMap(...). That's assigning uz to the reference you just returned.
so should i be returning the value i.e change the addUnMapZ function to unMapZ addUnMapZ(). relatively new to c++, so thanks for your patience
No, simply don't assign the return value.
yes, i think i got it. add functions should be void. It reduces the time taken by factor of 1000. can you pls confirm if thats right. so it should be void addUnMapZ(unMapZ & um... and in main addUnMapZ(uz,..
|
3

It depends on which values exactly your keys take, and which lookup patterns you are using. However, on more or less evenly spread keys with random access usage, std::unordered_map lookup and insertion should be quite a bit faster than std::map.

I can reproduce your results on GCC 4.8 but not on Clang 3.4. The differences are sufficiently large that even a skewed benchmark shouldn’t make that much of a difference: std::unordered_map is orders of magnitude slower than std::map. This could be a bug in the GCC c++stdlib implementation, or in g++’ optimiser – although it might still be an artefact of the benchmark – a better microbenchmark tool to assess these differences is Nonius.

Improve this answer

11 Comments

Am not doing any lookup as of now. just testing how much time adding 100k elements take. just 100k calls to map[X.id] = X;There might be duplicate keys though in the 100k Xs.
@NaveenSharma Every insertion is also a lookup. And your comment does not give enough details. Post the complete benchmark code.
can it be an issue of passing by address &.
@NaveenSharma No, because you’re not passing by address, you’re passing by reference. You are not compiling with optimisations enabled, though. This invalidates the benchmark. On my machine, both tests finish immediately. In addition, you are benchmarking tons of other operations besides the insertion – this will skew the benchmark sufficiently to invalidate it entirely. Nevertheless, if I increase the iterations fourfold, unordered_map is twice as fast as map.
Are you executing this program on an abacus?
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.