[2/2] Fix complexity of map insert_or_assign with a hint.

[Mordante]

Summary

In bug 38722 Mitsuru Kariya reported the map operations insert_or_assign with a hint violates the complexity requirement. The function no longer uses a lower_bound, which caused the wrong complexity.

This fixes bug 38722.

Benchmarked with:
Run on (4 X 3400 MHz CPU s)
CPU Caches:
  L1 Data 32K (x4)
  L1 Instruction 32K (x4)
  L2 Unified 256K (x4)
  L3 Unified 6144K (x1)


Timing before:
-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            6.99 ns         6.98 ns    121900000
BM_InsertAssignHint_MapSize=100_ExistingElement           14.4 ns         14.4 ns     48800000
BM_InsertAssignHint_MapSize=1000_ExistingElement          43.0 ns         43.0 ns     17000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         56.5 ns         56.5 ns     11000000
BM_InsertAssignHint_MapSize=100000_ExistingElement         116 ns          116 ns      6000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement        154 ns          154 ns      5000000
BM_InsertAssignHint_MapSize=10_NewElement                 28.4 ns         28.4 ns     24690000
BM_InsertAssignHint_MapSize=100_NewElement                72.4 ns         72.4 ns     12600000
BM_InsertAssignHint_MapSize=1000_NewElement               74.3 ns         74.3 ns      9000000
BM_InsertAssignHint_MapSize=10000_NewElement              92.4 ns         92.4 ns      7000000
BM_InsertAssignHint_MapSize=100000_NewElement              151 ns          151 ns      5000000
BM_InsertAssignHint_MapSize=1000000_NewElement             194 ns          194 ns      4000000

-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            6.96 ns         6.96 ns    123030000
BM_InsertAssignHint_MapSize=100_ExistingElement           14.5 ns         14.4 ns     48600000
BM_InsertAssignHint_MapSize=1000_ExistingElement          43.0 ns         43.0 ns     17000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         56.7 ns         56.7 ns     11000000
BM_InsertAssignHint_MapSize=100000_ExistingElement         116 ns          116 ns      6000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement        153 ns          153 ns      5000000
BM_InsertAssignHint_MapSize=10_NewElement                 28.6 ns         28.6 ns     24600000
BM_InsertAssignHint_MapSize=100_NewElement                76.2 ns         76.2 ns     12600000
BM_InsertAssignHint_MapSize=1000_NewElement               74.6 ns         74.6 ns      9000000
BM_InsertAssignHint_MapSize=10000_NewElement              92.4 ns         92.4 ns      7000000
BM_InsertAssignHint_MapSize=100000_NewElement              151 ns          151 ns      4000000
BM_InsertAssignHint_MapSize=1000000_NewElement             194 ns          194 ns      3000000

-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            6.96 ns         6.96 ns    122840000
BM_InsertAssignHint_MapSize=100_ExistingElement           14.5 ns         14.5 ns     49000000
BM_InsertAssignHint_MapSize=1000_ExistingElement          43.0 ns         43.0 ns     17000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         56.4 ns         56.4 ns     11000000
BM_InsertAssignHint_MapSize=100000_ExistingElement         116 ns          116 ns      6000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement        154 ns          154 ns      4000000
BM_InsertAssignHint_MapSize=10_NewElement                 28.3 ns         28.3 ns     24830000
BM_InsertAssignHint_MapSize=100_NewElement                76.1 ns         76.1 ns     12500000
BM_InsertAssignHint_MapSize=1000_NewElement               74.7 ns         74.7 ns      9000000
BM_InsertAssignHint_MapSize=10000_NewElement              92.8 ns         92.8 ns      7000000
BM_InsertAssignHint_MapSize=100000_NewElement              150 ns          150 ns      4000000
BM_InsertAssignHint_MapSize=1000000_NewElement             197 ns          197 ns      3000000

