std::map insert && overload causes copy

Question

Looking at this interesting talk:

CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step”

He mentions around minute 38:32 that

void Benchmark_Slow(int iters) {
    std::unordered_map<string, int> m;
    std::pair<const string, int> p = {};
    while (iters--) m.insert(p)
}

is ~2x slower than the following variation

void Benchmark_Fast(int iters) {
    std::unordered_map<string, int> m;
    const std::pair<const string, int> p = {};
    while (iters--) m.insert(p)
}

I am still thinking about why the && overload (1) would be selected.

• std::pair<iterator,bool> insert( value_type&& value ); (1)

• std::pair<iterator,bool> insert( const value_type& value ); (3)

where value_typeis std::pair<const Key, T>.

After all, we are not moving the values, so in my understanding, the expression p should be an lvalue and not an x/prvalue, is that right? Can somebody enlighten me?

Answer 1

You don't take the problematic overloads:

std::pair<iterator,bool> insert(const value_type& value); // (1)

template< class P >
std::pair<iterator,bool> insert(P&& value); // (2)

P deduced as value_type&.

Answer 2

1. The template overload is called (overload (2) on cppreference)
2. The template overload is equivalent to emplace
3. emplace is not slower that insert and is faster in general case, but...

But, emplace allows for one abuse and that is when you repeatedly try to insert the same key. And the benchmark does exactly that (note that while). I'd say it's just a benchmark that show a behavior when you are deliberately shooting yourself in the foot. In the real world i don't think one would do that via emplace or insert.

In C++17 this has been fixed in 1 way that requires to modify your code:

1. try_emplace function https://isocpp.org/files/papers/n4279.html