From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.129.124]) by sourceware.org (Postfix) with ESMTPS id EE3CF3858005 for ; Thu, 9 Dec 2021 23:27:06 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EE3CF3858005 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-23-XL8QdQ7pMzq642JXnLJJ5g-1; Thu, 09 Dec 2021 18:27:03 -0500 X-MC-Unique: XL8QdQ7pMzq642JXnLJJ5g-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.phx2.redhat.com [10.5.11.14]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 3E09E10247A6; Thu, 9 Dec 2021 23:27:02 +0000 (UTC) Received: from localhost (unknown [10.33.36.71]) by smtp.corp.redhat.com (Postfix) with ESMTP id C1A2517CD9; Thu, 9 Dec 2021 23:27:01 +0000 (UTC) From: Jonathan Wakely 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 Message-Id: <20211209232700.1568897-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.14 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset="US-ASCII" X-Spam-Status: No, score=-13.9 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=unavailable autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: libstdc++@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Libstdc++ mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 09 Dec 2021 23:27:08 -0000 Tested powerpc64le-linux, pushed to trunk. Inserting a pair into a map will allocate a new node and construct a pair in the node, then check if the Key is already present in the map. That is because pair 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, pair, pair 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 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> + static constexpr bool __usable_key + = __or_v, + __and_, 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 std::pair 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>) + { + auto&& [__a, __v] = pair<_Args&...>(__args...); + if constexpr (__usable_key) + { + 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::value, pair> 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>) + if constexpr (__usable_key) + { + 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 inline constexpr size_t tuple_size_v> = 2; + + template + inline constexpr bool __is_pair = false; + + template + inline constexpr bool __is_pair> = true; + + template + inline constexpr bool __is_pair> = 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 - inline constexpr bool __is_pair = false; - template - inline constexpr bool __is_pair> = true; - template - inline constexpr bool __is_pair> = true; template 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 +#include + +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 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 +#include + +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 m; + int i = 0; + (void) m[i]; + oom = true; + m.insert({i, 1}); // insert(value_type&&) + m.insert(pair(i, 2)); // insert(Pair&&) + m.insert(pair(i, 3)); // insert(Pair&&) + m.insert(pair(i, 4L)); // insert(Pair&&) + m.insert(pair(i, 5L)); // insert(Pair&&) + m.insert(pair(i, 6L)); // insert(Pair&&) +} -- 2.31.1