Timing after:
-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            4.30 ns         4.30 ns    167310000
BM_InsertAssignHint_MapSize=100_ExistingElement           8.18 ns         8.18 ns     85400000
BM_InsertAssignHint_MapSize=1000_ExistingElement          8.11 ns         8.11 ns     87000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         8.11 ns         8.11 ns     87000000
BM_InsertAssignHint_MapSize=100000_ExistingElement        8.28 ns         8.28 ns     83000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement       8.63 ns         8.62 ns     82000000
BM_InsertAssignHint_MapSize=10_NewElement                 23.5 ns         23.4 ns     30110000
BM_InsertAssignHint_MapSize=100_NewElement                63.2 ns         63.0 ns     10000000
BM_InsertAssignHint_MapSize=1000_NewElement               46.7 ns         46.6 ns     15000000
BM_InsertAssignHint_MapSize=10000_NewElement              41.8 ns         41.7 ns     13000000
BM_InsertAssignHint_MapSize=100000_NewElement             42.3 ns         42.1 ns     15000000
BM_InsertAssignHint_MapSize=1000000_NewElement            47.9 ns         47.7 ns     14000000

-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            4.30 ns         4.30 ns    167500000
BM_InsertAssignHint_MapSize=100_ExistingElement           8.39 ns         8.39 ns     84800000
BM_InsertAssignHint_MapSize=1000_ExistingElement          8.14 ns         8.15 ns     86000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         8.12 ns         8.12 ns     87000000
BM_InsertAssignHint_MapSize=100000_ExistingElement        8.37 ns         8.37 ns     85000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement       8.61 ns         8.61 ns     82000000
BM_InsertAssignHint_MapSize=10_NewElement                 23.4 ns         23.4 ns     29830000
BM_InsertAssignHint_MapSize=100_NewElement                66.8 ns         66.8 ns     10000000
BM_InsertAssignHint_MapSize=1000_NewElement               46.6 ns         46.6 ns     14000000
BM_InsertAssignHint_MapSize=10000_NewElement              41.3 ns         41.4 ns     14000000
BM_InsertAssignHint_MapSize=100000_NewElement             41.7 ns         41.7 ns     14000000
BM_InsertAssignHint_MapSize=1000000_NewElement            48.5 ns         48.5 ns     11000000

-----------------------------------------------------------------------------------------------
Benchmark                                                    Time             CPU   Iterations
-----------------------------------------------------------------------------------------------
BM_InsertAssignHint_MapSize=10_ExistingElement            4.27 ns         4.27 ns    166850000
BM_InsertAssignHint_MapSize=100_ExistingElement           8.53 ns         8.53 ns     85100000
BM_InsertAssignHint_MapSize=1000_ExistingElement          8.31 ns         8.31 ns     86000000
BM_InsertAssignHint_MapSize=10000_ExistingElement         8.17 ns         8.18 ns     86000000
BM_InsertAssignHint_MapSize=100000_ExistingElement        8.73 ns         8.73 ns     82000000
BM_InsertAssignHint_MapSize=1000000_ExistingElement       8.98 ns         8.98 ns     81000000
BM_InsertAssignHint_MapSize=10_NewElement                 24.6 ns         24.6 ns     29720000
BM_InsertAssignHint_MapSize=100_NewElement                71.9 ns         71.9 ns     10000000
BM_InsertAssignHint_MapSize=1000_NewElement               46.1 ns         46.1 ns     13000000
BM_InsertAssignHint_MapSize=10000_NewElement              41.7 ns         41.8 ns     14000000
BM_InsertAssignHint_MapSize=100000_NewElement             42.1 ns         42.1 ns     13000000
BM_InsertAssignHint_MapSize=1000000_NewElement            48.6 ns         48.6 ns     13000000

[mclow.lists]

You're going to need several tests here.

Hints that are correct.
Hints that are wrong.
Hints that are end() <-- All the tests we have pass end(), as far as I can tell.
See "test/std/containers/associative/map/map.modifiers/insert_node_type_hint.pass.cpp"

[Mordante]

It seems there already is a unit test "test/std/containers/associative/map/map.modifiers/insert_or_assign.pass.cpp". I'll add extra tests to this file.

[ldionne]

@Mordante Ping! I'm willing to look at this with added tests.

[Mordante]

Thanks for looking into these patches!

I thought I already had added the unit test, but seem I forgot to update the diff.

[Mordante]

Added unit tests as requested and rebased against master.

[ldionne]

libcxx/include/map

1274

I think it would be better if __emplace_hint_unique_key_args returned a pair of bool and iterator, like __emplace_unique_key_args does. We could then reuse it to implement this functionality. WDYT?

[Mordante]

I'll rebase the patch and then have a look at your suggestion.

[Mordante]

