diff --git a/libcxx/benchmarks/algorithms/find.bench.cpp b/libcxx/benchmarks/algorithms/find.bench.cpp --- a/libcxx/benchmarks/algorithms/find.bench.cpp +++ b/libcxx/benchmarks/algorithms/find.bench.cpp @@ -46,4 +46,32 @@ BENCHMARK(bm_ranges_find)->DenseRange(1, 8)->Range(16, 1 << 20); BENCHMARK(bm_ranges_find)->DenseRange(1, 8)->Range(16, 1 << 20); +static void bm_vector_bool_find(benchmark::State& state) { + std::vector vec1(state.range(), false); + std::mt19937_64 rng(std::random_device{}()); + + for (auto _ : state) { + auto idx = rng() % vec1.size(); + vec1[idx] = true; + benchmark::DoNotOptimize(vec1); + benchmark::DoNotOptimize(std::find(vec1.begin(), vec1.end(), true)); + vec1[idx] = false; + } +} +BENCHMARK(bm_vector_bool_find)->DenseRange(1, 8)->Range(16, 1 << 20); + +static void bm_vector_bool_ranges_find(benchmark::State& state) { + std::vector vec1(state.range(), false); + std::mt19937_64 rng(std::random_device{}()); + + for (auto _ : state) { + auto idx = rng() % vec1.size(); + vec1[idx] = true; + benchmark::DoNotOptimize(vec1); + benchmark::DoNotOptimize(std::ranges::find(vec1, true)); + vec1[idx] = false; + } +} +BENCHMARK(bm_vector_bool_ranges_find)->DenseRange(1, 8)->Range(16, 1 << 20); + BENCHMARK_MAIN(); diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -248,6 +248,7 @@ __bit/countr.h __bit/endian.h __bit/has_single_bit.h + __bit/invert_if.h __bit/popcount.h __bit/rotate.h __bit_reference @@ -414,6 +415,7 @@ __functional/unary_negate.h __functional/weak_result_type.h __fwd/array.h + __fwd/bit_reference.h __fwd/fstream.h __fwd/get.h __fwd/hash.h diff --git a/libcxx/include/__algorithm/find.h b/libcxx/include/__algorithm/find.h --- a/libcxx/include/__algorithm/find.h +++ b/libcxx/include/__algorithm/find.h @@ -10,10 +10,14 @@ #ifndef _LIBCPP___ALGORITHM_FIND_H #define _LIBCPP___ALGORITHM_FIND_H +#include <__algorithm/min.h> #include <__algorithm/unwrap_iter.h> +#include <__bit/countr.h> +#include <__bit/invert_if.h> #include <__config> #include <__functional/identity.h> #include <__functional/invoke.h> +#include <__fwd/bit_reference.h> #include <__string/constexpr_c_functions.h> #include <__type_traits/is_same.h> @@ -25,8 +29,12 @@ # pragma GCC system_header #endif +_LIBCPP_PUSH_MACROS +#include <__undef_macros> + _LIBCPP_BEGIN_NAMESPACE_STD +// generic implementation template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Iter __find_impl(_Iter __first, _Sent __last, const _Tp& __value, _Proj& __proj) { @@ -36,6 +44,7 @@ return __first; } +// trivially equality comparable implementations template +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, _IsConst> +__find_bool(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) { + using _It = __bit_iterator<_Cp, _IsConst>; + using __storage_type = typename _It::__storage_type; + + const int __bits_per_word = _It::__bits_per_word; + // do first partial word + if (__first.__ctz_ != 0) { + __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); + __storage_type __dn = std::min(__clz_f, __n); + __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); + __storage_type __b = std::__invert_if(*__first.__seg_) & __m; + if (__b) + return _It(__first.__seg_, static_cast(std::__libcpp_ctz(__b))); + if (__n == __dn) + return __first + __n; + __n -= __dn; + ++__first.__seg_; + } + // do middle whole words + for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) { + __storage_type __b = std::__invert_if(*__first.__seg_); + if (__b) + return _It(__first.__seg_, static_cast(std::__libcpp_ctz(__b))); + } + // do last partial word + if (__n > 0) { + __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); + __storage_type __b = std::__invert_if(*__first.__seg_) & __m; + if (__b) + return _It(__first.__seg_, static_cast(std::__libcpp_ctz(__b))); + } + return _It(__first.__seg_, static_cast(__n)); +} + +template ::value, int> = 0> +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, _IsConst> +__find_impl(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value, _Proj&) { + if (static_cast(__value)) + return std::__find_bool(__first, static_cast(__last - __first)); + return std::__find_bool(__first, static_cast(__last - __first)); +} + template _LIBCPP_NODISCARD_EXT inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _InputIterator find(_InputIterator __first, _InputIterator __last, const _Tp& __value) { @@ -74,4 +128,6 @@ _LIBCPP_END_NAMESPACE_STD +_LIBCPP_POP_MACROS + #endif // _LIBCPP___ALGORITHM_FIND_H diff --git a/libcxx/include/__bit/invert_if.h b/libcxx/include/__bit/invert_if.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__bit/invert_if.h @@ -0,0 +1,32 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___BIT_INVERT_IF_H +#define _LIBCPP___BIT_INVERT_IF_H + +#include <__concepts/arithmetic.h> +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +_LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp __invert_if(_Tp __v) { + if (_Invert) { + return ~__v; + } else { + return __v; + } +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___BIT_INVERT_IF_H diff --git a/libcxx/include/__bit_reference b/libcxx/include/__bit_reference --- a/libcxx/include/__bit_reference +++ b/libcxx/include/__bit_reference @@ -14,8 +14,10 @@ #include <__algorithm/fill_n.h> #include <__algorithm/min.h> #include <__bit/countr.h> +#include <__bit/invert_if.h> #include <__bit/popcount.h> #include <__config> +#include <__fwd/bit_reference.h> #include <__iterator/iterator_traits.h> #include <__memory/construct_at.h> #include <__memory/pointer_traits.h> @@ -32,8 +34,6 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template -class __bit_iterator; template class __bit_const_reference; @@ -171,61 +171,6 @@ __bit_const_reference& operator=(const __bit_const_reference&) = delete; }; -template -_LIBCPP_CONSTEXPR_SINCE_CXX14 _Tp __invert_if(_Tp __v) { - if (_Invert) { - return ~__v; - } else { - return __v; - } -} - -// find - -template -_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __bit_iterator<_Cp, _IsConst> -__find_bool(__bit_iterator<_Cp, _IsConst> __first, typename _Cp::size_type __n) { - using _It = __bit_iterator<_Cp, _IsConst>; - using __storage_type = typename _It::__storage_type; - - const int __bits_per_word = _It::__bits_per_word; - // do first partial word - if (__first.__ctz_ != 0) { - __storage_type __clz_f = static_cast<__storage_type>(__bits_per_word - __first.__ctz_); - __storage_type __dn = std::min(__clz_f, __n); - __storage_type __m = (~__storage_type(0) << __first.__ctz_) & (~__storage_type(0) >> (__clz_f - __dn)); - __storage_type __b = std::__invert_if(*__first.__seg_) & __m; - if (__b) - return _It(__first.__seg_, static_cast(std::__libcpp_ctz(__b))); - if (__n == __dn) - return __first + __n; - __n -= __dn; - ++__first.__seg_; - } - // do middle whole words - for (; __n >= __bits_per_word; ++__first.__seg_, __n -= __bits_per_word) { - __storage_type __b = std::__invert_if(*__first.__seg_); - if (__b) - return _It(__first.__seg_, static_cast(std::__libcpp_ctz(__b))); - } - // do last partial word - if (__n > 0) { - __storage_type __m = ~__storage_type(0) >> (__bits_per_word - __n); - __storage_type __b = std::__invert_if(*__first.__seg_) & __m; - if (__b) - return _It(__first.__seg_, static_cast(std::__libcpp_ctz(__b))); - } - return _It(__first.__seg_, static_cast(__n)); -} - -template -inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __bit_iterator<_Cp, _IsConst> -find(__bit_iterator<_Cp, _IsConst> __first, __bit_iterator<_Cp, _IsConst> __last, const _Tp& __value) { - if (static_cast(__value)) - return std::__find_bool(__first, static_cast(__last - __first)); - return std::__find_bool(__first, static_cast(__last - __first)); -} - // count template diff --git a/libcxx/include/__fwd/bit_reference.h b/libcxx/include/__fwd/bit_reference.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__fwd/bit_reference.h @@ -0,0 +1,21 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___FWD_BIT_REFERENCE_H +#define _LIBCPP___FWD_BIT_REFERENCE_H + +#include <__config> + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +class __bit_iterator; + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___FWD_BIT_REFERENCE_H