[libc++] __key_equiv is sometimes 2x expensive#175087
[libc++] __key_equiv is sometimes 2x expensive#175087
Conversation
|
@llvm/pr-subscribers-libcxx Author: None (halbi2) ChangesMaybe __key_equiv is wrongly named. It could be __key_not_greater. The definition for flat_multiset is wrong (should be same as flat_set, not same as flat_map). The definitions for flat_multiset and flat_multimap are unused so I removed them. Fixes #175086 @huixie please take a look. This patch reduces the number of comparisons used by that test program from 27 to only 18 so I think it is a large improvement. Full diff: https://github.com/llvm/llvm-project/pull/175087.diff 4 Files Affected:
diff --git a/libcxx/include/__flat_map/flat_map.h b/libcxx/include/__flat_map/flat_map.h
index 50487cada24c0..cd97584bbbeed 100644
--- a/libcxx/include/__flat_map/flat_map.h
+++ b/libcxx/include/__flat_map/flat_map.h
@@ -1138,8 +1138,9 @@ class flat_map {
struct __key_equiv {
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
- operator()(const_reference __x, const_reference __y) const {
- return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
+ operator()(const auto& __x, const auto& __y) const {
+ // __x is less or equal to __y because the range is already sorted
+ return !__comp_(std::get<0>(__x), std::get<0>(__y));
}
key_compare __comp_;
};
diff --git a/libcxx/include/__flat_map/flat_multimap.h b/libcxx/include/__flat_map/flat_multimap.h
index 72e3b5f21670c..bd3ec81b98b7f 100644
--- a/libcxx/include/__flat_map/flat_multimap.h
+++ b/libcxx/include/__flat_map/flat_multimap.h
@@ -934,15 +934,6 @@ class flat_multimap {
containers __containers_;
_LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
-
- struct __key_equiv {
- _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}
- _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
- operator()(const_reference __x, const_reference __y) const {
- return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
- }
- key_compare __comp_;
- };
};
template <class _KeyContainer, class _MappedContainer, class _Compare = less<typename _KeyContainer::value_type>>
diff --git a/libcxx/include/__flat_set/flat_multiset.h b/libcxx/include/__flat_set/flat_multiset.h
index b2de63bc3038c..4324645fb8445 100644
--- a/libcxx/include/__flat_set/flat_multiset.h
+++ b/libcxx/include/__flat_set/flat_multiset.h
@@ -745,15 +745,6 @@ class flat_multiset {
_KeyContainer __keys_;
_LIBCPP_NO_UNIQUE_ADDRESS key_compare __compare_;
-
- struct __key_equiv {
- _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}
- _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
- operator()(const_reference __x, const_reference __y) const {
- return !__comp_(std::get<0>(__x), std::get<0>(__y)) && !__comp_(std::get<0>(__y), std::get<0>(__x));
- }
- key_compare __comp_;
- };
};
template <class _KeyContainer, class _Compare = less<typename _KeyContainer::value_type>>
diff --git a/libcxx/include/__flat_set/flat_set.h b/libcxx/include/__flat_set/flat_set.h
index 57c3926e33b68..4c24f56423b5c 100644
--- a/libcxx/include/__flat_set/flat_set.h
+++ b/libcxx/include/__flat_set/flat_set.h
@@ -784,8 +784,9 @@ class flat_set {
struct __key_equiv {
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 __key_equiv(key_compare __c) : __comp_(__c) {}
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX26 bool
- operator()(const_reference __x, const_reference __y) const {
- return !__comp_(__x, __y) && !__comp_(__y, __x);
+ operator()(const auto& __x, const auto& __y) const {
+ // __x is less or equal to __y because the range is already sorted
+ return !__comp_(__x, __y);
}
key_compare __comp_;
};
|
|
✅ With the latest revision this PR passed the C/C++ code formatter. |
libcxx/include/__flat_map/flat_map.h
Outdated
| @@ -1137,9 +1137,9 @@ class flat_map { | |||
|
|
|||
| struct __key_equiv { | |||
There was a problem hiding this comment.
If we want to reform the functors in this way, we should rename them (maybe to __key_greater_or_equal_to or __key_not_less).
Also, we should post benchmark results somewhere.
There was a problem hiding this comment.
It's a bit unfortunate that usages of ranges::unique is no longer pedantically correct due to [alg.unique]/9.2.1 - ranges::unique expects the comparator to express an equivalence relation.
I think we should use some other another algorithm. It seems that potential future refactoring of ranges::unique can break the current strategy.
philnik777
left a comment
There was a problem hiding this comment.
I don't think this is a good idea, at least as-is. ranges::unique requires the predicate to be an equivalence relation, which the new definition of __key_equiv isn't, which means that this patch introduces UB.
Rename to __key_not_less. Rename and comment on __unique to __unchecked_unique: ranges::unique has UB but internal function helper __unchecked_unique does not have UB. Fixes llvm#175086
libcxx/include/__algorithm/unique.h
Outdated
| template <class _AlgPolicy, class _Iter, class _Sent, class _BinaryPredicate> | ||
| [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 std::pair<_Iter, _Iter> | ||
| __unique(_Iter __first, _Sent __last, _BinaryPredicate&& __pred) { | ||
| __unchecked_unique(_Iter __first, _Sent __last, _BinaryPredicate&& __pred) { |
There was a problem hiding this comment.
it is unclear to me what the meaning of this unchecked is. I stiff prefer the old name __unique , which matches our convention for all algorithms. __foo is the internal function that is shared between std::foo and std::ranges::foo.
I think what others concern is not only about equivalent_relation concept, it is also about the semantic of this algorithm. Even the c++17 version has a "equivalence relation" precondition. It happens that the implementation is currently invoking the predicate only in one direction. if the implementation of unique one day does something different in the future, this could break.
There was a problem hiding this comment.
The meaning of this is that this internal helper algorithm does not have the semantic of the std::unique algorithm, that checks where the predicate is an equivalence relation and otherwise UB. This algorithm is unchecked, does not require equivalence relation. There it is different to even the c++17 version. This helper algorithm does not have the same semantics as std::unique or ranges::unique, therefore it should not have the same name, so I have changed its name accordingly.
"if the implementation of unique one day does something different in the future, this could break" -- I do not understand your meaning. This unchecked algorithm is libc++'s implementation of unique, is it not? How could it do something different, without breaking libc++?
This helper function could be named __oneway_unique -- the predicate is evaluated only one way -- or __unconstrained_unique -- it has no constraints -- instead of __unchecked_unique. I only copied unchecked from other places in libc++ where a preconditioned helper is used.
There was a problem hiding this comment.
I'm not a huge fan of the naming either. To me this currently implies that we simply don't check some semantic requirement/precondition, which is not the case. However, I do agree with @halbi2 that it shouldn't be __unique, since that implies the same semantics as {std,ranges}::unique, which we don't want. This function actually has different semantics, or at least preconditions. WDYT about __unique_sorted_range?
There was a problem hiding this comment.
@philnik777 I have renamed the function as you asked. Can you merge this improvement please?
philnik777
left a comment
There was a problem hiding this comment.
Please provide benchmark results as well and remove any @ mentions from the commit message.
libcxx/include/__algorithm/unique.h
Outdated
| template <class _AlgPolicy, class _Iter, class _Sent, class _BinaryPredicate> | ||
| [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 std::pair<_Iter, _Iter> | ||
| __unique(_Iter __first, _Sent __last, _BinaryPredicate&& __pred) { | ||
| __unchecked_unique(_Iter __first, _Sent __last, _BinaryPredicate&& __pred) { |
There was a problem hiding this comment.
I'm not a huge fan of the naming either. To me this currently implies that we simply don't check some semantic requirement/precondition, which is not the case. However, I do agree with @halbi2 that it shouldn't be __unique, since that implies the same semantics as {std,ranges}::unique, which we don't want. This function actually has different semantics, or at least preconditions. WDYT about __unique_sorted_range?
Currently there is no benchmark for constructing a This patch obviously does not do anything except remove excess calls to the comparator. I do not think a benchmark will show much data. |
how can we explain the consistent speed up in the |
The benchmark is not very good, it is noisy. Perhaps my computer is faster on the second run. I do not care about the benchmark because the change is very obvious and trivial. @huixie90 could you help me merge this please? |
I think I am happy with the current state of the PR. I will wait for @philnik777 to confirm if his concerns have been addressed |
| [[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator | ||
| unique(_ForwardIterator __first, _ForwardIterator __last, _BinaryPredicate __pred) { | ||
| return std::__unique<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __pred).first; | ||
| return std::__unique_sorted_range<_ClassicAlgPolicy>(std::move(__first), std::move(__last), __pred).first; |
There was a problem hiding this comment.
This seems incorrect conceptually. std::unique isn't guaranteed to be given a sorted range.
There was a problem hiding this comment.
I don't understand. Do you want me to duplicate the code, or what? Please instruct me what to do.
There was a problem hiding this comment.
__deduplicate_on_non_front_back_relation (which means deduplicating when !pred(front_element, back_element)) seems to be a less misleading name, but I'm not sure whether it's too complicated to read.
It's a bit hard to name it because we want to allow the relation to be equivalence or ordering.
There was a problem hiding this comment.
Duplicating the code is one option. Another option would be a somewhat different name. Maybe something like __deduplicate_if? IDK. I'm kinda tempted to say we should just introduce a flat_{set,map}-specific algorithm that takes the underlying container and destroys the non-unique elements. That would give us an API to improve this more (e.g. by making use of trivially relocatable concepts).
There was a problem hiding this comment.
@philnik777: Can you explain about "making use of trivially relocatable concepts"? I don't see what you mean.
What can I do to help you merge this very simple performance improvement to your library?
There was a problem hiding this comment.
@frederick-vs-ja can you help me land this patch please?
|
@philnik777 ping |
Rename to __key_not_less. Rename and comment on __unique
to __unchecked_unique: ranges::unique has UB but internal
function helper __unchecked_unique does not have UB.
Fixes #175086
This patch reduces the number of comparisons used by that test program from 27 to only 18 so I think it is a large improvement.