libcxx/include/map

1274

I think it could work something like:

auto [__r, __inserted] = __tree_.__emplace_hint_unique_key_args(     
    __h.__i_, __k, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));           
  
if (!__inserted)                                                          
  __r->__get_value().second = _VSTD::forward<_Vp>(__v);              

return __r;

I'm not fond of using __k and moving it in the same function call, but try_emplace(key_type&& __k, _Args&&... __args) uses the same method for the key. Since it's safe here and I see no reason why it would become unsafe in the future I don't mind.

I like that this approach keeps the header file smaller so I'll test this approach further.

[ldionne]

libcxx/include/map

1274

Excellent. I like that it avoids code duplication, but I agree the move is a bit sneaky. Let's use that approach, though.

[Mordante]

Improves the code based on @ldionne's suggestion

• __emplace_hint_unique_key_args returns a pair
• insert_or_assign uses __emplace_hint_unique_key_args internally
• removes the now unused code from the initial patch
• removes unused #ifdefs for __emplace_hint_unique_key_args, they seem a copy paste and the code isn't used for C++03

[ldionne]

This looks really good, thanks! Just one comment about structured bindings, and I think we're good to go.

libcxx/include/map

1275

You can't use structured bindings here, this is supposed to work before C++17.

[Mordante]

libcxx/include/map

1275

I used the structured bindings since the code is ifdef'ed at line 1204 with #if _LIBCPP_STD_VER > 14 so I assumed it wasn't intended to be used prior to C++17. But no problem to use a pair.

[ldionne]

LGTM, please:

1. Reduce your commit message to get rid of the benchmark output
2. Run: for std in c++03 c++11 c++14 c++17 c++2a; do <build-dir>/bin/llvm-lit -sv libcxx/test/std/containers/associative/map --param std=$std; done to make sure it all works

And the commit. Yay!

libcxx/include/map

1275

Oh, my apologies. In that case that LGTM.

[Mordante]

Thanks for the review!

In D62779#2279968, @ldionne wrote:

LGTM, please:

2. Run: for std in c++03 c++11 c++14 c++17 c++2a; do <build-dir>/bin/llvm-lit -sv libcxx/test/std/containers/associative/map --param std=$std; done to make sure it all works

Thanks for this hint, clang tests al required C++ versions without overriding the std. It turns out the removed C++03 was required so I restored it before committing.

libcxx/include/__tree

#if _LIBCPP_STD_VER > 14
 
 
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(key_type const&);
     template <class _NodeHandle>
     _LIBCPP_INLINE_VISIBILITY
     _NodeHandle __node_handle_extract(const_iterator);
+
+
+    template <class _Vp>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __insert_or_assign_hint(const_iterator __p, key_type const& __k, _Vp&& __v);
+    template <class _Vp>
+    _LIBCPP_INLINE_VISIBILITY
+    iterator __insert_or_assign_hint(const_iterator __p, key_type&& __k, _Vp&& __v);
 #endif
 
     iterator erase(const_iterator __p);
     iterator erase(const_iterator __f, const_iterator __l);
     template <class _Key>
         size_type __erase_unique(const _Key& __k);
     template <class _Key>
         size_type __erase_multi(const _Key& __k);
