Test of performance bug with some std::map and std::unordered_map implementations

map_insert_test.cpp

// Test of performance bug with some std::map and std::unordered_map implementations
// see http://www.forwardscattering.org/post/37 for details.
//
// Written by Andrey Upadyshev https://github.com/oliora/ based on article's test code
#include <unordered_map>
#include <map>
#include <iostream>
#include <iomanip>
#include <chrono>
#include <type_traits>


namespace {
    // PerfTimer taken from https://gist.github.com/oliora/8c6f5b46d0e6121b593e3477c50ced37:
    
    // Floating seconds duration
    using fseconds = std::chrono::duration<double>;

    class PerfTimer
    {
    public:
        using clock = std::conditional<
            std::chrono::high_resolution_clock::is_steady,
            std::chrono::high_resolution_clock,
            std::chrono::steady_clock
        >::type;

        PerfTimer(): m_start(clock::now()) {}

        fseconds passed() const { return clock::now() - m_start; }

    private:
        clock::time_point m_start;
    };

    template<class Cont>
    inline void printResult(const fseconds& duration, const Cont& cont, const char *title)
    {
        std::cout << "time: " << std::setw(12) << std::setprecision(10) << duration.count() << "s, final cont size: " << std::setw(10) << cont.size() << " (" << title << ")\n";
    }
}

int main()
{
    const int N = 1000000; // Num insertions to attempt
    const int num_unique_keys = 65536;

    // Test insertion into an unordered_map, doing a find() before the insert().
    {
        PerfTimer timer;
        std::unordered_map<int, int> m;
        for(int i=0; i<N; ++i)
        {
            const int x = i % num_unique_keys;
            if(m.find(x) == m.end()) // If no such entry with given key:
                m.insert(std::make_pair(x, x));
        }
        printResult(timer.passed(), m, "std::unordered_map find then insert");
    }

    // Test insertion into an unordered_map, inserting directly without calling find() first.
    {
        PerfTimer timer;
        std::unordered_map<int, int> m;
        for(int i=0; i<N; ++i)
        {
            const int x = i % num_unique_keys;
            m.insert(std::make_pair(x, x));
        }
        printResult(timer.passed(), m, "std::unordered_map just insert");
    }

    // Test insertion into a map, doing a find() before the insert().
    {
        PerfTimer timer;
        std::map<int, int> m;
        for(int i=0; i<N; ++i)
        {
            const int x = i % num_unique_keys;
            if(m.find(x) == m.end()) // If no such entry with given key:
                m.insert(std::make_pair(x, x));
        }
        printResult(timer.passed(), m, "std::map find then insert");
    }

    // Test insertion into a map, inserting directly without calling find() first.
    {
        PerfTimer timer;
        std::map<int, int> m;
        for(int i=0; i<N; ++i)
        {
            const int x = i % num_unique_keys;
            m.insert(std::make_pair(x, x));
        }
        printResult(timer.passed(), m, "std::map just insert");
    }
}

Results for gcc4.9 on Linux:

time:  0.019020032s, final cont size:      65536 (std::unordered_map find then insert)
time:  0.044767412s, final cont size:      65536 (std::unordered_map just insert)
time:  0.093311802s, final cont size:      65536 (std::map find then insert)
time:  0.091446838s, final cont size:      65536 (std::map just insert)