On 05/11/24 17:50 +0000, Jonathan Wakely wrote:
On 28/10/24 21:51 +0100, François Dumont wrote:
On 24/10/2024 21:49, Jonathan Wakely wrote:
On Thu, 24 Oct 2024 at 19:43, François Dumont<frs.dum...@gmail.com> wrote:
Committed as trivial the attached patch.
libstdc++: Fix test broken when using COW std::string
libstdc++-v3/ChangeLog:
* testsuite/23_containers/unordered_map/96088.cc (test03):
Thanks! I think it was affecting the unordered_set test too.
Hi
This was indeed revealing a problem in my attempt to fix this bug.
Here is the complete patch that I will backport if validated.
libstdc++: [_Hashtable] Avoid temporaries when inserting existing key
Following PR 115285 fix, the hashtable _S_forward_key responsible
for finding
the best way to transmit the key part of the argument parameter to the hash
functor was modified to return a key_type instance for any argument
type. Only
the overloads for const key_type& and key_type&& were still
preventing a key_type
instanciation.
It revealed that a overload for key_type& was missing. To fix this
problem we now
deal with all sort of key_type of reference type in the unique
_S_forward_key static
method and remove the overloads. When decayed type of the input
instance is the same
as key_type we avoid the instanciation. Note that for the comparison
we also decay
key_type to properly managed when unordered container is
instantiated with a const
type.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h
(_ConvertToValueType<_Select1st,
_Value>::operator(std::pair<>&)): New,
allow consistent behavior with
_ConvertToValueType<_Identity, _Value>.
* include/bits/hashtable.h
(_S_forward_key<_Kt>(_Kt&&)): Adapt to return _Kt&& when
decayed _Kt is
key_type, return a new key_type instance otherwise.
(_S_forward_key(const key_type&)): Remove.
(_S_forward_key(key_type&&)): Remove.
* testsuite/23_containers/unordered_set/96088.cc (test03):
Adapt expected
allocation increment.
Tested under linux x64, both std::string abi.
Ok to commit ?
No, because it's still not a complete fix, just more special cases.
I think the attached patch (actually two patches, as there's one to
add __is_pair first) fixes PR 115285, including all the other cases I
added in comment 14. It also avoids regressing PR 96088.
This seems small and safe enough to backport. On trunk I still plan to
follow this with the bigger refactoring.
Tests are still running ...
commit 590091e997248dd475d7329f4613765d7cff8bb6
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Fri Nov 1 10:09:55 2024
libstdc++: Define __is_pair variable template for C++11
libstdc++-v3/ChangeLog:
* include/bits/stl_pair.h (__is_pair): Define for C++11 and
C++14 as well.
diff --git a/libstdc++-v3/include/bits/stl_pair.h
b/libstdc++-v3/include/bits/stl_pair.h
index e92fcad2d66..527fb9105f0 100644
--- a/libstdc++-v3/include/bits/stl_pair.h
+++ b/libstdc++-v3/include/bits/stl_pair.h
@@ -1189,12 +1189,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
template<typename _Tp1, typename _Tp2>
inline constexpr size_t tuple_size_v<const pair<_Tp1, _Tp2>> = 2;
+#endif
+#if __cplusplus >= 201103L
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wc++14-extensions" // variable templates
+#pragma GCC diagnostic ignored "-Wc++17-extensions" // inline variables
template<typename _Tp>
inline constexpr bool __is_pair = false;
template<typename _Tp, typename _Up>
inline constexpr bool __is_pair<pair<_Tp, _Up>> = true;
+#pragma GCC diagnostic pop
#endif
/// @cond undocumented
commit 23328cc25365593d045096ccf913cb273202edb0
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Tue Nov 5 17:19:06 2024
libstdc++: Fix conversions to key/value type for insertions into hash tables
[PR115285]
The conversions to key_type and value_type that are performed when
inserting into _Hashtable need to be fixed to do any required
conversions explicitly. The current code assumes that conversions from
the parameter to the key_type or value_type can be done implicitly,
which isn't necessarily true.
Remove the _S_forward_key function which doesn't handle all cases and
either forward the parameter if it already has type cv key_type, or
explicitly construct a temporary of type key_type.
Similarly, for the _ConvertToValueType specialization for maps, either
forward a std::pair parameter unchanged, or explicitly construct a
temporary of type value_type.
libstdc++-v3/ChangeLog:
PR libstdc++/115285
* include/bits/hashtable.h (_Hashtable::_S_forward_key): Remove.
(_Hashtable::_M_insert_unique_aux):
* include/bits/hashtable_policy.h (_ConvertToValueType): Add
comment.
(_ConvertToValueType<_Select1st, _Value>): Replace incomplete
overload set with two overloads, one for std::pair
specializations and one for everything else.
* testsuite/23_containers/unordered_map/insert/115285.cc: New test.
* testsuite/23_containers/unordered_set/insert/115285.cc: New test.
* testsuite/23_containers/unordered_set/96088.cc: Adjust
expected number of allocations.
diff --git a/libstdc++-v3/include/bits/hashtable.h
b/libstdc++-v3/include/bits/hashtable.h
index 47321a9cb13..0759a9699e5 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -929,25 +929,16 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
std::pair<iterator, bool>
_M_insert_unique(_Kt&&, _Arg&&, _NodeGenerator&);
- template<typename _Kt>
- key_type
- _S_forward_key(_Kt&& __k)
- { return std::forward<_Kt>(__k); }
-
- static const key_type&
- _S_forward_key(const key_type& __k)
- { return __k; }
-
- static key_type&&
- _S_forward_key(key_type&& __k)
- { return std::move(__k); }
-
template<typename _Arg, typename _NodeGenerator>
std::pair<iterator, bool>
_M_insert_unique_aux(_Arg&& __arg, _NodeGenerator& __node_gen)
{
+ using _Kt = decltype(_ExtractKey{}(std::forward<_Arg>(__arg)));
+ constexpr bool __is_key_type
+ = is_same<__remove_cvref_t<_Kt>, key_type>::value;
+ using _Fwd_key = __conditional_t<__is_key_type, _Kt&&, key_type>;
return _M_insert_unique(
- _S_forward_key(_ExtractKey{}(std::forward<_Arg>(__arg))),
+ static_cast<_Fwd_key>(_ExtractKey{}(std::forward<_Arg>(__arg))),
std::forward<_Arg>(__arg), __node_gen);
}
Actually we can simplify this further.
There's no need to use _ConvertToValueType for the non-unique keys
case. We don't need to extract a key and search for duplicates, we are
just going to insert it anyway. So just forward the _Arg without
conversion.
That means we only use _ConvertToValueType in one place, the overload
of _M_insert for unique keys. And we can replace it with a typedef and
a static_cast there. That means we don't need to instantiate the
_ConvertToValueType class template at all, and can remove it.
Here's an incremental patch to be applied on top of the previous one:
diff --git a/libstdc++-v3/include/bits/hashtable.h
b/libstdc++-v3/include/bits/hashtable.h
index 0759a9699e5..45829fa2a14 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -947,10 +947,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
true_type /* __uks */)
{
- using __to_value
- = __detail::_ConvertToValueType<_ExtractKey, value_type>;
+ using __detail::_Identity;
+ using _Vt = __conditional_t<is_same<_ExtractKey, _Identity>::value
+ || __is_pair<__remove_cvref_t<_Arg>>,
+ _Arg&&, value_type>;
return _M_insert_unique_aux(
- __to_value{}(std::forward<_Arg>(__arg)), __node_gen);
+ static_cast<_Vt>(std::forward<_Arg>(__arg)), __node_gen);
}
template<typename _Arg, typename _NodeGenerator>
@@ -958,10 +960,8 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
_M_insert(_Arg&& __arg, _NodeGenerator& __node_gen,
false_type __uks)
{
- using __to_value
- = __detail::_ConvertToValueType<_ExtractKey, value_type>;
- return _M_insert(cend(),
- __to_value{}(std::forward<_Arg>(__arg)), __node_gen, __uks);
+ return _M_insert(cend(), std::forward<_Arg>(__arg),
+ __node_gen, __uks);
}
// Insert with hint, not used when keys are unique.
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index 36cd3219af4..b8d1f5de36d 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -113,37 +113,6 @@ namespace __detail
{ return std::forward<_Tp>(__x).first; }
};
- // This is misnamed, it doesn't actually convert to the value_type,
- // but for maps it converts non-pairs to the value_type.
- template<typename _ExKey, typename _Value>
- struct _ConvertToValueType;
-
- template<typename _Value>
- struct _ConvertToValueType<_Identity, _Value>
- {
- template<typename _Kt>
- constexpr _Kt&&
- operator()(_Kt&& __k) const noexcept
- { return std::forward<_Kt>(__k); }
- };
-
- template<typename _Value>
- struct _ConvertToValueType<_Select1st, _Value>
- {
- // If the argument is already a std::pair, just forward it unchanged
- // (even if not the same std::pair specialization as _Value).
- template<typename _Tp>
- constexpr __enable_if_t<__is_pair<__remove_cvref_t<_Tp>>, _Tp&&>
- operator()(_Tp&& __x) const noexcept
- { return std::forward<_Tp>(__x); }
-
- // Otherwise, create a temporary of the container's value_type.
- template<typename _Tp>
- constexpr __enable_if_t<!__is_pair<__remove_cvref_t<_Tp>>, _Value>
- operator()(_Tp&& __x) const noexcept
- { return _Value(std::forward<_Tp>(__x)); }
- };
-
template<typename _ExKey>
struct _NodeBuilder;
