CODEWITHSUNDEEP
c++stlstdmapvalue-categories
user823255
user823255

Reputation: 1010

std::map insert && overload causes copy

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.

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?

Upvotes: 1

Views: 772

Answers (2)

dimm
dimm

Reputation: 1798

  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

Upvotes: 0

Jarod42
Jarod42

Reputation: 217145

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&.

Upvotes: 2

Related Questions