public inbox for libstdc++@gcc.gnu.org
 help / color / mirror / Atom feed
From: Jonathan Wakely <jwakely@redhat.com>
To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org
Subject: [committed] libstdc++: Avoid unnecessary allocations in std::map insertions [PR92300]
Date: Thu,  9 Dec 2021 23:27:00 +0000	[thread overview]
Message-ID: <20211209232700.1568897-1-jwakely@redhat.com> (raw)

Tested powerpc64le-linux, pushed to trunk.


Inserting a pair<Key, Value> into a map<Key, Value> will allocate a new
node and construct a pair<const Key, Value> in the node, then check if
the Key is already present in the map. That is because pair<Key, Value>
is not the same type as the map's value_type. But it only differs in the
const-qualification on the Key, and so we should be able to do the
lookup directly, without allocating a new node. This avoids allocating
and then deallocating a node for the case where the key is already found
and nothing gets inserted.

We can take this optimization further and lookup the key directly for a
pair<Key, X>, pair<const Key, X>, pair<Key&, X> etc. for any X. A strict
reading of the standard says we can only do this when we know the
allocator won't do anything funky with the value when constructing a
pair<const Key, Value> from a slightly different type. Inserting that
type only requires the value_type to be Cpp17EmplaceInsertable into the
container, and that doesn't have any requirement that the value is
unchanged (unlike Cpp17CopyInsertable and Cpp17MoveInsertable). For that
reason, the optimization is only done for maps using std::allocator.

A similar optimization can be done for map.emplace(key, value) where the
first argument is similar to the key_type and so can be looked up
without allocating a new node and constructing a key_type.

Finally, both of the insert and emplace cases can use the same
optimization when key_type is a scalar type and some other scalar is
being passed as the insert/emplace argument. Converting from one scalar
type to another won't have surprising value-altering behaviour, and has
no side effects (unlike e.g. constructing a std::string from a const
char* argument, which might allocate).

We don't need to do this for std::multimap, because we always insert the
new node even if the key is already present. So there's no benefit to
doing the lookup before allocating the new node.

libstdc++-v3/ChangeLog:

	PR libstdc++/92300
	* include/bits/stl_map.h (insert(Pair&&), emplace(Args&&...)):
	Check whether the arguments can be looked up directly without
	constructing a temporary node first.
	* include/bits/stl_pair.h (__is_pair): Move to here, from ...
	* include/bits/uses_allocator_args.h (__is_pair): ... here.
	* testsuite/23_containers/map/modifiers/emplace/92300.cc: New test.
	* testsuite/23_containers/map/modifiers/insert/92300.cc: New test.
---
 libstdc++-v3/include/bits/stl_map.h           | 49 ++++++++++++++++++-
 libstdc++-v3/include/bits/stl_pair.h          |  9 ++++
 .../include/bits/uses_allocator_args.h        |  6 ---
 .../map/modifiers/emplace/92300.cc            | 36 ++++++++++++++
 .../map/modifiers/insert/92300.cc             | 38 ++++++++++++++
 5 files changed, 130 insertions(+), 8 deletions(-)
 create mode 100644 libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/92300.cc
 create mode 100644 libstdc++-v3/testsuite/23_containers/map/modifiers/insert/92300.cc

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index cc87f11fb11..658d5865138 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -154,6 +154,13 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 
       typedef __gnu_cxx::__alloc_traits<_Pair_alloc_type> _Alloc_traits;
 
+#if __cplusplus >= 201703L
+      template<typename _Up, typename _Vp = remove_reference_t<_Up>>
+	static constexpr bool __usable_key
+	  = __or_v<is_same<const _Vp, const _Key>,
+		   __and_<is_scalar<_Vp>, is_scalar<_Key>>>;
+#endif
+
     public:
       // many of these are specified differently in ISO, but the following are
       // "functionally equivalent"
@@ -574,7 +581,27 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
       template<typename... _Args>
 	std::pair<iterator, bool>
 	emplace(_Args&&... __args)