for (typename _Tree::iterator __i = __source.begin();
             __parent, _NodeTypes::__get_key(__src_ptr->__value_));
         ++__i;
         __source.__remove_node_pointer(__src_ptr);
         __insert_node_at(__parent, __child,
                          static_cast<__node_base_pointer>(__src_ptr));
     }
 }
 
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Vp>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::
+    __insert_or_assign_hint(const_iterator __p, key_type const& __k, _Vp&& __v)
+{
+    __parent_pointer __parent;
+    __node_base_pointer __dummy;
+    __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
+    __node_pointer __r = static_cast<__node_pointer>(__child);
+    if (__child == nullptr)
+    {
+        __node_holder __h = __construct_node(__k, _VSTD::forward<_Vp>(__v));
+        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+        __r = __h.release();
+    }
+    else
+        iterator(__r)->__get_value().second = std::forward<_Vp>(__v);
+    return iterator(__r);
+}
+
+template <class _Tp, class _Compare, class _Allocator>
+template <class _Vp>
+_LIBCPP_INLINE_VISIBILITY
+typename __tree<_Tp, _Compare, _Allocator>::iterator
+__tree<_Tp, _Compare, _Allocator>::
+    __insert_or_assign_hint(const_iterator __p, key_type && __k, _Vp&& __v)
+{
+    __parent_pointer __parent;
+    __node_base_pointer __dummy;
+    __node_base_pointer& __child = __find_equal(__p, __parent, __dummy, __k);
+    __node_pointer __r = static_cast<__node_pointer>(__child);
+    if (__child == nullptr)
+    {
+        __node_holder __h = __construct_node(_VSTD::forward<key_type>(__k), _VSTD::forward<_Vp>(__v));
+        __insert_node_at(__parent, __child, static_cast<__node_base_pointer>(__h.get()));
+        __r = __h.release();
+    }
+    else
+        iterator(__r)->__get_value().second = std::forward<_Vp>(__v);
+    return iterator(__r);
+}
 #endif  // _LIBCPP_STD_VER > 14
 
 template <class _Tp, class _Compare, class _Allocator>
 typename __tree<_Tp, _Compare, _Allocator>::iterator
 __tree<_Tp, _Compare, _Allocator>::erase(const_iterator __p)
 {
     __node_pointer __np = __p.__get_np();
     iterator __r = __remove_node_pointer(__np);

libcxx/include/map

template <class _Vp>
             return _VSTD::make_pair(__p, false);
         }
         return _VSTD::make_pair(emplace_hint(__p, _VSTD::move(__k), _VSTD::forward<_Vp>(__v)), true);
     }
 
     template <class _Vp>
         _LIBCPP_INLINE_VISIBILITY
         iterator insert_or_assign(const_iterator __h, const key_type& __k, _Vp&& __v)
-     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-        {
-            __p->second = _VSTD::forward<_Vp>(__v);
-            return __p;
-        }
-        return emplace_hint(__h, __k, _VSTD::forward<_Vp>(__v));
-     }
-
+         return __tree_.__insert_or_assign_hint(__h.__i_, __k,  _VSTD::forward<_Vp>(__v));
     template <class _Vp>
         _LIBCPP_INLINE_VISIBILITY
         iterator insert_or_assign(const_iterator __h, key_type&& __k, _Vp&& __v)
