diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -162,6 +162,7 @@ algorithms/lower_bound.bench.cpp algorithms/make_heap.bench.cpp algorithms/make_heap_then_sort_heap.bench.cpp + algorithms/min.bench.cpp algorithms/min_max_element.bench.cpp algorithms/pop_heap.bench.cpp algorithms/push_heap.bench.cpp diff --git a/libcxx/benchmarks/algorithms/min.bench.cpp b/libcxx/benchmarks/algorithms/min.bench.cpp new file mode 100644 --- /dev/null +++ b/libcxx/benchmarks/algorithms/min.bench.cpp @@ -0,0 +1,70 @@ +#include +#include + +#include + +void run_sizes(auto benchmark) { + benchmark->Arg(1) + ->Arg(2) + ->Arg(3) + ->Arg(4) + ->Arg(5) + ->Arg(6) + ->Arg(7) + ->Arg(8) + ->Arg(9) + ->Arg(10) + ->Arg(11) + ->Arg(12) + ->Arg(13) + ->Arg(14) + ->Arg(15) + ->Arg(16) + ->Arg(17) + ->Arg(18) + ->Arg(19) + ->Arg(20) + ->Arg(21) + ->Arg(22) + ->Arg(23) + ->Arg(24) + ->Arg(25) + ->Arg(26) + ->Arg(27) + ->Arg(28) + ->Arg(29) + ->Arg(30) + ->Arg(31) + ->Arg(32) + ->Arg(64) + ->Arg(512) + ->Arg(1024) + ->Arg(4000) + ->Arg(4096) + ->Arg(5500) + ->Arg(64000) + ->Arg(65536) + ->Arg(70000); +} + +template +static void BM_std_min(benchmark::State& state) { + std::vector vec(state.range(), 3); + + for (auto _ : state) { + benchmark::DoNotOptimize(vec); + benchmark::DoNotOptimize(std::ranges::min(vec)); + } +} +BENCHMARK(BM_std_min)->Apply(run_sizes); +BENCHMARK(BM_std_min)->Apply(run_sizes); +BENCHMARK(BM_std_min)->Apply(run_sizes); +BENCHMARK(BM_std_min)->Apply(run_sizes); +BENCHMARK(BM_std_min<__int128>)->Apply(run_sizes); +BENCHMARK(BM_std_min)->Apply(run_sizes); +BENCHMARK(BM_std_min)->Apply(run_sizes); +BENCHMARK(BM_std_min)->Apply(run_sizes); +BENCHMARK(BM_std_min)->Apply(run_sizes); +BENCHMARK(BM_std_min)->Apply(run_sizes); + +BENCHMARK_MAIN(); diff --git a/libcxx/include/__algorithm/ranges_max.h b/libcxx/include/__algorithm/ranges_max.h --- a/libcxx/include/__algorithm/ranges_max.h +++ b/libcxx/include/__algorithm/ranges_max.h @@ -20,6 +20,7 @@ #include <__iterator/projected.h> #include <__ranges/access.h> #include <__ranges/concepts.h> +#include <__type_traits/is_trivially_copyable.h> #include <__utility/move.h> #include @@ -67,7 +68,7 @@ _LIBCPP_ASSERT(__first != __last, "range must contain at least one element"); - if constexpr (forward_range<_Rp>) { + if constexpr (forward_range<_Rp> && !__is_cheap_to_copy>) { auto __comp_lhs_rhs_swapped = [&](auto&& __lhs, auto&& __rhs) { return std::invoke(__comp, __rhs, __lhs); }; return *ranges::__min_element_impl(std::move(__first), std::move(__last), __comp_lhs_rhs_swapped, __proj); } else { diff --git a/libcxx/include/__algorithm/ranges_min.h b/libcxx/include/__algorithm/ranges_min.h --- a/libcxx/include/__algorithm/ranges_min.h +++ b/libcxx/include/__algorithm/ranges_min.h @@ -20,6 +20,7 @@ #include <__iterator/projected.h> #include <__ranges/access.h> #include <__ranges/concepts.h> +#include <__type_traits/is_trivially_copyable.h> #include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) @@ -61,10 +62,8 @@ range_value_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const { auto __first = ranges::begin(__r); auto __last = ranges::end(__r); - _LIBCPP_ASSERT(__first != __last, "range must contain at least one element"); - - if constexpr (forward_range<_Rp>) { + if constexpr (forward_range<_Rp> && !__is_cheap_to_copy>) { return *ranges::__min_element_impl(__first, __last, __comp, __proj); } else { range_value_t<_Rp> __result = *__first; diff --git a/libcxx/include/__type_traits/is_trivially_copyable.h b/libcxx/include/__type_traits/is_trivially_copyable.h --- a/libcxx/include/__type_traits/is_trivially_copyable.h +++ b/libcxx/include/__type_traits/is_trivially_copyable.h @@ -11,6 +11,7 @@ #include <__config> #include <__type_traits/integral_constant.h> +#include #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -27,6 +28,11 @@ inline constexpr bool is_trivially_copyable_v = __is_trivially_copyable(_Tp); #endif +#if _LIBCPP_STD_VER >= 20 +template +inline constexpr bool __is_cheap_to_copy = is_trivially_copyable_v<_Tp> && sizeof(_Tp) <= sizeof(std::intmax_t); +#endif + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___TYPE_TRAITS_IS_TRIVIALLY_COPYABLE_H diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.max.pass.cpp @@ -176,19 +176,38 @@ template constexpr void test_range_types() { - int a[] = {7, 6, 9, 3, 5, 1, 2, 4}; + std::iter_value_t a[] = {7, 6, 9, 3, 5, 1, 2, 4}; auto range = std::ranges::subrange(It(a), Sent(It(a + 8))); - int ret = std::ranges::max(range); + auto ret = std::ranges::max(range); assert(ret == 9); } constexpr void test_range() { - { // check that all range types work - test_range_types, sentinel_wrapper>>(); - test_range_types>(); - test_range_types>(); - test_range_types>(); - test_range_types>(); + // check that all range types work + { + struct NonTrivialInt { + int val_; + constexpr NonTrivialInt(int val) : val_(val) {} + constexpr NonTrivialInt(const NonTrivialInt& other) : val_(other.val_) {} + constexpr NonTrivialInt& operator=(const NonTrivialInt& other) { + val_ = other.val_; + return *this; + } + + constexpr ~NonTrivialInt() {} + + auto operator<=>(const NonTrivialInt&) const = default; + }; + + auto call_with_sentinels = [] { + if constexpr (std::forward_iterator) + test_range_types(); + test_range_types>(); + test_range_types>(); + }; + + types::for_each(types::cpp20_input_iterator_list{}, call_with_sentinels); + types::for_each(types::cpp20_input_iterator_list{}, call_with_sentinels); } int a[] = {7, 6, 9, 3, 5, 1, 2, 4}; diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp @@ -171,19 +171,38 @@ template constexpr void test_range_types() { - int a[] = {7, 6, 9, 3, 5, 1, 2, 4}; + std::iter_value_t a[] = {7, 6, 9, 3, 5, 1, 2, 4}; auto range = std::ranges::subrange(It(a), Sent(It(a + 8))); - int ret = std::ranges::min(range); + auto ret = std::ranges::min(range); assert(ret == 1); } constexpr void test_range() { - { // check that all range types work - test_range_types, sentinel_wrapper>>(); - test_range_types>(); - test_range_types>(); - test_range_types>(); - test_range_types>(); + // check that all range types work + { + struct NonTrivialInt { + int val_; + constexpr NonTrivialInt(int val) : val_(val) {} + constexpr NonTrivialInt(const NonTrivialInt& other) : val_(other.val_) {} + constexpr NonTrivialInt& operator=(const NonTrivialInt& other) { + val_ = other.val_; + return *this; + } + + constexpr ~NonTrivialInt() {} + + auto operator<=>(const NonTrivialInt&) const = default; + }; + + auto call_with_sentinels = [] { + if constexpr (std::forward_iterator) + test_range_types(); + test_range_types>(); + test_range_types>(); + }; + + types::for_each(types::cpp20_input_iterator_list{}, call_with_sentinels); + types::for_each(types::cpp20_input_iterator_list{}, call_with_sentinels); } int a[] = {7, 6, 9, 3, 5, 1, 2, 4};