[libc++] Optimize {set,map}::{lower,upper}_bound#161366
Merged
Merged
Conversation
Member
|
@llvm/pr-subscribers-libcxx Author: Nikolas Klauser (philnik777) ChangesApple M4: Full diff: https://github.com/llvm/llvm-project/pull/161366.diff 3 Files Affected:
diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index 61c910c52c536..ef53bf1fa8364 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -1165,6 +1165,48 @@ public:
template <class _Key>
_LIBCPP_HIDE_FROM_ABI size_type __count_multi(const _Key& __k) const;
+ template <bool _LowerBound, class _Key>
+ _LIBCPP_HIDE_FROM_ABI __end_node_pointer __lower_upper_bound_unique_impl(const _Key& __v) const {
+ auto __rt = __root();
+ auto __result = __end_node();
+ auto __comp = __lazy_synth_three_way_comparator<_Compare, _Key, value_type>(value_comp());
+ while (__rt != nullptr) {
+ auto __comp_res = __comp(__v, __rt->__get_value());
+
+ if (__comp_res.__less()) {
+ __result = static_cast<__end_node_pointer>(__rt);
+ __rt = static_cast<__node_pointer>(__rt->__left_);
+ } else if (__comp_res.__greater()) {
+ __rt = static_cast<__node_pointer>(__rt->__right_);
+ } else if _LIBCPP_CONSTEXPR (_LowerBound) {
+ return static_cast<__end_node_pointer>(__rt);
+ } else {
+ return __rt->__right_ ? static_cast<__end_node_pointer>(std::__tree_min(__rt->__right_)) : __result;
+ }
+ }
+ return __result;
+ }
+
+ template <class _Key>
+ _LIBCPP_HIDE_FROM_ABI iterator __lower_bound_unique(const _Key& __v) {
+ return iterator(__lower_upper_bound_unique_impl<true>(__v));
+ }
+
+ template <class _Key>
+ _LIBCPP_HIDE_FROM_ABI const_iterator __lower_bound_unique(const _Key& __v) const {
+ return const_iterator(__lower_upper_bound_unique_impl<true>(__v));
+ }
+
+ template <class _Key>
+ _LIBCPP_HIDE_FROM_ABI iterator __upper_bound_unique(const _Key& __v) {
+ return iterator(__lower_upper_bound_unique_impl<false>(__v));
+ }
+
+ template <class _Key>
+ _LIBCPP_HIDE_FROM_ABI const_iterator __upper_bound_unique(const _Key& __v) const {
+ return iterator(__lower_upper_bound_unique_impl<false>(__v));
+ }
+
template <class _Key>
_LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _Key& __v) {
return __lower_bound(__v, __root(), __end_node());
diff --git a/libcxx/include/map b/libcxx/include/map
index a63dfec910aae..58840556d42f5 100644
--- a/libcxx/include/map
+++ b/libcxx/include/map
@@ -1269,7 +1269,9 @@ public:
# endif // _LIBCPP_STD_VER >= 20
_LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
- _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
+ _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const {
+ return __tree_.__lower_bound_unique(__k);
+ }
# if _LIBCPP_STD_VER >= 14
template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
_LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
@@ -1282,8 +1284,10 @@ public:
}
# endif
- _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
- _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
+ _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.__upper_bound_unique(__k); }
+ _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const {
+ return __tree_.__upper_bound_unique(__k);
+ }
# if _LIBCPP_STD_VER >= 14
template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
_LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
diff --git a/libcxx/include/set b/libcxx/include/set
index 75529e7bac6ff..f77dc4821e997 100644
--- a/libcxx/include/set
+++ b/libcxx/include/set
@@ -849,8 +849,10 @@ public:
}
# endif // _LIBCPP_STD_VER >= 20
- _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.lower_bound(__k); }
- _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const { return __tree_.lower_bound(__k); }
+ _LIBCPP_HIDE_FROM_ABI iterator lower_bound(const key_type& __k) { return __tree_.__lower_bound_unique(__k); }
+ _LIBCPP_HIDE_FROM_ABI const_iterator lower_bound(const key_type& __k) const {
+ return __tree_.__lower_bound_unique(__k);
+ }
# if _LIBCPP_STD_VER >= 14
template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
_LIBCPP_HIDE_FROM_ABI iterator lower_bound(const _K2& __k) {
@@ -863,8 +865,10 @@ public:
}
# endif
- _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.upper_bound(__k); }
- _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const { return __tree_.upper_bound(__k); }
+ _LIBCPP_HIDE_FROM_ABI iterator upper_bound(const key_type& __k) { return __tree_.__upper_bound_unique(__k); }
+ _LIBCPP_HIDE_FROM_ABI const_iterator upper_bound(const key_type& __k) const {
+ return __tree_.__upper_bound_unique(__k);
+ }
# if _LIBCPP_STD_VER >= 14
template <typename _K2, enable_if_t<__is_transparent_v<_Compare, _K2>, int> = 0>
_LIBCPP_HIDE_FROM_ABI iterator upper_bound(const _K2& __k) {
|
ldionne
reviewed
Oct 1, 2025
98737ea to
bf8685a
Compare
ldionne
requested changes
Oct 6, 2025
bf8685a to
4e6971e
Compare
|
✅ With the latest revision this PR passed the C/C++ code formatter. |
4e6971e to
7ee59ec
Compare
ldionne
approved these changes
Oct 8, 2025
akadutta
pushed a commit
to akadutta/llvm-project
that referenced
this pull request
Oct 14, 2025
Apple M4: ``` Benchmark Baseline Candidate Difference % Difference --------------------------------------------------------------------------------------------- ---------- ----------- ------------ -------------- std::map<int,_int>::lower_bound(key)_(existent)/0 0.01 0.01 -0.00 -25.78 std::map<int,_int>::lower_bound(key)_(existent)/1024 7.94 4.28 -3.66 -46.09 std::map<int,_int>::lower_bound(key)_(existent)/32 2.73 1.69 -1.03 -37.89 std::map<int,_int>::lower_bound(key)_(existent)/8192 11.63 5.52 -6.11 -52.55 std::map<int,_int>::lower_bound(key)_(non-existent)/0 0.28 0.28 -0.00 -1.35 std::map<int,_int>::lower_bound(key)_(non-existent)/1024 17.21 7.63 -9.58 -55.67 std::map<int,_int>::lower_bound(key)_(non-existent)/32 4.71 3.26 -1.45 -30.71 std::map<int,_int>::lower_bound(key)_(non-existent)/8192 26.82 10.58 -16.24 -60.55 std::map<int,_int>::upper_bound(key)_(existent)/0 0.01 0.01 0.00 20.62 std::map<int,_int>::upper_bound(key)_(existent)/1024 7.93 3.61 -4.32 -54.49 std::map<int,_int>::upper_bound(key)_(existent)/32 2.83 1.98 -0.85 -30.01 std::map<int,_int>::upper_bound(key)_(existent)/8192 11.69 5.72 -5.97 -51.06 std::map<int,_int>::upper_bound(key)_(non-existent)/0 0.28 0.28 -0.00 -1.36 std::map<int,_int>::upper_bound(key)_(non-existent)/1024 17.21 8.00 -9.21 -53.53 std::map<int,_int>::upper_bound(key)_(non-existent)/32 4.70 2.93 -1.78 -37.76 std::map<int,_int>::upper_bound(key)_(non-existent)/8192 26.54 11.18 -15.36 -57.89 std::map<std::string,_int>::lower_bound(key)_(existent)/0 0.04 0.04 -0.00 -3.26 std::map<std::string,_int>::lower_bound(key)_(existent)/1024 27.46 26.25 -1.22 -4.43 std::map<std::string,_int>::lower_bound(key)_(existent)/32 19.17 15.71 -3.46 -18.07 std::map<std::string,_int>::lower_bound(key)_(existent)/8192 35.33 35.03 -0.30 -0.84 std::map<std::string,_int>::lower_bound(key)_(non-existent)/0 0.27 0.27 -0.00 -1.45 std::map<std::string,_int>::lower_bound(key)_(non-existent)/1024 24.88 24.17 -0.70 -2.83 std::map<std::string,_int>::lower_bound(key)_(non-existent)/32 11.67 11.63 -0.04 -0.32 std::map<std::string,_int>::lower_bound(key)_(non-existent)/8192 31.81 32.33 0.52 1.64 std::map<std::string,_int>::upper_bound(key)_(existent)/0 0.04 0.04 -0.00 -2.22 std::map<std::string,_int>::upper_bound(key)_(existent)/1024 29.91 26.51 -3.40 -11.38 std::map<std::string,_int>::upper_bound(key)_(existent)/32 19.69 17.74 -1.95 -9.92 std::map<std::string,_int>::upper_bound(key)_(existent)/8192 32.55 35.24 2.69 8.25 std::map<std::string,_int>::upper_bound(key)_(non-existent)/0 0.27 0.27 -0.00 -1.74 std::map<std::string,_int>::upper_bound(key)_(non-existent)/1024 23.87 26.77 2.91 12.18 std::map<std::string,_int>::upper_bound(key)_(non-existent)/32 11.44 11.81 0.37 3.24 std::map<std::string,_int>::upper_bound(key)_(non-existent)/8192 33.02 32.59 -0.43 -1.29 std::set<int>::lower_bound(key)_(existent)/0 0.01 0.01 0.00 0.48 std::set<int>::lower_bound(key)_(existent)/1024 7.83 4.21 -3.62 -46.23 std::set<int>::lower_bound(key)_(existent)/32 2.74 1.68 -1.06 -38.81 std::set<int>::lower_bound(key)_(existent)/8192 22.75 11.12 -11.63 -51.12 std::set<int>::lower_bound(key)_(non-existent)/0 0.28 0.27 -0.01 -3.52 std::set<int>::lower_bound(key)_(non-existent)/1024 17.15 8.40 -8.75 -51.03 std::set<int>::lower_bound(key)_(non-existent)/32 4.63 2.50 -2.13 -46.03 std::set<int>::lower_bound(key)_(non-existent)/8192 28.88 11.05 -17.82 -61.72 std::set<int>::upper_bound(key)_(existent)/0 0.01 0.01 -0.00 -7.79 std::set<int>::upper_bound(key)_(existent)/1024 7.80 3.63 -4.16 -53.42 std::set<int>::upper_bound(key)_(existent)/32 2.81 1.90 -0.91 -32.44 std::set<int>::upper_bound(key)_(existent)/8192 21.93 11.35 -10.58 -48.26 std::set<int>::upper_bound(key)_(non-existent)/0 0.28 0.27 -0.01 -3.81 std::set<int>::upper_bound(key)_(non-existent)/1024 16.76 7.38 -9.38 -55.98 std::set<int>::upper_bound(key)_(non-existent)/32 4.58 3.10 -1.48 -32.31 std::set<int>::upper_bound(key)_(non-existent)/8192 26.95 10.70 -16.25 -60.29 std::set<std::string>::lower_bound(key)_(existent)/0 0.04 0.04 0.00 0.02 std::set<std::string>::lower_bound(key)_(existent)/1024 28.08 27.04 -1.04 -3.71 std::set<std::string>::lower_bound(key)_(existent)/32 17.53 16.94 -0.58 -3.34 std::set<std::string>::lower_bound(key)_(existent)/8192 32.79 33.28 0.49 1.49 std::set<std::string>::lower_bound(key)_(non-existent)/0 0.28 0.28 -0.00 -0.06 std::set<std::string>::lower_bound(key)_(non-existent)/1024 25.23 24.38 -0.85 -3.38 std::set<std::string>::lower_bound(key)_(non-existent)/32 11.45 11.68 0.24 2.07 std::set<std::string>::lower_bound(key)_(non-existent)/8192 32.30 36.80 4.50 13.95 std::set<std::string>::upper_bound(key)_(existent)/0 0.04 0.04 -0.00 -0.14 std::set<std::string>::upper_bound(key)_(existent)/1024 26.71 26.37 -0.34 -1.27 std::set<std::string>::upper_bound(key)_(existent)/32 20.07 19.06 -1.02 -5.06 std::set<std::string>::upper_bound(key)_(existent)/8192 36.69 35.50 -1.19 -3.25 std::set<std::string>::upper_bound(key)_(non-existent)/0 0.28 0.28 -0.00 -0.16 std::set<std::string>::upper_bound(key)_(non-existent)/1024 24.48 24.90 0.42 1.73 std::set<std::string>::upper_bound(key)_(non-existent)/32 11.68 11.77 0.09 0.77 std::set<std::string>::upper_bound(key)_(non-existent)/8192 33.16 34.12 0.96 2.89 ```
Member
|
(re-posting since I previously posted before the end of the meeting by mistake, which we're not supposed to do) For posterity, while the validity of this optimization was challenged due to the Boost.ICL issue linked, LEWG reinforced libc++'s interpretation of the Standard when it discussed LWG 4572 at the Brno meeting, confirming that this optimization is valid. |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
3 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Apple M4: