From: "François Dumont" <frs.dumont@gmail.com>
To: "libstdc++@gcc.gnu.org" <libstdc++@gcc.gnu.org>
Cc: gcc-patches <gcc-patches@gcc.gnu.org>
Subject: [PATCH] libstdc++: Limit allocations in _Rb_tree 2/2
Date: Wed, 22 Feb 2023 07:08:24 +0100 [thread overview]
Message-ID: <98823f83-ae62-f3e4-4091-01841b08fbb7@gmail.com> (raw)
In-Reply-To: <7313d189-ae56-4582-6f23-9263dbf57dd3@gmail.com>
[-- Attachment #1: Type: text/plain, Size: 1312 bytes --]
This one is a refinement for multimap/multiset.
It allows to have share the same key if managed with ref counting like
the cow string.
libstdc++: [_Rb_tree] Limit allocations on equal insertions [PR 96088]
When inserting the same key several times prefer to insert the new
entry using the
current stored key_type instance if this copy is noexcept.
Otherwise create a new
key instance from input argument.
libstdc++-v3/ChangeLog:
PR libstdc++/96088
* include/bits/cow_string.h
(basic_string<>::basic_string(const basic_string&)):
Add noexcept qualification when allocator is always equal.
* include/bits/stl_tree.h
(_Rb_tree<>::_M_get_insert_equal_pos_tr): New.
(_Rb_tree<>::_M_emplace_equal_tr): New, use latter.
(_Rb_tree<>::_M_emplace_equal_aux): New, use latter.
(_Rb_tree<>::_M_emplace_equal<_Arg>(_Arg&&)): New, use latter.
* testsuite/23_containers/multimap/96088.cc (test01): Add
check on redundant
insertion.
(test02): Likewise.
* testsuite/23_containers/multiset/96088.cc (test01,
test02): Likewise.
François
[-- Attachment #2: pr96088_multimap.patch --]
[-- Type: text/x-patch, Size: 5413 bytes --]
diff --git a/libstdc++-v3/include/bits/cow_string.h b/libstdc++-v3/include/bits/cow_string.h
index ad9929c4ad3..cdfbe5e190b 100644
--- a/libstdc++-v3/include/bits/cow_string.h
+++ b/libstdc++-v3/include/bits/cow_string.h
@@ -541,6 +541,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
* @param __str Source string.
*/
basic_string(const basic_string& __str)
+ _GLIBCXX_NOEXCEPT_IF(_CharT_alloc_traits::_S_always_equal())
: _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
__str.get_allocator()),
__str.get_allocator())
diff --git a/libstdc++-v3/include/bits/stl_tree.h b/libstdc++-v3/include/bits/stl_tree.h
index 21e9586b0a3..c3a4a97cfcf 100644
--- a/libstdc++-v3/include/bits/stl_tree.h
+++ b/libstdc++-v3/include/bits/stl_tree.h
@@ -968,6 +968,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Kt>
pair<_Base_ptr, _Base_ptr>
_M_get_insert_unique_pos_tr(const _Kt& __k);
+
+ template<typename _Kt>
+ pair<_Base_ptr, _Base_ptr>
+ _M_get_insert_equal_pos_tr(const _Kt& __k);
#endif
pair<_Base_ptr, _Base_ptr>
@@ -1225,6 +1229,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::forward<_Arg>(__arg));
}
+ template<typename _Kt, typename _Arg>
+ iterator
+ _M_emplace_equal_kv(_Kt&&, _Arg&&);
+
+ template<typename _Arg>
+ iterator
+ _M_emplace_equal_aux(_Arg&& __arg)
+ {
+ return _M_emplace_equal_kv(
+ _S_forward_key(_KeyOfValue{}(std::forward<_Arg>(__arg))),
+ std::forward<_Arg>(__arg));
+ }
+
template<typename _Arg>
pair<iterator, bool>
_M_emplace_unique(_Arg&& __arg)
@@ -1237,6 +1254,14 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
pair<iterator, bool>
_M_emplace_unique(_Args&&... __args);
+ template<typename _Arg>
+ iterator
+ _M_emplace_equal(_Arg&& __arg)
+ {
+ using __to_value = _ConvertToValueType<_KeyOfValue, value_type>;
+ return _M_emplace_equal_aux(__to_value{}(std::forward<_Arg>(__arg)));
+ }
+
template<typename... _Args>
iterator
_M_emplace_equal(_Args&&... __args);
@@ -2355,6 +2380,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return _Res(__x, __y);
return _Res(__j._M_node, 0);
}
+
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template<typename _Kt>
+ auto
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_get_insert_equal_pos_tr(const _Kt& __k)
+ -> pair<_Base_ptr, _Base_ptr>
+ {
+ typedef pair<_Base_ptr, _Base_ptr> _Res;
+ _Link_type __x = _M_begin();
+ _Base_ptr __y = _M_end();
+ while (__x != 0)
+ {
+ __y = __x;
+ __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
+ _S_left(__x) : _S_right(__x);
+ }
+ return _Res(__x, __y);
+ }
#endif
template<typename _Key, typename _Val, typename _KeyOfValue,
@@ -2661,6 +2706,26 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return { iterator(__res.first), false };
}
+ template<typename _Key, typename _Val, typename _KeyOfValue,
+ typename _Compare, typename _Alloc>
+ template<typename _Kt, typename _Arg>
+ auto
+ _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
+ _M_emplace_equal_kv(_Kt&& __k, _Arg&& __arg)
+ -> iterator
+ {
+ auto __res = _M_get_insert_equal_pos_tr(__k);
+ _Auto_node __z =
+ (!is_nothrow_copy_constructible<key_type>::value
+ || __res.second == _M_end()
+ || _M_impl._M_key_compare(__k, _S_key(__res.second)))
+ ? _S_build_node(*this, std::forward<_Kt>(__k),
+ std::forward<_Arg>(__arg), _KeyOfValue{})
+ : _S_build_node(*this, _S_key(__res.second),
+ std::forward<_Arg>(__arg), _KeyOfValue{});
+ return __z._M_insert(__res);
+ }
+
template<typename _Key, typename _Val, typename _KeyOfValue,
typename _Compare, typename _Alloc>
template<typename... _Args>
diff --git a/libstdc++-v3/testsuite/23_containers/multimap/96088.cc b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
index 919c5e59c71..1a778a0785d 100644
--- a/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
+++ b/libstdc++-v3/testsuite/23_containers/multimap/96088.cc
@@ -1,4 +1,5 @@
// { dg-do run { target c++17 } }
+// { dg-add-options no_pch }
// { dg-require-effective-target std_allocator_new }
// Copyright (C) 2023 Free Software Foundation, Inc.
@@ -20,6 +21,9 @@
// libstdc++/96088
+#undef _GLIBCXX_USE_CXX11_ABI
+#define _GLIBCXX_USE_CXX11_ABI 0
+
#include <string_view>
#include <string>
#include <map>
@@ -42,6 +46,15 @@ test01()
VERIFY( __gnu_test::counter::count() == 2 );
VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+ // Allocate a node and the std::string (unless COW).
+ constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+ foo.insert(lst.begin(), lst.end());
+ VERIFY( foo.size() == 2 );
+
+ VERIFY( __gnu_test::counter::count() == 2 + increments );
+ VERIFY( __gnu_test::counter::get()._M_increments == 2 + increments );
}
void
@@ -54,6 +67,15 @@ test02()
VERIFY( __gnu_test::counter::count() == 2 );
VERIFY( __gnu_test::counter::get()._M_increments == 2 );
+
+ // Allocate a node and the std::string (unless COW).
+ constexpr std::size_t increments = _GLIBCXX_USE_CXX11_ABI ? 2 : 1;
+
+ foo.insert(lst.begin(), lst.end());
+ VERIFY( foo.size() == 2 );
+
+ VERIFY( __gnu_test::counter::count() == 2 + increments );
+ VERIFY( __gnu_test::counter::get()._M_increments == 2 + 2 );
}
int
next prev parent reply other threads:[~2023-02-22 6:08 UTC|newest]
Thread overview: 7+ messages / expand[flat|nested] mbox.gz Atom feed top
2023-02-02 18:20 [PATCH] libstdc++: Limit allocations in _Rb_tree François Dumont
2023-02-04 13:22 ` François Dumont
2023-02-22 6:06 ` [PATCH] libstdc++: Limit allocations in _Rb_tree 1/2 François Dumont
2023-02-22 6:08 ` François Dumont [this message]
2023-03-02 5:39 ` [PATCH] libstdc++: Limit allocations in _Rb_tree 2/2 François Dumont
2023-03-02 10:43 ` Jonathan Wakely
2023-03-06 17:36 ` [PATCH] libstdc++: Limit allocations in _Rb_tree 1/2 Jonathan Wakely
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=98823f83-ae62-f3e4-4091-01841b08fbb7@gmail.com \
--to=frs.dumont@gmail.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).