PR 95079 Improve unordered_map insert_or_assign and try_emplace

Message ID 45eeed75-e0a0-d33c-8edc-92c0cba55d1c@gmail.com
State New
Headers show
Series
  • PR 95079 Improve unordered_map insert_or_assign and try_emplace
Related show

Commit Message

Kewen.Lin via Gcc-patches May 29, 2020, 8:18 a.m.
I added a try_emplace at the underlying _Hashtable level which I use in 
both insert_or_assign and try_emplace.

I am not making any use of the hint for the moment. I'll review this 
once my other hashtable patches are being validated.

             PR libstdc++/95079
             * include/bits/hashtable_policy.h 
(_Insert_base<>::try_emplace): New.
             * include/bits/unordered_map.h 
(unordered_map<>::try_emplace): Adapt.
             (unordered_map<>::insert_or_assign): Adapt.

Tested under Linux x86_64.

Ok to commit ?

François

Comments

Kewen.Lin via Gcc-patches May 29, 2020, 9:53 a.m. | #1
On 29/05/20 10:18 +0200, François Dumont via Libstdc++ wrote:
>I added a try_emplace at the underlying _Hashtable level which I use 

>in both insert_or_assign and try_emplace.

>

>I am not making any use of the hint for the moment. I'll review this 

>once my other hashtable patches are being validated.

>

>            PR libstdc++/95079

>            * include/bits/hashtable_policy.h 

>(_Insert_base<>::try_emplace): New.

>            * include/bits/unordered_map.h 

>(unordered_map<>::try_emplace): Adapt.

>            (unordered_map<>::insert_or_assign): Adapt.

>

>Tested under Linux x86_64.

>

>Ok to commit ?

>

>François

>


>diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h

>index ef120134914..5c6c81bcf21 100644

>--- a/libstdc++-v3/include/bits/hashtable_policy.h

>+++ b/libstdc++-v3/include/bits/hashtable_policy.h

>@@ -848,6 +848,28 @@ namespace __detail

> 	return __h._M_insert(__hint, __v, __node_gen, __unique_keys());

>       }

> 

>+      template <typename _KType, typename... _Args>


Our coding conventions say no space in "template <" here.


Otherwise looks great, thanks.

OK for master. Please be aware of the new ChangeLog policy I forwarded
to the mailing list the other day.

Patch

diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index ef120134914..5c6c81bcf21 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -848,6 +848,28 @@  namespace __detail
 	return __h._M_insert(__hint, __v, __node_gen, __unique_keys());
       }
 
+      template <typename _KType, typename... _Args>
+	std::pair<iterator, bool>
+	try_emplace(const_iterator, _KType&& __k, _Args&&... __args)
+	{
+	  __hashtable& __h = _M_conjure_hashtable();
+	  auto __code = __h._M_hash_code(__k);
+	  std::size_t __bkt = __h._M_bucket_index(__k, __code);
+	  if (__node_type* __node = __h._M_find_node(__bkt, __k, __code))
+	    return { iterator(__node), false };
+
+	  typename __hashtable::_Scoped_node __node {
+	    &__h,
+	    std::piecewise_construct,
+	    std::forward_as_tuple(std::forward<_KType>(__k)),
+	    std::forward_as_tuple(std::forward<_Args>(__args)...)
+	    };
+	  auto __it
+	    = __h._M_insert_unique_node(__k, __bkt, __code, __node._M_node);
+	  __node._M_node = nullptr;
+	  return { __it, true };
+	}
+
       void
       insert(initializer_list<value_type> __l)
       { this->insert(__l.begin(), __l.end()); }
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index 0071d62e462..33f632ddb79 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -469,17 +469,7 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	pair<iterator, bool>
 	try_emplace(const key_type& __k, _Args&&... __args)
 	{
-          iterator __i = find(__k);
-          if (__i == end())
-            {
-              __i = emplace(std::piecewise_construct,
-                            std::forward_as_tuple(__k),
-                            std::forward_as_tuple(
-                              std::forward<_Args>(__args)...))
-                .first;
-              return {__i, true};
-            }
-          return {__i, false};
+	  return _M_h.try_emplace(cend(), __k, std::forward<_Args>(__args)...);
 	}
 
       // move-capable overload
