aboutsummaryrefslogtreecommitdiff
path: root/libcxx/include
diff options
context:
space:
mode:
Diffstat (limited to 'libcxx/include')
-rw-r--r--libcxx/include/__algorithm/find.h110
-rw-r--r--libcxx/include/__algorithm/simd_utils.h5
-rw-r--r--libcxx/include/__flat_map/flat_map.h2
-rw-r--r--libcxx/include/__flat_map/flat_multimap.h5
-rw-r--r--libcxx/include/__flat_map/key_value_iterator.h1
-rw-r--r--libcxx/include/__flat_set/flat_multiset.h14
-rw-r--r--libcxx/include/__flat_set/flat_set.h8
-rw-r--r--libcxx/include/module.modulemap.in7
8 files changed, 98 insertions, 54 deletions
diff --git a/libcxx/include/__algorithm/find.h b/libcxx/include/__algorithm/find.h
index 8c8cb58..5f32ae8 100644
--- a/libcxx/include/__algorithm/find.h
+++ b/libcxx/include/__algorithm/find.h
@@ -12,6 +12,7 @@
#include <__algorithm/find_segment_if.h>
#include <__algorithm/min.h>
+#include <__algorithm/simd_utils.h>
#include <__algorithm/unwrap_iter.h>
#include <__bit/countr.h>
#include <__bit/invert_if.h>
@@ -44,39 +45,102 @@ _LIBCPP_BEGIN_NAMESPACE_STD
// generic implementation
template <class _Iter, class _Sent, class _Tp, class _Proj>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter
-__find(_Iter __first, _Sent __last, const _Tp& __value, _Proj& __proj) {
+__find_loop(_Iter __first, _Sent __last, const _Tp& __value, _Proj& __proj) {
for (; __first != __last; ++__first)
if (std::__invoke(__proj, *__first) == __value)
break;
return __first;
}
-// trivially equality comparable implementations
-template <class _Tp,
- class _Up,
- class _Proj,
- __enable_if_t<__is_identity<_Proj>::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value &&
- sizeof(_Tp) == 1,
- int> = 0>
-_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* __find(_Tp* __first, _Tp* __last, const _Up& __value, _Proj&) {
- if (auto __ret = std::__constexpr_memchr(__first, __value, __last - __first))
- return __ret;
- return __last;
+template <class _Iter, class _Sent, class _Tp, class _Proj>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter
+__find(_Iter __first, _Sent __last, const _Tp& __value, _Proj& __proj) {
+ return std::__find_loop(std::move(__first), std::move(__last), __value, __proj);
}
-#if _LIBCPP_HAS_WIDE_CHARACTERS
-template <class _Tp,
- class _Up,
- class _Proj,
- __enable_if_t<__is_identity<_Proj>::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value &&
- sizeof(_Tp) == sizeof(wchar_t) && _LIBCPP_ALIGNOF(_Tp) >= _LIBCPP_ALIGNOF(wchar_t),
- int> = 0>
+#if _LIBCPP_VECTORIZE_ALGORITHMS
+template <class _Tp, class _Up>
+[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI
+_LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* __find_vectorized(_Tp* __first, _Tp* __last, _Up __value) {
+ if (!__libcpp_is_constant_evaluated()) {
+ constexpr size_t __unroll_count = 4;
+ constexpr size_t __vec_size = __native_vector_size<_Tp>;
+ using __vec = __simd_vector<_Tp, __vec_size>;
+
+ auto __orig_first = __first;
+
+ auto __values = static_cast<__simd_vector<_Up, __vec_size>>(__value); // broadcast the value
+ while (static_cast<size_t>(__last - __first) >= __unroll_count * __vec_size) [[__unlikely__]] {
+ __vec __lhs[__unroll_count];
+
+ for (size_t __i = 0; __i != __unroll_count; ++__i)
+ __lhs[__i] = std::__load_vector<__vec>(__first + __i * __vec_size);
+
+ for (size_t __i = 0; __i != __unroll_count; ++__i) {
+ if (auto __cmp_res = __lhs[__i] == __values; std::__any_of(__cmp_res)) {
+ auto __offset = __i * __vec_size + std::__find_first_set(__cmp_res);
+ return __first + __offset;
+ }
+ }
+
+ __first += __unroll_count * __vec_size;
+ }
+
+ // check the remaining 0-3 vectors
+ while (static_cast<size_t>(__last - __first) >= __vec_size) {
+ if (auto __cmp_res = std::__load_vector<__vec>(__first) == __values; std::__any_of(__cmp_res)) {
+ return __first + std::__find_first_set(__cmp_res);
+ }
+ __first += __vec_size;
+ }
+
+ if (__last - __first == 0)
+ return __first;
+
+ // Check if we can load elements in front of the current pointer. If that's the case load a vector at
+ // (last - vector_size) to check the remaining elements
+ if (static_cast<size_t>(__first - __orig_first) >= __vec_size) {
+ __first = __last - __vec_size;
+ return __first + std::__find_first_set(std::__load_vector<__vec>(__first) == __values);
+ }
+ }
+
+ __identity __proj;
+ return std::__find_loop(__first, __last, __value, __proj);
+}
+#endif
+
+#ifndef _LIBCPP_CXX03_LANG
+// trivially equality comparable implementations
+template <
+ class _Tp,
+ class _Up,
+ class _Proj,
+ __enable_if_t<__is_identity<_Proj>::value && __libcpp_is_trivially_equality_comparable<_Tp, _Up>::value, int> = 0>
_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp* __find(_Tp* __first, _Tp* __last, const _Up& __value, _Proj&) {
- if (auto __ret = std::__constexpr_wmemchr(__first, __value, __last - __first))
- return __ret;
- return __last;
+ if constexpr (sizeof(_Tp) == 1) {
+ if (auto __ret = std::__constexpr_memchr(__first, __value, __last - __first))
+ return __ret;
+ return __last;
+ }
+# if _LIBCPP_HAS_WIDE_CHARACTERS
+ else if constexpr (sizeof(_Tp) == sizeof(wchar_t) && _LIBCPP_ALIGNOF(_Tp) >= _LIBCPP_ALIGNOF(wchar_t)) {
+ if (auto __ret = std::__constexpr_wmemchr(__first, __value, __last - __first))
+ return __ret;
+ return __last;
+ }
+# endif
+# if _LIBCPP_VECTORIZE_ALGORITHMS
+ else if constexpr (is_integral<_Tp>::value) {
+ return std::__find_vectorized(__first, __last, __value);
+ }
+# endif
+ else {
+ __identity __proj;
+ return std::__find_loop(__first, __last, __value, __proj);
+ }
}
-#endif // _LIBCPP_HAS_WIDE_CHARACTERS
+#endif
// TODO: This should also be possible to get right with different signedness
// cast integral types to allow vectorization
diff --git a/libcxx/include/__algorithm/simd_utils.h b/libcxx/include/__algorithm/simd_utils.h
index 96b074c..aaeb8a8 100644
--- a/libcxx/include/__algorithm/simd_utils.h
+++ b/libcxx/include/__algorithm/simd_utils.h
@@ -115,6 +115,11 @@ template <class _VecT, class _Iter>
}
template <class _Tp, size_t _Np>
+[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool __any_of(__simd_vector<_Tp, _Np> __vec) noexcept {
+ return __builtin_reduce_or(__builtin_convertvector(__vec, __simd_vector<bool, _Np>));
+}
+
+template <class _Tp, size_t _Np>
[[__nodiscard__]] _LIBCPP_HIDE_FROM_ABI bool __all_of(__simd_vector<_Tp, _Np> __vec) noexcept {
return __builtin_reduce_and(__builtin_convertvector(__vec, __simd_vector<bool, _Np>));
}
diff --git a/libcxx/include/__flat_map/flat_map.h b/libcxx/include/__flat_map/flat_map.h
index 31ba9bc..7bb235b 100644
--- a/libcxx/include/__flat_map/flat_map.h
+++ b/libcxx/include/__flat_map/flat_map.h
@@ -29,7 +29,6 @@
#include <__flat_map/key_value_iterator.h>
#include <__flat_map/sorted_unique.h>
#include <__flat_map/utils.h>
-#include <__functional/invoke.h>
#include <__functional/is_transparent.h>
#include <__functional/operations.h>
#include <__fwd/memory.h>
@@ -48,7 +47,6 @@
#include <__ranges/container_compatible_range.h>
#include <__ranges/drop_view.h>
#include <__ranges/from_range.h>
-#include <__ranges/ref_view.h>
#include <__ranges/size.h>
#include <__ranges/subrange.h>
#include <__ranges/zip_view.h>
diff --git a/libcxx/include/__flat_map/flat_multimap.h b/libcxx/include/__flat_map/flat_multimap.h
index abaacf9..96d9454 100644
--- a/libcxx/include/__flat_map/flat_multimap.h
+++ b/libcxx/include/__flat_map/flat_multimap.h
@@ -22,7 +22,6 @@
#include <__algorithm/upper_bound.h>
#include <__assert>
#include <__compare/synth_three_way.h>
-#include <__concepts/convertible_to.h>
#include <__concepts/swappable.h>
#include <__config>
#include <__cstddef/byte.h>
@@ -30,7 +29,6 @@
#include <__flat_map/key_value_iterator.h>
#include <__flat_map/sorted_equivalent.h>
#include <__flat_map/utils.h>
-#include <__functional/invoke.h>
#include <__functional/is_transparent.h>
#include <__functional/operations.h>
#include <__fwd/vector.h>
@@ -47,7 +45,6 @@
#include <__ranges/container_compatible_range.h>
#include <__ranges/drop_view.h>
#include <__ranges/from_range.h>
-#include <__ranges/ref_view.h>
#include <__ranges/size.h>
#include <__ranges/subrange.h>
#include <__ranges/zip_view.h>
@@ -57,14 +54,12 @@
#include <__type_traits/is_allocator.h>
#include <__type_traits/is_nothrow_constructible.h>
#include <__type_traits/is_same.h>
-#include <__type_traits/maybe_const.h>
#include <__utility/exception_guard.h>
#include <__utility/move.h>
#include <__utility/pair.h>
#include <__utility/scope_guard.h>
#include <__vector/vector.h>
#include <initializer_list>
-#include <stdexcept>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
diff --git a/libcxx/include/__flat_map/key_value_iterator.h b/libcxx/include/__flat_map/key_value_iterator.h
index d04a23d..795651a 100644
--- a/libcxx/include/__flat_map/key_value_iterator.h
+++ b/libcxx/include/__flat_map/key_value_iterator.h
@@ -20,7 +20,6 @@
#include <__type_traits/conditional.h>
#include <__utility/forward.h>
#include <__utility/move.h>
-#include <__utility/pair.h>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
# pragma GCC system_header
diff --git a/libcxx/include/__flat_set/flat_multiset.h b/libcxx/include/__flat_set/flat_multiset.h
index 65f4161..b1a4917 100644
--- a/libcxx/include/__flat_set/flat_multiset.h
+++ b/libcxx/include/__flat_set/flat_multiset.h
@@ -13,54 +13,40 @@
#include <__algorithm/equal_range.h>
#include <__algorithm/lexicographical_compare_three_way.h>
#include <__algorithm/lower_bound.h>
-#include <__algorithm/min.h>
#include <__algorithm/ranges_equal.h>
#include <__algorithm/ranges_inplace_merge.h>
#include <__algorithm/ranges_is_sorted.h>
#include <__algorithm/ranges_sort.h>
-#include <__algorithm/ranges_unique.h>
#include <__algorithm/remove_if.h>
#include <__algorithm/upper_bound.h>
#include <__assert>
#include <__compare/synth_three_way.h>
-#include <__concepts/convertible_to.h>
#include <__concepts/swappable.h>
#include <__config>
-#include <__cstddef/byte.h>
-#include <__cstddef/ptrdiff_t.h>
-#include <__flat_map/key_value_iterator.h>
#include <__flat_map/sorted_equivalent.h>
#include <__flat_set/ra_iterator.h>
#include <__flat_set/utils.h>
-#include <__functional/invoke.h>
#include <__functional/is_transparent.h>
#include <__functional/operations.h>
#include <__fwd/vector.h>
#include <__iterator/concepts.h>
-#include <__iterator/distance.h>
#include <__iterator/iterator_traits.h>
#include <__iterator/prev.h>
-#include <__iterator/ranges_iterator_traits.h>
#include <__iterator/reverse_iterator.h>
#include <__memory/allocator_traits.h>
#include <__memory/uses_allocator.h>
#include <__memory/uses_allocator_construction.h>
-#include <__ranges/access.h>
#include <__ranges/concepts.h>
#include <__ranges/container_compatible_range.h>
#include <__ranges/drop_view.h>
#include <__ranges/from_range.h>
-#include <__ranges/ref_view.h>
#include <__ranges/size.h>
#include <__ranges/subrange.h>
-#include <__ranges/zip_view.h>
-#include <__type_traits/conjunction.h>
#include <__type_traits/container_traits.h>
#include <__type_traits/invoke.h>
#include <__type_traits/is_allocator.h>
#include <__type_traits/is_nothrow_constructible.h>
#include <__type_traits/is_same.h>
-#include <__type_traits/maybe_const.h>
#include <__utility/as_const.h>
#include <__utility/exception_guard.h>
#include <__utility/move.h>
diff --git a/libcxx/include/__flat_set/flat_set.h b/libcxx/include/__flat_set/flat_set.h
index cc788bd..5fa1f2d 100644
--- a/libcxx/include/__flat_set/flat_set.h
+++ b/libcxx/include/__flat_set/flat_set.h
@@ -12,7 +12,6 @@
#include <__algorithm/lexicographical_compare_three_way.h>
#include <__algorithm/lower_bound.h>
-#include <__algorithm/min.h>
#include <__algorithm/ranges_adjacent_find.h>
#include <__algorithm/ranges_equal.h>
#include <__algorithm/ranges_inplace_merge.h>
@@ -24,20 +23,16 @@
#include <__compare/synth_three_way.h>
#include <__concepts/swappable.h>
#include <__config>
-#include <__cstddef/ptrdiff_t.h>
#include <__flat_map/sorted_unique.h>
#include <__flat_set/ra_iterator.h>
#include <__flat_set/utils.h>
-#include <__functional/invoke.h>
#include <__functional/is_transparent.h>
#include <__functional/operations.h>
#include <__fwd/vector.h>
#include <__iterator/concepts.h>
-#include <__iterator/distance.h>
#include <__iterator/iterator_traits.h>
#include <__iterator/next.h>
#include <__iterator/prev.h>
-#include <__iterator/ranges_iterator_traits.h>
#include <__iterator/reverse_iterator.h>
#include <__memory/allocator_traits.h>
#include <__memory/uses_allocator.h>
@@ -47,10 +42,7 @@
#include <__ranges/container_compatible_range.h>
#include <__ranges/drop_view.h>
#include <__ranges/from_range.h>
-#include <__ranges/ref_view.h>
#include <__ranges/size.h>
-#include <__ranges/subrange.h>
-#include <__type_traits/conjunction.h>
#include <__type_traits/container_traits.h>
#include <__type_traits/invoke.h>
#include <__type_traits/is_allocator.h>
diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in
index dc19333..93d43f8 100644
--- a/libcxx/include/module.modulemap.in
+++ b/libcxx/include/module.modulemap.in
@@ -1225,6 +1225,7 @@ module std [system] {
header "deque"
export *
export std.iterator.reverse_iterator
+ export std.algorithm.simd_utils // This is a workaround for https://llvm.org/PR120108.
}
module exception {
@@ -1847,7 +1848,10 @@ module std [system] {
module ranges {
module access { header "__ranges/access.h" }
- module all { header "__ranges/all.h" }
+ module all {
+ header "__ranges/all.h"
+ export std.ranges.ref_view
+ }
module as_rvalue_view { header "__ranges/as_rvalue_view.h" }
module chunk_by_view {
header "__ranges/chunk_by_view.h"
@@ -2235,6 +2239,7 @@ module std [system] {
header "vector"
export std.iterator.reverse_iterator
export *
+ export std.algorithm.simd_utils // This is a workaround for https://llvm.org/PR120108.
}
// Experimental C++ Standard Library interfaces
generated by cgit v1.1 at 2025-09-30 07:01:27 +0000