Search code examples
c++moveunordered-maprvalue

Why is move assignment of unordered_map slow?


I am trying to understand how the move/rvalue assignment operator works. I know that it is largely implementation-specific, but assuming that move assignment in unordered_map works by only swapping the underlying data pointer or size attributes, I suppose it should be extremely fast?

This is the code that I tried to run:

#include <chrono>
#include <functional>
#include <iostream>
#include <memory>
#include <string>
#include <unordered_map>
using namespace std;
 
void time_it(function<void()> f)
{
    auto start = chrono::steady_clock::now();
    f();
    auto end = chrono::steady_clock::now();
    auto diff = end - start;
    cout << chrono::duration<double, milli>(diff).count() << " ms" << endl;
}
 
using umap = unordered_map<string, string>;
static const size_t MAP_SIZE = 1000000;
 
int main()
{
    umap m;
    for (int i = 0; i < MAP_SIZE; i++)
    {
        auto s = to_string(i);
        m[s] = s;
    }
 
    time_it([&]() {
        cout << "copy\n";
        auto c = m;
    });
    time_it([&]() {
        cout << "move\n";
        auto c = move(m);
    });
}

It returns:

copy
204.4 ms
move
98.568 ms

How come that the move assignment operator takes so long (~100 ms)?

I compiled using g++ test.cpp -O3. This is what my g++ -v returns:

Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=c:/mingw/bin/../libexec/gcc/mingw32/6.3.0/lto-wrapper.exe
Target: mingw32
Configured with: ../src/gcc-6.3.0/configure --build=x86_64-pc-linux-gnu --host=mingw32 --with-gmp=/mingw --with-mpfr=/mingw --with-mpc=/mingw --with-isl=/mingw --prefix=/mingw --disable-win32-registry --target=mingw32 --with-arch=i586 --enable-languages=c,c++,objc,obj-c++,fortran,ada --with-pkgversion='MinGW.org GCC-6.3.0-1' --enable-static --enable-shared --enable-threads --with-dwarf2 --disable-sjlj-exceptions --enable-version-specific-runtime-libs --with-libiconv-prefix=/mingw --with-libintl-prefix=/mingw --enable-libstdcxx-debug --with-tune=generic --enable-libgomp --disable-libvtv --enable-nls
Thread model: win32
gcc version 6.3.0 (MinGW.org GCC-6.3.0-1)

Solution

  • As MilesBudnek explained in his comment, I only counted the runtime for unordered_map destructor (i.e. the object c) inside my second time_it inner function.

    I changed it to:

        time_it([&]() mutable {
            cout << "copy\n";
            auto c = m;
            m = c;
        });
        time_it([&]() mutable {
            cout << "move\n";
            auto c = move(m);
            m = move(c);
        });
    

    to make the underlying object of c not getting deallocated, and now it says ~0.6 ms using -O0 to not let the compiler do undesirable stuff.

    Thanks everyone, really sorry for my mistakes in the post!