@@ -487,17 +477,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	pair<iterator, bool>
 	try_emplace(key_type&& __k, _Args&&... __args)
 	{
-          iterator __i = find(__k);
-          if (__i == end())
-            {
-              __i = emplace(std::piecewise_construct,
-                            std::forward_as_tuple(std::move(__k)),
-                            std::forward_as_tuple(
-                              std::forward<_Args>(__args)...))
-                .first;
-              return {__i, true};
-            }
-          return {__i, false};
+	  return _M_h.try_emplace(cend(), std::move(__k),
+				  std::forward<_Args>(__args)...);
 	}
 
       /**
@@ -533,13 +514,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	try_emplace(const_iterator __hint, const key_type& __k,
 		    _Args&&... __args)
 	{
-          iterator __i = find(__k);
-          if (__i == end())
-            __i = emplace_hint(__hint, std::piecewise_construct,
-                               std::forward_as_tuple(__k),
-                               std::forward_as_tuple(
-                                 std::forward<_Args>(__args)...));
-          return __i;
+	  return _M_h.try_emplace(__hint, __k,
+				  std::forward<_Args>(__args)...).first;
 	}
 
       // move-capable overload
@@ -547,13 +523,8 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	iterator
 	try_emplace(const_iterator __hint, key_type&& __k, _Args&&... __args)
 	{
-          iterator __i = find(__k);
-          if (__i == end())
-            __i = emplace_hint(__hint, std::piecewise_construct,
-                               std::forward_as_tuple(std::move(__k)),
-                               std::forward_as_tuple(
-                                 std::forward<_Args>(__args)...));
-          return __i;
+	  return _M_h.try_emplace(__hint, std::move(__k),
+				  std::forward<_Args>(__args)...).first;
 	}
 #endif // C++17
 
@@ -681,17 +652,11 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	pair<iterator, bool>
 	insert_or_assign(const key_type& __k, _Obj&& __obj)
 	{
-          iterator __i = find(__k);
-          if (__i == end())
-            {
-              __i = emplace(std::piecewise_construct,
-                            std::forward_as_tuple(__k),
-                            std::forward_as_tuple(std::forward<_Obj>(__obj)))
-                .first;
-              return {__i, true};
-            }
-          (*__i).second = std::forward<_Obj>(__obj);
-          return {__i, false};
+	  auto __ret = _M_h.try_emplace(cend(), __k,
+					std::forward<_Obj>(__obj));
+	  if (!__ret.second)
+	    __ret.first->second = std::forward<_Obj>(__obj);
+	  return __ret;
 	}
 
       // move-capable overload
@@ -699,17 +664,11 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	pair<iterator, bool>
 	insert_or_assign(key_type&& __k, _Obj&& __obj)
 	{
-          iterator __i = find(__k);
-          if (__i == end())
-            {
-              __i = emplace(std::piecewise_construct,
-                            std::forward_as_tuple(std::move(__k)),
-                            std::forward_as_tuple(std::forward<_Obj>(__obj)))
-                .first;
-              return {__i, true};
-            }
-          (*__i).second = std::forward<_Obj>(__obj);
-          return {__i, false};
+	  auto __ret = _M_h.try_emplace(cend(), std::move(__k),
+					std::forward<_Obj>(__obj));
+	  if (!__ret.second)
+	    __ret.first->second = std::forward<_Obj>(__obj);
+	  return __ret;
 	}
 
       /**
@@ -743,16 +702,10 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	insert_or_assign(const_iterator __hint, const key_type& __k,
 			 _Obj&& __obj)
 	{
-          iterator __i = find(__k);
-          if (__i == end())
-            {
-              return emplace_hint(__hint, std::piecewise_construct,
-                                  std::forward_as_tuple(__k),
-                                  std::forward_as_tuple(
-                                    std::forward<_Obj>(__obj)));
-            }
-          (*__i).second = std::forward<_Obj>(__obj);
-          return __i;
+	  auto __ret = _M_h.try_emplace(__hint, __k, std::forward<_Obj>(__obj));
+	  if (!__ret.second)
+	    __ret.first->second = std::forward<_Obj>(__obj);
+	  return __ret.first;
 	}
 
       // move-capable overload
@@ -760,16 +713,11 @@  _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	iterator
 	insert_or_assign(const_iterator __hint, key_type&& __k, _Obj&& __obj)
 	{
-          iterator __i = find(__k);
-          if (__i == end())
-            {
-              return emplace_hint(__hint, std::piecewise_construct,
-                                  std::forward_as_tuple(std::move(__k)),
-                                  std::forward_as_tuple(
-                                    std::forward<_Obj>(__obj)));
-            }
-          (*__i).second = std::forward<_Obj>(__obj);
-          return __i;
+	  auto __ret = _M_h.try_emplace(__hint, std::move(__k),
+					std::forward<_Obj>(__obj));
+	  if (!__ret.second)
+	    __ret.first->second = std::forward<_Obj>(__obj);
+	  return __ret.first;
 	}
 #endif