defect in [unord.map.modifiers] 2+4

[Alkis Evlogimenos]

template <class P>
pair<iterator, bool> insert(P&& obj);  // (1)

​

http://eel.is/c++draft/unord.map.modifiers#1

Effects: Equivalent to: return emplace(std::forward<P>(obj));

http://eel.is/c++draft/unord.map.modifiers#2

Remarks: This signature shall not participate in overload resolution unless std::is_constructible_v<value_type, P&&> is true.

Also note the other two overloads of insert:

pair<iterator, bool> insert(const value_type& obj);  // (2)
pair<iterator, bool> insert(value_type&& obj);       // (3)

​

And the semantics of emplace:

I couldn't find the requirement in the standard but in all implementations emplace constructs a value_type from the args and then attempts to insert it into the container. That is, if emplace is called with a resource handle by rvalue, there will be no resource leak, irrespective of if the emplace resulted in an insertion or not.

To illustrate the DR, consider the following benchmarks:

using M = std::unordered_map<int, int>;

void BM_Fast(int iters) {
  M m;
  const M::value_type p = {};
  while (iters--) m.insert(p);
}

void BM_Slow(int iters) {
  M m;
  M::value_type p = {};  // not const
  while (iters--) m.insert(p);
}

​

Both implementations I have tried follow the standard and exhibit a big difference in performance; ~10x between BM_Fast and BM_Slow.

The reason is because given a const value_type&, overload (2) is picked and given a value_type&, overload (1) is picked. As noted above emplace() has very different performance characteristics compared to insert().

The suggested fix is to amend http://eel.is/c++draft/unord.map.modifiers#2 to read:

Remarks: This signature shall not participate in overload resolution unless unless std::is_same_v<value_type, std::decay<P>> is false.

[Nicol Bolas]

On Saturday, November 26, 2016 at 5:39:13 PM UTC-5, Alkis Evlogimenos wrote:

The suggested fix is to amend http://eel.is/c++draft/unord.map.modifiers#2 to read:

Remarks: This signature shall not participate in overload resolution unless unless std::is_same_v<value_type, std::decay<P>> is false.

I think you have too many negatives. Perhaps you mean "This signature shall not participate in overload resolution if std::is_same_v<value_type, std::decay<P>> is true".

That being said, I think this is no longer needed. C++17 adds an explicit `value_type&&` form of `insert` for move-insertion (the signature is there, but the details are explained in a different section). And since that one doesn't use template argument deduction, it should win out in overload resolution without having to explicitly disallow the forwarding version. So the wording change is unnecessary.

Those are new to C++17, so the compiler in question may not expose them yet.

[Alkis Evlogimenos (Άλκης Ευλογημένος)]

On Sun, Nov 27, 2016 at 3:29 AM, Nicol Bolas <jmck...@gmail.com> wrote:

I think you have too many negatives. Perhaps you mean "This signature shall not participate in overload resolution if std::is_same_v<value_type, std::decay<P>> is true".

This reads better thank you.

 

That being said, I think this is no longer needed. C++17 adds an explicit `value_type&&` form of `insert` for move-insertion (the signature is there, but the details are explained in a different section). And since that one doesn't use template argument deduction, it should win out in overload resolution without having to explicitly disallow the forwarding version. So the wording change is unnecessary.

The `value_type&&` form of insert will not be picked when we are passing an lvalue. The `insert(P&&)` overload will be picked instead (with a performance regression). What we want is for the `insert(const value_type&)` overload to be picked.

- alkis

Google Switzerland GmbH
Brandschenkestrasse 110,
Zurich, Switzerland
8002 Zurich

[Ville Voutilainen]

On 29 November 2016 at 15:44, 'Alkis Evlogimenos (Άλκης Ευλογημένος)'

via ISO C++ Standard - Discussion <std-dis...@isocpp.org> wrote:
>> That being said, I think this is no longer needed. C++17 adds an explicit
>> `value_type&&` form of `insert` for move-insertion (the signature is there,
>> but the details are explained in a different section). And since that one
>> doesn't use template argument deduction, it should win out in overload
>> resolution without having to explicitly disallow the forwarding version. So
>> the wording change is unnecessary.
>
>
> The `value_type&&` form of insert will not be picked when we are passing an
> lvalue. The `insert(P&&)` overload will be picked instead (with a
> performance regression). What we want is for the `insert(const value_type&)`
> overload to be picked.

Makes sense to me. I have forwarded this defect for LWG to consider;
if they support fixing it, I will send an issue submission.

[Alkis Evlogimenos (Άλκης Ευλογημένος)]

On Tue, Nov 29, 2016 at 3:21 PM, Ville Voutilainen <ville.vo...@gmail.com> wrote:

Makes sense to me. I have forwarded this defect for LWG to consider;
if they support fixing it, I will send an issue submission.

Thanks Ville.

Actually after more discussions on the matter I discovered this is not a defect per se. It turns out that it is ok for emplace() to not create a node and good implementations can do that depending on the arguments to emplace. If the argument is any pair, emplace can take the key perform the lookup and if the key exists, elide creating the node.

Cheers,

[Ville Voutilainen]

On 17 December 2016 at 17:13, 'Alkis Evlogimenos (Άλκης Ευλογημένος)'

via ISO C++ Standard - Discussion <std-dis...@isocpp.org> wrote:
>

> On Tue, Nov 29, 2016 at 3:21 PM, Ville Voutilainen
> <ville.vo...@gmail.com> wrote:
>>
>> Makes sense to me. I have forwarded this defect for LWG to consider;
>> if they support fixing it, I will send an issue submission.
>
>
> Thanks Ville.
>
> Actually after more discussions on the matter I discovered this is not a
> defect per se. It turns out that it is ok for emplace() to not create a node
> and good implementations can do that depending on the arguments to emplace.
> If the argument is any pair, emplace can take the key perform the lookup and
> if the key exists, elide creating the node.

Ah, thanks for reminding me to get back to this thread. Yes, there's
no reason why
the template overload needs to perform badly, the problem is in the
underlying implementation
rather than in the specification, and sfinaeing the template overloads
doesn't solve the problem.