diff options
| author | Peng Liu <winner245@hotmail.com> | 2025-02-19 11:36:45 -0500 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2025-02-19 11:36:45 -0500 |
| commit | ab3d793982acb946afc2028ca41304913879c6c9 (patch) | |
| tree | 0e2400808108a5cc3ac2df709d25fb9627f87c8d /libcxx/include/__algorithm | |
| parent | 70e693c77f0044643f3a301a0b7bc334a6e558c9 (diff) | |
| download | llvm-ab3d793982acb946afc2028ca41304913879c6c9.zip llvm-ab3d793982acb946afc2028ca41304913879c6c9.tar.gz llvm-ab3d793982acb946afc2028ca41304913879c6c9.tar.bz2 | |
[libc++] Optimize ranges::move{,_backward} for vector<bool>::iterator (#121109)
As a follow-up to #121013 (which optimized `ranges::copy`) and #121026
(which optimized `ranges::copy_backward`), this PR enhances the
performance of `std::ranges::{move, move_backward}` for
`vector<bool>::iterator`, addressing a subtask outlined in issue #64038.
The optimizations bring performance improvements analogous to those
achieved for the `{copy, copy_backward}` algorithms: up to 2000x for
aligned moves and 60x for unaligned moves. Moreover, comprehensive
tests covering up to 4 storage words (256 bytes) with odd and even bit
sizes are provided, which validate the proposed optimizations in this
patch.
Diffstat (limited to 'libcxx/include/__algorithm')
| -rw-r--r-- | libcxx/include/__algorithm/move.h | 10 | ||||
| -rw-r--r-- | libcxx/include/__algorithm/move_backward.h | 10 |
2 files changed, 20 insertions, 0 deletions
diff --git a/libcxx/include/__algorithm/move.h b/libcxx/include/__algorithm/move.h index 6f3b0eb..a3320e9 100644 --- a/libcxx/include/__algorithm/move.h +++ b/libcxx/include/__algorithm/move.h @@ -9,11 +9,13 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_H #define _LIBCPP___ALGORITHM_MOVE_H +#include <__algorithm/copy.h> #include <__algorithm/copy_move_common.h> #include <__algorithm/for_each_segment.h> #include <__algorithm/iterator_operations.h> #include <__algorithm/min.h> #include <__config> +#include <__fwd/bit_reference.h> #include <__iterator/iterator_traits.h> #include <__iterator/segmented_iterator.h> #include <__type_traits/common_type.h> @@ -98,6 +100,14 @@ struct __move_impl { } } + template <class _Cp, bool _IsConst> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> > + operator()(__bit_iterator<_Cp, _IsConst> __first, + __bit_iterator<_Cp, _IsConst> __last, + __bit_iterator<_Cp, false> __result) { + return std::__copy(__first, __last, __result); + } + // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer. template <class _In, class _Out, __enable_if_t<__can_lower_move_assignment_to_memmove<_In, _Out>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*> diff --git a/libcxx/include/__algorithm/move_backward.h b/libcxx/include/__algorithm/move_backward.h index 24a8d9b..14482fe 100644 --- a/libcxx/include/__algorithm/move_backward.h +++ b/libcxx/include/__algorithm/move_backward.h @@ -9,10 +9,12 @@ #ifndef _LIBCPP___ALGORITHM_MOVE_BACKWARD_H #define _LIBCPP___ALGORITHM_MOVE_BACKWARD_H +#include <__algorithm/copy_backward.h> #include <__algorithm/copy_move_common.h> #include <__algorithm/iterator_operations.h> #include <__algorithm/min.h> #include <__config> +#include <__fwd/bit_reference.h> #include <__iterator/iterator_traits.h> #include <__iterator/segmented_iterator.h> #include <__type_traits/common_type.h> @@ -107,6 +109,14 @@ struct __move_backward_impl { } } + template <class _Cp, bool _IsConst> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 pair<__bit_iterator<_Cp, _IsConst>, __bit_iterator<_Cp, false> > + operator()(__bit_iterator<_Cp, _IsConst> __first, + __bit_iterator<_Cp, _IsConst> __last, + __bit_iterator<_Cp, false> __result) { + return std::__copy_backward<_ClassicAlgPolicy>(__first, __last, __result); + } + // At this point, the iterators have been unwrapped so any `contiguous_iterator` has been unwrapped to a pointer. template <class _In, class _Out, __enable_if_t<__can_lower_move_assignment_to_memmove<_In, _Out>::value, int> = 0> _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 pair<_In*, _Out*> |