-     {
-        iterator __p = lower_bound(__k);
-        if ( __p != end() && !key_comp()(__k, __p->first))
-        {
-            __p->second = _VSTD::forward<_Vp>(__v);
-            return __p;
-        }
-        return emplace_hint(__h, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
-     }
+       return __tree_.__insert_or_assign_hint(__h.__i_, _VSTD::move(__k), _VSTD::forward<_Vp>(__v));
 
 #endif // _LIBCPP_STD_VER > 14
 
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(const_iterator __p) {return __tree_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY
     iterator erase(iterator __p)       {return __tree_.erase(__p.__i_);}
     _LIBCPP_INLINE_VISIBILITY

libcxx/test/std/containers/associative/map/map.modifiers/insert_or_assign.pass.cpp

int main(int, char**)
         assert(r->second.get() == 3);  // value
 
         Moveable mv2(5, 5.0);
         r = m.insert_or_assign(it, 3, std::move(mv2));
         assert(m.size() == 11);
         assert(mv2.moved());           // was moved from
         assert(r->first        == 3);  // key
         assert(r->second.get() == 5);  // value
+
+        // wrong hint: begin()
+        Moveable mv3(7, 7.0);
+        r = m.insert_or_assign(m.begin(), 4, std::move(mv3));
+        assert(m.size() == 11);
+        assert(mv3.moved());           // was moved from
+        assert(r->first        == 4);  // key
+        assert(r->second.get() == 7);  // value
+
+        Moveable mv4(9, 9.0);
+        r = m.insert_or_assign(m.begin(), 5, std::move(mv4));
+        assert(m.size() == 12);
+        assert(mv4.moved());           // was moved from
+        assert(r->first        == 5);  // key
+        assert(r->second.get() == 9);  // value
+
+        // wrong hint: end()
+        Moveable mv5(11, 11.0);
+        r = m.insert_or_assign(m.end(), 6, std::move(mv5));
+        assert(m.size() == 12);
+        assert(mv5.moved());           // was moved from
+        assert(r->first        == 6);  // key
+        assert(r->second.get() == 11); // value
+
+        Moveable mv6(13, 13.0);
+        r = m.insert_or_assign(m.end(), 7, std::move(mv6));
+        assert(m.size() == 13);
+        assert(mv6.moved());           // was moved from
+        assert(r->first        == 7);  // key
+        assert(r->second.get() == 13); // value
+
+        // wrong hint: third element
+        Moveable mv7(15, 15.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), 8, std::move(mv7));
+        assert(m.size() == 13);
+        assert(mv7.moved());           // was moved from
+        assert(r->first        == 8);  // key
+        assert(r->second.get() == 15); // value
+
+        Moveable mv8(17, 17.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), 9, std::move(mv8));
+        assert(m.size() == 14);
+        assert(mv8.moved());           // was moved from
+        assert(r->first        == 9);  // key
+        assert(r->second.get() == 17); // value
     }
     { // iterator insert_or_assign(const_iterator hint, key_type&& k, M&& obj);
         typedef std::map<Moveable, Moveable> M;
         M m;
         M::iterator r;
         for ( int i = 0; i < 20; i += 2 )
             m.emplace ( Moveable(i, (double) i), Moveable(i+1, (double) i+1));
         assert(m.size() == 10);
int main(int, char**)
         Moveable mvkey2(3, 3.0);
         Moveable mv2(5, 5.0);
         r = m.insert_or_assign(it, std::move(mvkey2), std::move(mv2));
         assert(m.size() == 11);
         assert(mv2.moved());           // was moved from
         assert(mvkey2.moved());        // was moved from
         assert(r->first.get()  == 3);  // key
         assert(r->second.get() == 5);  // value
+
+        // wrong hint: begin()
+        Moveable mvkey3(6, 6.0);
+        Moveable mv3(8, 8.0);
+        r = m.insert_or_assign(m.begin(), std::move(mvkey3), std::move(mv3));
+        assert(m.size() == 11);
+        assert(mv3.moved());           // was moved from
+        assert(!mvkey3.moved());       // was not moved from
+        assert(r->first == mvkey3);    // key
+        assert(r->second.get() == 8);  // value
+
+        Moveable mvkey4(7, 7.0);
+        Moveable mv4(9, 9.0);
+        r = m.insert_or_assign(m.begin(), std::move(mvkey4), std::move(mv4));
+        assert(m.size() == 12);
+        assert(mv4.moved());           // was moved from
+        assert(mvkey4.moved());        // was moved from
+        assert(r->first.get()  == 7);  // key
+        assert(r->second.get() == 9);  // value
+
+        // wrong hint: end()
+        Moveable mvkey5(8, 8.0);
+        Moveable mv5(10, 10.0);
+        r = m.insert_or_assign(m.end(), std::move(mvkey5), std::move(mv5));
+        assert(m.size() == 12);
+        assert(mv5.moved());           // was moved from
+        assert(!mvkey5.moved());       // was not moved from
+        assert(r->first == mvkey5);    // key
+        assert(r->second.get() == 10); // value
+
+        Moveable mvkey6(9, 9.0);
+        Moveable mv6(11, 11.0);
+        r = m.insert_or_assign(m.end(), std::move(mvkey6), std::move(mv6));
+        assert(m.size() == 13);
+        assert(mv6.moved());           // was moved from
+        assert(mvkey6.moved());        // was moved from
+        assert(r->first.get()  == 9);  // key
+        assert(r->second.get() == 11); // value
+
+        // wrong hint: third element
+        Moveable mvkey7(10, 10.0);
+        Moveable mv7(12, 12.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), std::move(mvkey7), std::move(mv7));
+        assert(m.size() == 13);
+        assert(mv7.moved());           // was moved from
+        assert(!mvkey7.moved());       // was not moved from
+        assert(r->first == mvkey7);    // key
+        assert(r->second.get() == 12); // value
+
+        Moveable mvkey8(11, 11.0);
+        Moveable mv8(13, 13.0);
+        r = m.insert_or_assign(std::next(m.begin(), 2), std::move(mvkey8), std::move(mv8));
+        assert(m.size() == 14);
+        assert(mv8.moved());           // was moved from
+        assert(mvkey8.moved());        // was moved from
+        assert(r->first.get()  == 11); // key
+        assert(r->second.get() == 13); // value
     }
 
   return 0;
 }