Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 1/16/20 5:01 PM, Jonathan Wakely wrote:
On 16/01/20 13:25 +, Jonathan Wakely wrote:
On 16/01/20 07:42 +0100, François Dumont wrote:
On 1/15/20 10:52 PM, Jonathan Wakely wrote:
On 15/01/20 21:48 +, Jonathan Wakely wrote:
On 14/01/20 22:25 +0100, François Dumont wrote:
On 1/13/20 10:53 PM, Jonathan Wakely wrote:
On 13/01/20 22:41 +0100, François Dumont wrote:
For the multi-keys we could still avoid redundant comparisons
when _Equal is just doing == on the key type. On
unordered_multiset we could just avoids the call to
is_permuation and on the unordered_multimap we could check the
is_permutation only on the associated value rather than on the
std::pair.
I don't think that's necessary, or helpful.
The idea of
https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is
that you shouldn't be using _Equal at all, and therefore it doesn't
matter whether it's std::equal_to or not.
And it was indeed possible.
Nice!
PR libstdc++/91223
* include/bits/hashtable.h (_Hashtable<>): Make _Equality<>
friend.
* include/bits/hashtable_policy.h: Include .
(_Equality_base): Remove.
(_Equality<>::_M_equal): Review implementation. Use
std::is_permutation.
* testsuite/23_containers/unordered_multiset/operators/1.cc
(Hash, Equal, test02, test03): New.
* testsuite/23_containers/unordered_set/operators/1.cc
(Hash, Equal, test02, test03): New.
Tested under Linux x86_64.
Ok to commit ?
Yes, OK for trunk (we're in stage4 but your patch was posted in
stage3
and fixes a pretty nasty performance bug, so is OK now).
N.B. GCC has moved to Git instead of Subversion. If you don't have
Git
access set up let me know and I can commit the patch for you.
I haven't done the move yet and won't be able to do it before the
week-end. So please proceed to the commit for me, thanks.
No problem, I can do that.
Your patch is now committed to trunk. Thanks for the major
improvement.
I had a look at std::is_permutation and I think we can make some
simplifications to the 4-argument overload, and we can share most of
the code between the 3-arg and 4-arg overloads (once they've confirmed
the lengths are the same they do exactly the same thing). See the
attached patch. This should probably wait for stage1 though.
I also wanted to add some comments to the _Equality::_M_equal
specialiation for unordered_multimap/multiset to explain what the code
was doing, and had some more ideas. See patch again.
It looks like this loop can potentially visit every element of
__other, instead of stopping at the end of the bucket:
typename __hashtable::const_iterator __ity(__y_n);
for (auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end)
if (--__x_count == 0)
break;
Consider a case like this:
unordered_multiset a{1, 2, 3, 4};
for (int i = 0; i <1; ++i)
a.insert(1);
unordered_multiset b{1, 2, 3, 4};
for (int i = 0; i <1; ++i)
b.insert(2);
When doing a == b we'll find 1 elements in a with key '1',
and find one element in b with that key. But then we iterate through
every element in b after that one, even though they have different
keys and are probably in different buckets.
Instead of just iterating from __ity to __other.end(), can we use a
local iterator so we stop at the end of the bucket?
This seems to make the PR91263 example *very* slightly slower, but
makes the example above significantly faster.
What do you think?
The hashtable implementation is doing its best to provide good
performances as long as the user does its part of the job. Mainly
provide a good hash to distrubute elements smoothly throughout the
buckets. But also avoid this kind of unordered_multiset.
If you check if you don't move out of bucket you'll have to pay for the
bucket computation (subject of PR 68303) or perform a redundant _Equal
to check when we left the range of equivalent elements like it used to
be done. Current implementation leave it to the std::is_permutation to
do that which in normal situation will be better I think.
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 16/01/20 13:25 +, Jonathan Wakely wrote:
On 16/01/20 07:42 +0100, François Dumont wrote:
On 1/15/20 10:52 PM, Jonathan Wakely wrote:
On 15/01/20 21:48 +, Jonathan Wakely wrote:
On 14/01/20 22:25 +0100, François Dumont wrote:
On 1/13/20 10:53 PM, Jonathan Wakely wrote:
On 13/01/20 22:41 +0100, François Dumont wrote:
For the multi-keys we could still avoid redundant
comparisons when _Equal is just doing == on the key type.
On unordered_multiset we could just avoids the call to
is_permuation and on the unordered_multimap we could check
the is_permutation only on the associated value rather
than on the std::pair.
I don't think that's necessary, or helpful.
The idea of https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is
that you shouldn't be using _Equal at all, and therefore it doesn't
matter whether it's std::equal_to or not.
And it was indeed possible.
Nice!
PR libstdc++/91223
* include/bits/hashtable.h (_Hashtable<>): Make _Equality<> friend.
* include/bits/hashtable_policy.h: Include .
(_Equality_base): Remove.
(_Equality<>::_M_equal): Review implementation. Use
std::is_permutation.
* testsuite/23_containers/unordered_multiset/operators/1.cc
(Hash, Equal, test02, test03): New.
* testsuite/23_containers/unordered_set/operators/1.cc
(Hash, Equal, test02, test03): New.
Tested under Linux x86_64.
Ok to commit ?
Yes, OK for trunk (we're in stage4 but your patch was posted in stage3
and fixes a pretty nasty performance bug, so is OK now).
N.B. GCC has moved to Git instead of Subversion. If you don't have Git
access set up let me know and I can commit the patch for you.
I haven't done the move yet and won't be able to do it before the
week-end. So please proceed to the commit for me, thanks.
No problem, I can do that.
Your patch is now committed to trunk. Thanks for the major
improvement.
I had a look at std::is_permutation and I think we can make some
simplifications to the 4-argument overload, and we can share most of
the code between the 3-arg and 4-arg overloads (once they've confirmed
the lengths are the same they do exactly the same thing). See the
attached patch. This should probably wait for stage1 though.
I also wanted to add some comments to the _Equality::_M_equal
specialiation for unordered_multimap/multiset to explain what the code
was doing, and had some more ideas. See patch again.
It looks like this loop can potentially visit every element of
__other, instead of stopping at the end of the bucket:
typename __hashtable::const_iterator __ity(__y_n);
for (auto __ity_end = __ity; __ity_end != __other.end(); ++__ity_end)
if (--__x_count == 0)
break;
Consider a case like this:
unordered_multiset a{1, 2, 3, 4};
for (int i = 0; i <1; ++i)
a.insert(1);
unordered_multiset b{1, 2, 3, 4};
for (int i = 0; i <1; ++i)
b.insert(2);
When doing a == b we'll find 1 elements in a with key '1',
and find one element in b with that key. But then we iterate through
every element in b after that one, even though they have different
keys and are probably in different buckets.
Instead of just iterating from __ity to __other.end(), can we use a
local iterator so we stop at the end of the bucket?
This seems to make the PR91263 example *very* slightly slower, but
makes the example above significantly faster.
What do you think?
diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 6503d1518d3..6d5d3b2fced 100644
--- a/libstdc++-v3/include/bits/stl_algo.h
+++ b/libstdc++-v3/include/bits/stl_algo.h
@@ -3588,6 +3588,33 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
return std::make_pair(*__p.first, *__p.second);
}
+ // precondition: distance(__first1, __last1) == distance(__first2, __last2).
+ template
+_GLIBCXX20_CONSTEXPR
+bool
+__is_permutation_impl(_FwdIter1 __first1, _FwdIter1 __last1,
+ _FwdIter2 __first2, _FwdIter2 __last2,
+ _BinaryPredicate __pred = {})
+{
+ for (auto __scan = __first1; __scan != __last1; ++__scan)
+ {
+ if (__scan != std::__find_if(__first1, __scan,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan)))
+ continue; // We've seen this one before.
+
+ auto __matches
+ = std::__count_if(__first2, __last2,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan));
+ if (0 == __matches ||
+ std::__count_if(__scan, __last1,
+ __gnu_cxx::__ops::__iter_comp_iter(__pred, __scan))
+ != __matches)
+ return false;
+ }
+ return true;
+}
+
template
_GLIBCXX20_CONSTEXPR
@@ -3604,26 +3631,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__first1 == __last1)
return true;
- // Establish __last2 assuming equal ranges by iterating over the
- // rest of the list.
- _ForwardIterator2 __last2 = __first2;
- std::advance(__last2, std::distance(__first1, __last1));
- for (_ForwardIterator1 __scan = __first1; __scan != __last1; ++__scan)
- {
-
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 16/01/20 07:42 +0100, François Dumont wrote: On 1/15/20 10:52 PM, Jonathan Wakely wrote: On 15/01/20 21:48 +, Jonathan Wakely wrote: On 14/01/20 22:25 +0100, François Dumont wrote: On 1/13/20 10:53 PM, Jonathan Wakely wrote: On 13/01/20 22:41 +0100, François Dumont wrote: For the multi-keys we could still avoid redundant comparisons when _Equal is just doing == on the key type. On unordered_multiset we could just avoids the call to is_permuation and on the unordered_multimap we could check the is_permutation only on the associated value rather than on the std::pair. I don't think that's necessary, or helpful. The idea of https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is that you shouldn't be using _Equal at all, and therefore it doesn't matter whether it's std::equal_to or not. And it was indeed possible. Nice! PR libstdc++/91223 * include/bits/hashtable.h (_Hashtable<>): Make _Equality<> friend. * include/bits/hashtable_policy.h: Include . (_Equality_base): Remove. (_Equality<>::_M_equal): Review implementation. Use std::is_permutation. * testsuite/23_containers/unordered_multiset/operators/1.cc (Hash, Equal, test02, test03): New. * testsuite/23_containers/unordered_set/operators/1.cc (Hash, Equal, test02, test03): New. Tested under Linux x86_64. Ok to commit ? Yes, OK for trunk (we're in stage4 but your patch was posted in stage3 and fixes a pretty nasty performance bug, so is OK now). N.B. GCC has moved to Git instead of Subversion. If you don't have Git access set up let me know and I can commit the patch for you. I haven't done the move yet and won't be able to do it before the week-end. So please proceed to the commit for me, thanks. No problem, I can do that.
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 1/15/20 10:52 PM, Jonathan Wakely wrote: On 15/01/20 21:48 +, Jonathan Wakely wrote: On 14/01/20 22:25 +0100, François Dumont wrote: On 1/13/20 10:53 PM, Jonathan Wakely wrote: On 13/01/20 22:41 +0100, François Dumont wrote: For the multi-keys we could still avoid redundant comparisons when _Equal is just doing == on the key type. On unordered_multiset we could just avoids the call to is_permuation and on the unordered_multimap we could check the is_permutation only on the associated value rather than on the std::pair. I don't think that's necessary, or helpful. The idea of https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is that you shouldn't be using _Equal at all, and therefore it doesn't matter whether it's std::equal_to or not. And it was indeed possible. Nice! PR libstdc++/91223 * include/bits/hashtable.h (_Hashtable<>): Make _Equality<> friend. * include/bits/hashtable_policy.h: Include . (_Equality_base): Remove. (_Equality<>::_M_equal): Review implementation. Use std::is_permutation. * testsuite/23_containers/unordered_multiset/operators/1.cc (Hash, Equal, test02, test03): New. * testsuite/23_containers/unordered_set/operators/1.cc (Hash, Equal, test02, test03): New. Tested under Linux x86_64. Ok to commit ? Yes, OK for trunk (we're in stage4 but your patch was posted in stage3 and fixes a pretty nasty performance bug, so is OK now). N.B. GCC has moved to Git instead of Subversion. If you don't have Git access set up let me know and I can commit the patch for you. I haven't done the move yet and won't be able to do it before the week-end. So please proceed to the commit for me, thanks. P.S. some performance numbers using the code in the bug report (calling Nested(n+1) and Nested(n) where n is the number of levels shown) ... Before: 10 levels of nesting, 0.90 seconds 20 levels of nesting, 0.082400 seconds 22 levels of nesting, 0.285758 seconds 24 levels of nesting, 1.146782 seconds 26 levels of nesting, 4.659524 seconds 28 levels of nesting, 17.739022 seconds 30 levels of nesting, 76.288977 seconds real 1m40.204s user 1m40.039s sys 0m0.005s After: 10 levels of nesting, 0.01 seconds 20 levels of nesting, 0.01 seconds 22 levels of nesting, 0.01 seconds 24 levels of nesting, 0.01 seconds 26 levels of nesting, 0.01 seconds 28 levels of nesting, 0.01 seconds 30 levels of nesting, 0.01 seconds 2 levels of nesting, 0.002905 seconds real 0m0.002s user 0m0.001s sys 0m0.001s Very nice indeed !
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 15/01/20 21:48 +, Jonathan Wakely wrote: On 14/01/20 22:25 +0100, François Dumont wrote: On 1/13/20 10:53 PM, Jonathan Wakely wrote: On 13/01/20 22:41 +0100, François Dumont wrote: For the multi-keys we could still avoid redundant comparisons when _Equal is just doing == on the key type. On unordered_multiset we could just avoids the call to is_permuation and on the unordered_multimap we could check the is_permutation only on the associated value rather than on the std::pair. I don't think that's necessary, or helpful. The idea of https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is that you shouldn't be using _Equal at all, and therefore it doesn't matter whether it's std::equal_to or not. And it was indeed possible. Nice! PR libstdc++/91223 * include/bits/hashtable.h (_Hashtable<>): Make _Equality<> friend. * include/bits/hashtable_policy.h: Include . (_Equality_base): Remove. (_Equality<>::_M_equal): Review implementation. Use std::is_permutation. * testsuite/23_containers/unordered_multiset/operators/1.cc (Hash, Equal, test02, test03): New. * testsuite/23_containers/unordered_set/operators/1.cc (Hash, Equal, test02, test03): New. Tested under Linux x86_64. Ok to commit ? Yes, OK for trunk (we're in stage4 but your patch was posted in stage3 and fixes a pretty nasty performance bug, so is OK now). N.B. GCC has moved to Git instead of Subversion. If you don't have Git access set up let me know and I can commit the patch for you. P.S. some performance numbers using the code in the bug report (calling Nested(n+1) and Nested(n) where n is the number of levels shown) ... Before: 10 levels of nesting, 0.90 seconds 20 levels of nesting, 0.082400 seconds 22 levels of nesting, 0.285758 seconds 24 levels of nesting, 1.146782 seconds 26 levels of nesting, 4.659524 seconds 28 levels of nesting, 17.739022 seconds 30 levels of nesting, 76.288977 seconds real1m40.204s user1m40.039s sys 0m0.005s After: 10 levels of nesting, 0.01 seconds 20 levels of nesting, 0.01 seconds 22 levels of nesting, 0.01 seconds 24 levels of nesting, 0.01 seconds 26 levels of nesting, 0.01 seconds 28 levels of nesting, 0.01 seconds 30 levels of nesting, 0.01 seconds 2 levels of nesting, 0.002905 seconds real0m0.002s user0m0.001s sys 0m0.001s
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 14/01/20 22:25 +0100, François Dumont wrote: On 1/13/20 10:53 PM, Jonathan Wakely wrote: On 13/01/20 22:41 +0100, François Dumont wrote: For the multi-keys we could still avoid redundant comparisons when _Equal is just doing == on the key type. On unordered_multiset we could just avoids the call to is_permuation and on the unordered_multimap we could check the is_permutation only on the associated value rather than on the std::pair. I don't think that's necessary, or helpful. The idea of https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is that you shouldn't be using _Equal at all, and therefore it doesn't matter whether it's std::equal_to or not. And it was indeed possible. Nice! PR libstdc++/91223 * include/bits/hashtable.h (_Hashtable<>): Make _Equality<> friend. * include/bits/hashtable_policy.h: Include . (_Equality_base): Remove. (_Equality<>::_M_equal): Review implementation. Use std::is_permutation. * testsuite/23_containers/unordered_multiset/operators/1.cc (Hash, Equal, test02, test03): New. * testsuite/23_containers/unordered_set/operators/1.cc (Hash, Equal, test02, test03): New. Tested under Linux x86_64. Ok to commit ? Yes, OK for trunk (we're in stage4 but your patch was posted in stage3 and fixes a pretty nasty performance bug, so is OK now). N.B. GCC has moved to Git instead of Subversion. If you don't have Git access set up let me know and I can commit the patch for you.
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 1/13/20 10:53 PM, Jonathan Wakely wrote:
On 13/01/20 22:41 +0100, François Dumont wrote:
For the multi-keys we could still avoid redundant comparisons when
_Equal is just doing == on the key type. On unordered_multiset we
could just avoids the call to is_permuation and on the
unordered_multimap we could check the is_permutation only on the
associated value rather than on the std::pair.
I don't think that's necessary, or helpful.
The idea of https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is
that you shouldn't be using _Equal at all, and therefore it doesn't
matter whether it's std::equal_to or not.
And it was indeed possible.
PR libstdc++/91223
* include/bits/hashtable.h (_Hashtable<>): Make _Equality<> friend.
* include/bits/hashtable_policy.h: Include .
(_Equality_base): Remove.
(_Equality<>::_M_equal): Review implementation. Use
std::is_permutation.
* testsuite/23_containers/unordered_multiset/operators/1.cc
(Hash, Equal, test02, test03): New.
* testsuite/23_containers/unordered_set/operators/1.cc
(Hash, Equal, test02, test03): New.
Tested under Linux x86_64.
Ok to commit ?
François
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 8fac385570b..9e721aad8cc 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -337,6 +337,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool _Constant_iteratorsa>
friend struct __detail::_Insert;
+ template
+ friend struct __detail::_Equality;
+
public:
using size_type = typename __hashtable_base::size_type;
using difference_type = typename __hashtable_base::difference_type;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 7bbfdfd375b..4024e6c37fa 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -34,6 +34,7 @@
#include // for std::tuple, std::forward_as_tuple
#include // for std::numeric_limits
#include // for std::min.
+#include // for std::is_permutation.
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -1815,65 +1816,6 @@ namespace __detail
_M_eq() const { return _EqualEBO::_M_cget(); }
};
- /**
- * struct _Equality_base.
- *
- * Common types and functions for class _Equality.
- */
- struct _Equality_base
- {
- protected:
-template
- static bool
- _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
- };
-
- // See std::is_permutation in N3068.
- template
-bool
-_Equality_base::
-_S_is_permutation(_Uiterator __first1, _Uiterator __last1,
- _Uiterator __first2)
-{
- for (; __first1 != __last1; ++__first1, ++__first2)
- if (!(*__first1 == *__first2))
- break;
-
- if (__first1 == __last1)
- return true;
-
- _Uiterator __last2 = __first2;
- std::advance(__last2, std::distance(__first1, __last1));
-
- for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
- {
- _Uiterator __tmp = __first1;
- while (__tmp != __it1 && !bool(*__tmp == *__it1))
- ++__tmp;
-
- // We've seen this one before.
- if (__tmp != __it1)
- continue;
-
- std::ptrdiff_t __n2 = 0;
- for (__tmp = __first2; __tmp != __last2; ++__tmp)
- if (*__tmp == *__it1)
- ++__n2;
-
- if (!__n2)
- return false;
-
- std::ptrdiff_t __n1 = 0;
- for (__tmp = __it1; __tmp != __last1; ++__tmp)
- if (*__tmp == *__it1)
- ++__n1;
-
- if (__n1 != __n2)
- return false;
- }
- return true;
-}
-
/**
* Primary class template _Equality.
*
@@ -1889,7 +1831,7 @@ namespace __detail
bool _Unique_keys = _Traits::__unique_keys::value>
struct _Equality;
- /// Specialization.
+ /// unordered_map and unordered_set specializations.
template::
_M_equal(const __hashtable& __other) const
{
+ using __node_base = typename __hashtable::__node_base;
+ using __node_type = typename __hashtable::__node_type;
const __hashtable* __this = static_cast(this);
-
if (__this->size() != __other.size())
return false;
for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
{
- const auto __ity = __other.find(_ExtractKey()(*__itx));
- if (__ity == __other.end() || !bool(*__ity == *__itx))
+ std::size_t __ybkt = __other._M_bucket_index(__itx._M_cur);
+ __node_base* __prev_n = __other._M_buckets[__ybkt];
+ if (!__prev_n)
return false;
+
+ for (__node_type* __n = static_cast<__node_type*>(__prev_n->_M_nxt);;
+ __n = __n->_M_next())
+ {
+ if (__n->_M_v() == *__itx)
+ break;
+
+ if (!__n->_M_nxt
+ || __other._M_bucket_index(__n->_M_next()) != __ybkt)
+ return false;
+ }
}
+
return true;
}
- /// Specialization.
+ /// unordered_multiset and unordered_multimap specializations.
template
struct _Equality<_Key, _Value, _Alloc, _ExtractKey,
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 13/01/20 22:41 +0100, François Dumont wrote:
On 1/10/20 11:01 PM, Jonathan Wakely wrote:
On 10/01/20 18:54 +0100, François Dumont wrote:
Hi
Here is my attempt to improve == operator.
There is a small optimization for the std::unordered_mutiXXX
containers but the main enhancement rely on some partial template
specialization of the _Equality type. I limit it to usage of
unordered containers with std::equal_to to be sure that the
container _Equal functor is like the key type ==.
I think we can assume that for any _Equal, not just std::equal_to:
http://eel.is/c++draft/unord.req#12.sentence-5
However ...
Ok but...
Do I need to also consider user partial template
specialization of std::equal_to ? It is a well know bad practice
so I hope the Standard says that such a partial specialization
leads to undefined behavior.
It's certainly not undefined to specialize equal_to, and I'm not sure
how to make your optimisations valid in that case.
This proposal is indeed invalid if you use a std::equal_to partial
specialization, this is why I asked.
Consider:
struct X
{
int i;
int rounded() const { return i - (i % 10); }
bool operator==(X x) const { return i == x.i; }
};
template<> struct std::equal_to
{
bool operator()(X l, X r) const
{ return l.rounded() == r.rounded(); }
};
template<> std::hash
{
bool operator()(X x) const { return hash()(x.rounded()); }
};
std::unordered_multiset u{ X{10}, X{11}, X{12} };
std::unordered_multiset v{ X{15}, X{16}, X{17} };
bool b1 = u == v;
bool b2 = std::is_permutation(u.begin(), u.end(), v.begin());
assert(b1 == b2);
I think the last new specialization in your patch would be used for
this case, and because __x_count == v.count(*u.begin()) it will say
they're equal. But the is_permutation call says they're not.
So I think the assertion would fail, but the standard says it should
pass. Am I mistaken?
I agree, it would fail and the Standard says it should pass.
So here is a new proposal. For the unique keys case I think we are
good, I do not see any other optimization.
For the multi-keys we could still avoid redundant comparisons when
_Equal is just doing == on the key type. On unordered_multiset we
could just avoids the call to is_permuation and on the
unordered_multimap we could check the is_permutation only on the
associated value rather than on the std::pair.
In order to detect that _Equal is the std::equal_to from
stl_function.h it would be great to have something like a
__builtin_is_system returning true for types defined in system
headers. For now I try to propose something similar without compiler
help.
I don't think that's necessary, or helpful.
The idea of https://gcc.gnu.org/ml/libstdc++/2020-01/msg00070.html is
that you shouldn't be using _Equal at all, and therefore it doesn't
matter whether it's std::equal_to or not.
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 1/10/20 11:01 PM, Jonathan Wakely wrote:
On 10/01/20 18:54 +0100, François Dumont wrote:
Hi
Here is my attempt to improve == operator.
There is a small optimization for the std::unordered_mutiXXX
containers but the main enhancement rely on some partial template
specialization of the _Equality type. I limit it to usage of
unordered containers with std::equal_to to be sure that the container
_Equal functor is like the key type ==.
I think we can assume that for any _Equal, not just std::equal_to:
http://eel.is/c++draft/unord.req#12.sentence-5
However ...
Ok but...
Do I need to also consider user partial template specialization
of std::equal_to ? It is a well know bad practice so I hope the
Standard says that such a partial specialization leads to undefined
behavior.
It's certainly not undefined to specialize equal_to, and I'm not sure
how to make your optimisations valid in that case.
This proposal is indeed invalid if you use a std::equal_to partial
specialization, this is why I asked.
Consider:
struct X
{
int i;
int rounded() const { return i - (i % 10); }
bool operator==(X x) const { return i == x.i; }
};
template<> struct std::equal_to
{
bool operator()(X l, X r) const
{ return l.rounded() == r.rounded(); }
};
template<> std::hash
{
bool operator()(X x) const { return hash()(x.rounded()); }
};
std::unordered_multiset u{ X{10}, X{11}, X{12} };
std::unordered_multiset v{ X{15}, X{16}, X{17} };
bool b1 = u == v;
bool b2 = std::is_permutation(u.begin(), u.end(), v.begin());
assert(b1 == b2);
I think the last new specialization in your patch would be used for
this case, and because __x_count == v.count(*u.begin()) it will say
they're equal. But the is_permutation call says they're not.
So I think the assertion would fail, but the standard says it should
pass. Am I mistaken?
I agree, it would fail and the Standard says it should pass.
So here is a new proposal. For the unique keys case I think we are good,
I do not see any other optimization.
For the multi-keys we could still avoid redundant comparisons when
_Equal is just doing == on the key type. On unordered_multiset we could
just avoids the call to is_permuation and on the unordered_multimap we
could check the is_permutation only on the associated value rather than
on the std::pair.
In order to detect that _Equal is the std::equal_to from stl_function.h
it would be great to have something like a __builtin_is_system returning
true for types defined in system headers. For now I try to propose
something similar without compiler help.
François
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 8fac385570b..9e721aad8cc 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -337,6 +337,13 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
bool _Constant_iteratorsa>
friend struct __detail::_Insert;
+ template
+ friend struct __detail::_Equality;
+
public:
using size_type = typename __hashtable_base::size_type;
using difference_type = typename __hashtable_base::difference_type;
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 7bbfdfd375b..55c020f93d1 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -34,6 +34,7 @@
#include // for std::tuple, std::forward_as_tuple
#include // for std::numeric_limits
#include // for std::min.
+#include // for std::is_permutation.
namespace std _GLIBCXX_VISIBILITY(default)
{
@@ -1815,65 +1816,6 @@ namespace __detail
_M_eq() const { return _EqualEBO::_M_cget(); }
};
- /**
- * struct _Equality_base.
- *
- * Common types and functions for class _Equality.
- */
- struct _Equality_base
- {
- protected:
-template
- static bool
- _S_is_permutation(_Uiterator, _Uiterator, _Uiterator);
- };
-
- // See std::is_permutation in N3068.
- template
-bool
-_Equality_base::
-_S_is_permutation(_Uiterator __first1, _Uiterator __last1,
- _Uiterator __first2)
-{
- for (; __first1 != __last1; ++__first1, ++__first2)
- if (!(*__first1 == *__first2))
- break;
-
- if (__first1 == __last1)
- return true;
-
- _Uiterator __last2 = __first2;
- std::advance(__last2, std::distance(__first1, __last1));
-
- for (_Uiterator __it1 = __first1; __it1 != __last1; ++__it1)
- {
- _Uiterator __tmp = __first1;
- while (__tmp != __it1 && !bool(*__tmp == *__it1))
- ++__tmp;
-
- // We've seen this one before.
- if (__tmp != __it1)
- continue;
-
- std::ptrdiff_t __n2 = 0;
- for (__tmp = __first2; __tmp != __last2; ++__tmp)
- if (*__tmp == *__it1)
- ++__n2;
-
- if (!__n2)
- return false;
-
- std::ptrdiff_t __n1 = 0;
- for (__tmp = __it1; __tmp != __last1; ++__tmp)
- if (*__tmp == *__it1)
- ++__n1;
-
- if (__n1 !=
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 10/01/20 22:01 +, Jonathan Wakely wrote:
On 10/01/20 18:54 +0100, François Dumont wrote:
Hi
Here is my attempt to improve == operator.
There is a small optimization for the std::unordered_mutiXXX
containers but the main enhancement rely on some partial template
specialization of the _Equality type. I limit it to usage of
unordered containers with std::equal_to to be sure that the
container _Equal functor is like the key type ==.
I think we can assume that for any _Equal, not just std::equal_to:
http://eel.is/c++draft/unord.req#12.sentence-5
However ...
Do I need to also consider user partial template specialization
of std::equal_to ? It is a well know bad practice so I hope the
Standard says that such a partial specialization leads to undefined
behavior.
It's certainly not undefined to specialize equal_to, and I'm not sure
how to make your optimisations valid in that case.
Consider:
struct X
{
int i;
int rounded() const { return i - (i % 10); }
bool operator==(X x) const { return i == x.i; }
};
template<> struct std::equal_to
{
bool operator()(X l, X r) const
{ return l.rounded() == r.rounded(); }
};
template<> std::hash
{
bool operator()(X x) const { return hash()(x.rounded()); }
};
std::unordered_multiset u{ X{10}, X{11}, X{12} };
std::unordered_multiset v{ X{15}, X{16}, X{17} };
bool b1 = u == v;
bool b2 = std::is_permutation(u.begin(), u.end(), v.begin());
assert(b1 == b2);
I think the last new specialization in your patch would be used for
this case, and because __x_count == v.count(*u.begin()) it will say
they're equal. But the is_permutation call says they're not.
So I think the assertion would fail, but the standard says it should
pass. Am I mistaken?
I believe the optimization would still be valid if you do not use
__other.count(*__itx) to check for equivalent keys in the other
container. Your patch does:
+ if (__x_count != __other.count(*__itx))
+ return false;
This uses the _Equal predicate to count the equivalent elements in
__other. Instead you need to use operator== to count the **equal**
elements.
I think there's a similar problem in the _Equality specialization for
unordered_map (i.e. key-value pairs, unique keys):
+ const auto __ity = __other.find(__itx->first);
+ if (__ity == __other.end() || !bool(__ity->second == __itx->second))
+ return false;
The call to __other.find(__itx->first) will return an element with
equivalent key, but that's not guaranteed to be equal. I think you
could fix this either by still using == to compare the keys after
__other.find(*__itx) returns an element (which doesn't fix the PR91263
bug) or by replacing find with a similar operation that looks up the
hash code and then uses == to test for equality (instead of using
_Equal pred to test for equivalent keys).
Basically, you can't use functions like find and count that rely on
equivalence of keys, you need to use handwritten lookups using ==.
And if you do that, then it doesn't matter whether _Equal is a
specialization of std::equal_to or not, and it doesn't matter whether
the user has defined their own specialization of std::equal_to. You
can do the optimizations for any _Equal, because you won't actually be
using it to test for equality.
Does that make sense?
Re: [PATCH] libstdc++/91223 Improve unordered containers == operator
On 10/01/20 18:54 +0100, François Dumont wrote:
Hi
Here is my attempt to improve == operator.
There is a small optimization for the std::unordered_mutiXXX
containers but the main enhancement rely on some partial template
specialization of the _Equality type. I limit it to usage of unordered
containers with std::equal_to to be sure that the container _Equal
functor is like the key type ==.
I think we can assume that for any _Equal, not just std::equal_to:
http://eel.is/c++draft/unord.req#12.sentence-5
However ...
Do I need to also consider user partial template specialization of
std::equal_to ? It is a well know bad practice so I hope the Standard
says that such a partial specialization leads to undefined behavior.
It's certainly not undefined to specialize equal_to, and I'm not sure
how to make your optimisations valid in that case.
Consider:
struct X
{
int i;
int rounded() const { return i - (i % 10); }
bool operator==(X x) const { return i == x.i; }
};
template<> struct std::equal_to
{
bool operator()(X l, X r) const
{ return l.rounded() == r.rounded(); }
};
template<> std::hash
{
bool operator()(X x) const { return hash()(x.rounded()); }
};
std::unordered_multiset u{ X{10}, X{11}, X{12} };
std::unordered_multiset v{ X{15}, X{16}, X{17} };
bool b1 = u == v;
bool b2 = std::is_permutation(u.begin(), u.end(), v.begin());
assert(b1 == b2);
I think the last new specialization in your patch would be used for
this case, and because __x_count == v.count(*u.begin()) it will say
they're equal. But the is_permutation call says they're not.
So I think the assertion would fail, but the standard says it should
pass. Am I mistaken?
I saw that the _S_is_permutation has been done in 2012, before
std::is_permutation has been added in 2013. I'll try to replace it in
a future patch.
Yes, that seems like a good idea.
PR libstdc++/91223
* include/bits/hashtable_policy.h
(_Equality<_Key, std::pair, _Alloc,
__detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash,
_RehashPolicy, _Traits, true>): New partial template spetialization.
(_Equality<_Value, _Value, _Alloc, __detail::_Identity,
std::equal_to<_Value>, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>):
Likewise.
(_Equality<_Key, std::pair, _Alloc,
__detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash,
_RehashPolicy, _Traits, false>): Likewise.
(_Equality<_Key, std::pair, _Alloc,
__detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash)
(_RehashPolicy, _Traits, false>): Likewise.
* src/c++11/hashtable_c++0x.cc: Include .
* testsuite/23_containers/unordered_multiset/operators/1.cc
(Hash, Equal, test02, test03): New.
* testsuite/23_containers/unordered_set/operators/1.cc
(Hash, Equal, test02, test03): New.
unordered tests run under Linux x86_64.
Ok to commit after running all tests ?
François
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h
b/libstdc++-v3/include/bits/hashtable_policy.h
index 7bbfdfd375b..2ac3e959320 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -1959,11 +1959,18 @@ namespace __detail
for (auto __itx = __this->begin(); __itx != __this->end();)
{
- const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
+ std::size_t __x_count = 1;
+ auto __itx_end = __itx;
+ for (++__itx_end; __itx_end != __this->end()
+&& __this->key_eq()(_ExtractKey()(*__itx_end),
+_ExtractKey()(*__itx));
+ ++__itx_end)
+ ++__x_count;
This is a nice optimisation.
+ const auto __xrange = std::make_pair(__itx, __itx_end);
const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
- if (std::distance(__xrange.first, __xrange.second)
- != std::distance(__yrange.first, __yrange.second))
+ if (__x_count != std::distance(__yrange.first, __yrange.second))
return false;
if (!_S_is_permutation(__xrange.first, __xrange.second,
@@ -1975,6 +1982,242 @@ namespace __detail
return true;
}
+ /// Specialization.
With the increased number of specializations I think this comment
would be more useful if it said "specialization for multimap", and
change the others to "specialization for multiset" etc.
+ template
+struct _Equality<_Key, std::pair, _Alloc,
+__detail::_Select1st, std::equal_to<_Key>,
+_H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+{
+ using __hashtable = _Hashtable<_Key, std::pair, _Alloc,
+__detail::_Select1st, std::equal_to<_Key>,
+_H1, _H2, _Hash, _RehashPolicy, _Traits>;
+
+ bool
+ _M_equal(const __hashtable&) const;
+};
+
+ template
+bool
+_Equality<_Key, std::pair, _Alloc, __detail::_Select1st,
+
[PATCH] libstdc++/91223 Improve unordered containers == operator
Hi
Here is my attempt to improve == operator.
There is a small optimization for the std::unordered_mutiXXX
containers but the main enhancement rely on some partial template
specialization of the _Equality type. I limit it to usage of unordered
containers with std::equal_to to be sure that the container _Equal
functor is like the key type ==.
Do I need to also consider user partial template specialization of
std::equal_to ? It is a well know bad practice so I hope the Standard
says that such a partial specialization leads to undefined behavior.
I saw that the _S_is_permutation has been done in 2012, before
std::is_permutation has been added in 2013. I'll try to replace it in a
future patch.
PR libstdc++/91223
* include/bits/hashtable_policy.h
(_Equality<_Key, std::pair, _Alloc,
__detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash,
_RehashPolicy, _Traits, true>): New partial template spetialization.
(_Equality<_Value, _Value, _Alloc, __detail::_Identity,
std::equal_to<_Value>, _H1, _H2, _Hash, _RehashPolicy, _Traits, true>):
Likewise.
(_Equality<_Key, std::pair, _Alloc,
__detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash,
_RehashPolicy, _Traits, false>): Likewise.
(_Equality<_Key, std::pair, _Alloc,
__detail::_Select1st, std::equal_to<_Key>, _H1, _H2, _Hash)
(_RehashPolicy, _Traits, false>): Likewise.
* src/c++11/hashtable_c++0x.cc: Include .
* testsuite/23_containers/unordered_multiset/operators/1.cc
(Hash, Equal, test02, test03): New.
* testsuite/23_containers/unordered_set/operators/1.cc
(Hash, Equal, test02, test03): New.
unordered tests run under Linux x86_64.
Ok to commit after running all tests ?
François
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 7bbfdfd375b..2ac3e959320 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -1959,11 +1959,18 @@ namespace __detail
for (auto __itx = __this->begin(); __itx != __this->end();)
{
- const auto __xrange = __this->equal_range(_ExtractKey()(*__itx));
+ std::size_t __x_count = 1;
+ auto __itx_end = __itx;
+ for (++__itx_end; __itx_end != __this->end()
+ && __this->key_eq()(_ExtractKey()(*__itx_end),
+ _ExtractKey()(*__itx));
+ ++__itx_end)
+ ++__x_count;
+
+ const auto __xrange = std::make_pair(__itx, __itx_end);
const auto __yrange = __other.equal_range(_ExtractKey()(*__itx));
- if (std::distance(__xrange.first, __xrange.second)
- != std::distance(__yrange.first, __yrange.second))
+ if (__x_count != std::distance(__yrange.first, __yrange.second))
return false;
if (!_S_is_permutation(__xrange.first, __xrange.second,
@@ -1975,6 +1982,242 @@ namespace __detail
return true;
}
+ /// Specialization.
+ template
+struct _Equality<_Key, std::pair, _Alloc,
+ __detail::_Select1st, std::equal_to<_Key>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits, true>
+{
+ using __hashtable = _Hashtable<_Key, std::pair, _Alloc,
+ __detail::_Select1st, std::equal_to<_Key>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>;
+
+ bool
+ _M_equal(const __hashtable&) const;
+};
+
+ template
+bool
+_Equality<_Key, std::pair, _Alloc, __detail::_Select1st,
+ std::equal_to<_Key>, _H1, _H2,
+ _Hash, _RehashPolicy, _Traits, true>::
+_M_equal(const __hashtable& __other) const
+{
+ const __hashtable* __this = static_cast(this);
+
+ if (__this->size() != __other.size())
+ return false;
+
+ for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
+ {
+ const auto __ity = __other.find(__itx->first);
+ if (__ity == __other.end() || !bool(__ity->second == __itx->second))
+ return false;
+ }
+ return true;
+}
+
+ /// Specialization.
+ template
+ struct _Equality<_Value, _Value, _Alloc, __detail::_Identity,
+ std::equal_to<_Value>, _H1, _H2,
+ _Hash, _RehashPolicy, _Traits, true>
+{
+ using __hashtable = _Hashtable<_Value, _Value, _Alloc,
+ __detail::_Identity, std::equal_to<_Value>,
+ _H1, _H2, _Hash, _RehashPolicy, _Traits>;
+
+ bool
+ _M_equal(const __hashtable&) const;
+};
+
+ template
+bool
+_Equality<_Value, _Value, _Alloc, __detail::_Identity,
+ std::equal_to<_Value>, _H1, _H2,
+ _Hash, _RehashPolicy, _Traits, true>::
+_M_equal(const __hashtable& __other) const
+{
+ const __hashtable* __this = static_cast(this);
+
+ if (__this->size() != __other.size())
+ return false;
+
+ for (auto __itx = __this->begin(); __itx != __this->end(); ++__itx)
+ if (__other.find(*__itx) == __other.end())
+ return false;
+
+ return true;
+}
+
+ /// Specialization.
+ template
+struct _Equality<_Key, std::pair, _Alloc,
+ __detail::_Select1st,