-	{ return _M_t._M_emplace_unique(std::forward<_Args>(__args)...); }
+	{
+#if __cplusplus >= 201703L
+	  if constexpr (sizeof...(_Args) == 2)
+	    if constexpr (is_same_v<allocator_type, allocator<value_type>>)
+	      {
+		auto&& [__a, __v] = pair<_Args&...>(__args...);
+		if constexpr (__usable_key<decltype(__a)>)
+		  {
+		    const key_type& __k = __a;
+		    iterator __i = lower_bound(__k);
+		    if (__i == end() || key_comp()(__k, (*__i).first))
+		      {
+			__i = emplace_hint(__i, std::forward<_Args>(__args)...);
+			return {__i, true};
+		      }
+		    return {__i, false};
+		  }
+	      }
+#endif
+	  return _M_t._M_emplace_unique(std::forward<_Args>(__args)...);
+	}
 
       /**
        *  @brief Attempts to build and insert a std::pair into the %map.
@@ -814,7 +841,25 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
 	__enable_if_t<is_constructible<value_type, _Pair>::value,
 		      pair<iterator, bool>>
 	insert(_Pair&& __x)
-	{ return _M_t._M_emplace_unique(std::forward<_Pair>(__x)); }
+	{
+#if __cplusplus >= 201703L
+	  using _P2 = remove_reference_t<_Pair>;
+	  if constexpr (__is_pair<_P2>)
+	    if constexpr (is_same_v<allocator_type, allocator<value_type>>)
+	      if constexpr (__usable_key<typename _P2::first_type>)
+		{
+		  const key_type& __k = __x.first;
+		  iterator __i = lower_bound(__k);
+		  if (__i == end() || key_comp()(__k, (*__i).first))
+		    {
+		      __i = emplace_hint(__i, std::forward<_Pair>(__x));
+		      return {__i, true};
+		    }
+		  return {__i, false};
+		}
+#endif
+	  return _M_t._M_emplace_unique(std::forward<_Pair>(__x));
+	}
 #endif
       /// @}
 
diff --git a/libstdc++-v3/include/bits/stl_pair.h b/libstdc++-v3/include/bits/stl_pair.h
index 6081e0c7fe9..5f7b60932e4 100644
--- a/libstdc++-v3/include/bits/stl_pair.h
+++ b/libstdc++-v3/include/bits/stl_pair.h
@@ -777,6 +777,15 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
 
   template<typename _Tp1, typename _Tp2>
     inline constexpr size_t tuple_size_v<const pair<_Tp1, _Tp2>> = 2;
+
+  template<typename _Tp>
+    inline constexpr bool __is_pair = false;
+
+  template<typename _Tp, typename _Up>
+    inline constexpr bool __is_pair<pair<_Tp, _Up>> = true;
+
+  template<typename _Tp, typename _Up>
+    inline constexpr bool __is_pair<const pair<_Tp, _Up>> = true;
 #endif
 
   /// @cond undocumented
diff --git a/libstdc++-v3/include/bits/uses_allocator_args.h b/libstdc++-v3/include/bits/uses_allocator_args.h
index 8b548ff6981..e1fd7e7d611 100644
--- a/libstdc++-v3/include/bits/uses_allocator_args.h
+++ b/libstdc++-v3/include/bits/uses_allocator_args.h
@@ -56,12 +56,6 @@
 namespace std _GLIBCXX_VISIBILITY(default)
 {
 _GLIBCXX_BEGIN_NAMESPACE_VERSION
-  template<typename _Tp>
-    inline constexpr bool __is_pair = false;
-  template<typename _Tp, typename _Up>
-    inline constexpr bool __is_pair<pair<_Tp, _Up>> = true;
-  template<typename _Tp, typename _Up>
-    inline constexpr bool __is_pair<const pair<_Tp, _Up>> = true;
 
   template<typename _Tp>
     concept _Std_pair = __is_pair<_Tp>;
diff --git a/libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/92300.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/92300.cc
new file mode 100644
index 00000000000..937b4d9a103
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/emplace/92300.cc
@@ -0,0 +1,36 @@
+// { dg-do run { target c++17 } }
+
+#include <map>
+#include <cstdlib>
+
+bool oom = false;
+
+void* operator new(std::size_t n)
+{
+  if (oom)
+    throw std::bad_alloc();
+  return std::malloc(n);
+}
+
+void operator delete(void* p)
+{
+  std::free(p);
+}
+
+void operator delete(void* p, std::size_t)
+{
+  std::free(p);
+}
+
+int main()
+{
+  std::map<int, int> m;
+  int i = 0;
+  (void) m[i];
+  oom = true;
+  m.emplace(i, 1);
+  m.emplace(i, 2L);
+  const int c = 3;
+  m.emplace(i, c);
+  m.emplace((long)i, 4);
+}
diff --git a/libstdc++-v3/testsuite/23_containers/map/modifiers/insert/92300.cc b/libstdc++-v3/testsuite/23_containers/map/modifiers/insert/92300.cc
new file mode 100644
index 00000000000..80abdaf1f30
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/map/modifiers/insert/92300.cc
@@ -0,0 +1,38 @@
+// { dg-do run { target c++17 } }
+
+#include <map>
+#include <cstdlib>
+
+bool oom = false;
+
+void* operator new(std::size_t n)
+{
+  if (oom)
+    throw std::bad_alloc();
+  return std::malloc(n);
+}
+
+void operator delete(void* p)
+{
+  std::free(p);
+}
+
+void operator delete(void* p, std::size_t)
+{
+  std::free(p);
+}
+
+int main()
+{
+  using std::pair;
+  std::map<int, int> m;
+  int i = 0;
+  (void) m[i];
+  oom = true;
+  m.insert({i, 1});			    // insert(value_type&&)
+  m.insert(pair<int, int>(i, 2));	    // insert(Pair&&)
+  m.insert(pair<int&, int>(i, 3));	    // insert(Pair&&)
+  m.insert(pair<int, long>(i, 4L));	    // insert(Pair&&)
+  m.insert(pair<const int, long>(i, 5L));   // insert(Pair&&)
+  m.insert(pair<const int&, long>(i, 6L));  // insert(Pair&&)
+}
-- 
2.31.1


                 reply	other threads:[~2021-12-09 23:27 UTC|newest]

Thread overview: [no followups] expand[flat|nested]  mbox.gz  Atom feed

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20211209232700.1568897-1-jwakely@redhat.com \
    --to=jwakely@redhat.com \
    --cc=gcc-patches@gcc.gnu.org \
    --cc=libstdc++@gcc.gnu.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).