Is unordered map slower than map in c++?

Question

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.

Answer 1

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.

Answer 2

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.