Index: benchmarks/algorithms.merge.bench.cpp =================================================================== --- /dev/null +++ benchmarks/algorithms.merge.bench.cpp @@ -0,0 +1,147 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#include +#include + +#include "benchmark/benchmark.h" + +#include "CartesianBenchmarks.hpp" +#include "GenerateInput.hpp" +#include "test_macros.h" + +namespace { + +constexpr size_t kSplitPointCount = 5; + +template +std::array pickSplitPoints(I f, I l) { + std::ptrdiff_t N = std::distance(f, l); + + return { + f + N / 4, + f + N / 3, + f + N / 2, + f + 2 * N / 3, + f + 3 * N / 4 + }; +} + +template +struct TestIntBase { + static std::vector generateInput(size_t size) { + std::vector Res(size); + std::generate(Res.begin(), Res.end(), + [] { return getRandomInteger(); }); + return Res; + } +}; + +struct TestInt32 : TestIntBase { + static constexpr const char* Name = "TestInt32"; +}; + +struct TestInt64 : TestIntBase { + static constexpr const char* Name = "TestInt64"; +}; + +struct TestUint32 : TestIntBase { + static constexpr const char* Name = "TestUint32"; +}; + +struct TestMediumString { + static constexpr const char* Name = "TestMediumString"; + static constexpr size_t StringSize = 32; + + static std::vector generateInput(size_t size) { + std::vector Res(size); + std::generate(Res.begin(), Res.end(), + [] { return getRandomString(StringSize); }); + return Res; + } +}; + +using AllTestTypes = + std::tuple; + +struct MergeAlg { + template + O operator()(I1 first1, I1 last1, I2 first2, I2 last2, O out) { + return std::merge(first1, last1, first2, last2, out); + } + + static constexpr const char* Name = "MergeAlg"; +}; + +using AllAlgs = std::tuple; + +} // namespace + +template +struct MergeBench { + size_t Quantity; + + std::string name() const { + return std::string("MergeBench_") + Alg::Name + "_" + TestType::Name + '/' + + std::to_string(Quantity); + } + + template + struct BenchmarkPrepared { + std::array LhsArray; + std::array RhsArray; + VecT output; + }; + + TEST_NOINLINE auto prepareBenchmark() const { + auto Data = TestType::generateInput(Quantity); + using VecT = decltype(Data); + + const auto SplitPoints = pickSplitPoints(Data.begin(), Data.end()); + + BenchmarkPrepared Res; + + VecT* LhsIt = Res.LhsArray.begin(); + VecT* RhsIt = Res.RhsArray.begin(); + for (auto Split : SplitPoints) { + *LhsIt = VecT{Data.begin(), Split}; + *RhsIt = VecT{Split, Data.end()}; + std::sort(LhsIt->begin(), LhsIt->end()); + std::sort(RhsIt->begin(), RhsIt->end()); + ++LhsIt; + ++RhsIt; + } + + Res.output = VecT(Data.size()); + + return Res; + } + + + void run(benchmark::State& state) const { + auto[LhsArray, RhsArray, Output] = prepareBenchmark(); + + for (auto _ : state) { + for (size_t i = 0; i < LhsArray.size(); ++i) { + Alg{}(LhsArray[i].begin(), LhsArray[i].end(), RhsArray[i].begin(), + RhsArray[i].end(), Output.begin()); + benchmark::DoNotOptimize(Output); + } + } + } +}; + +int main(int argc, char** argv) { + benchmark::Initialize(&argc, argv); + if (benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + + const std::vector Quantities = {1 << 9, 1 << 11, 1 << 21}; + makeCartesianProductBenchmark(Quantities); + benchmark::RunSpecifiedBenchmarks(); +} Index: include/algorithm =================================================================== --- include/algorithm +++ include/algorithm @@ -1631,7 +1631,7 @@ // copy template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR _Iter __unwrap_iter(_Iter __i) { @@ -1639,7 +1639,7 @@ } template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR typename enable_if < is_trivially_copy_assignable<_Tp>::value, @@ -1653,7 +1653,7 @@ #if _LIBCPP_DEBUG_LEVEL < 2 template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR typename enable_if < is_trivially_copy_assignable<_Tp>::value, @@ -1665,7 +1665,7 @@ } template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR typename enable_if < is_trivially_copy_assignable<_Tp>::value, @@ -1679,7 +1679,7 @@ #else template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_IF_NODEBUG +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR typename enable_if < is_trivially_copy_assignable<_Tp>::value, @@ -1693,7 +1693,7 @@ #endif // _LIBCPP_DEBUG_LEVEL < 2 template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator __copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { @@ -1703,7 +1703,7 @@ } template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 typename enable_if < is_same::type, _Up>::value && @@ -1714,12 +1714,12 @@ { const size_t __n = static_cast(__last - __first); if (__n > 0) - _VSTD::memmove(__result, __first, __n * sizeof(_Up)); + __builtin_memmove(__result, __first, __n * sizeof(_Up)); return __result + __n; } template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator copy(_InputIterator __first, _InputIterator __last, _OutputIterator __result) { @@ -4342,9 +4342,11 @@ // merge template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator -__merge(_InputIterator1 __first1, _InputIterator1 __last1, - _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) +__merge_constexpr(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _OutputIterator __result, _Compare __comp) { for (; __first1 != __last1; ++__result) { @@ -4364,18 +4366,58 @@ return _VSTD::copy(__first2, __last2, __result); } -template +template inline _LIBCPP_INLINE_VISIBILITY _OutputIterator +__merge_runtime(_InputIterator1 __first1, _InputIterator1 __last1, + _InputIterator2 __first2, _InputIterator2 __last2, + _OutputIterator __result, _Compare __comp) +{ + if (__first1 == __last1) goto __copySecond; + if (__first2 == __last2) goto __copyFirst; + + while (true) { + if (__comp(*__first2, *__first1)) goto __takeSecond; + *__result = *__first1; + ++__first1, (void)++__result; + if (__first1 == __last1) goto __copySecond; + goto __unrolledCheck; +__takeSecond: + *__result = *__first2; + ++__first2, (void)++__result; + if (__first2 == __last2) goto __copyFirst; +__unrolledCheck: + if (__comp(*__first2, *__first1)) goto __takeSecond; + *__result = *__first1; + ++__first1, (void)++__result; + if (__first1 == __last1) goto __copySecond; + } + +__copySecond: + return _VSTD::copy(__first2, __last2, __result); +__copyFirst: + return _VSTD::copy(__first1, __last1, __result); +} + +template +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 +_OutputIterator merge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result, _Compare __comp) { typedef typename __comp_ref_type<_Compare>::type _Comp_ref; - return _VSTD::__merge<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); + +#if defined(__cpp_lib_is_constant_evaluated) + if (_VSTD::is_constant_evaluated()) { + return _VSTD::__merge_constexpr<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); + } +#endif // __cpp_lib_is_constant_evaluated + + return _VSTD::__merge_runtime<_Comp_ref>(__first1, __last1, __first2, __last2, __result, __comp); } template -inline _LIBCPP_INLINE_VISIBILITY +inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 _OutputIterator merge(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2, _OutputIterator __result) Index: include/iterator =================================================================== --- include/iterator +++ include/iterator @@ -1304,7 +1304,7 @@ __wrap_iter<_Iter> operator+(typename __wrap_iter<_Iter>::difference_type, __wrap_iter<_Iter>) _NOEXCEPT; -template _Op _LIBCPP_INLINE_VISIBILITY copy(_Ip, _Ip, _Op); +template _Op _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17 copy(_Ip, _Ip, _Op); template _B2 _LIBCPP_INLINE_VISIBILITY copy_backward(_B1, _B1, _B2); template _Op _LIBCPP_INLINE_VISIBILITY move(_Ip, _Ip, _Op); template _B2 _LIBCPP_INLINE_VISIBILITY move_backward(_B1, _B1, _B2); @@ -1515,7 +1515,7 @@ __wrap_iter<_Iter1> operator+(typename __wrap_iter<_Iter1>::difference_type, __wrap_iter<_Iter1>) _NOEXCEPT; - template friend _Op copy(_Ip, _Ip, _Op); + template friend _LIBCPP_CONSTEXPR_AFTER_CXX17 _Op copy(_Ip, _Ip, _Op); template friend _B2 copy_backward(_B1, _B1, _B2); template friend _Op move(_Ip, _Ip, _Op); template friend _B2 move_backward(_B1, _B1, _B2); Index: test/libcxx/algorithms/merge.pass.cpp =================================================================== --- /dev/null +++ test/libcxx/algorithms/merge.pass.cpp @@ -0,0 +1,149 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// __merge_constexpr, __merge_runtime - implementations of std::merge + +#include + +#include +#include +#include +#include + +#include "MoveOnly.h" +#include "test_iterators.h" + +namespace { + +using TestType = std::pair; + +struct LessFirst { + template + bool operator()(const std::pair& x, const std::pair& y) const { + return x.first < y.first; + } +}; + +std::vector make_vector_of_test_type(const std::vector& data, + int marker) { + std::vector res(data.size()); + + std::transform(data.begin(), data.end(), res.begin(), [&](int x) { + return TestType{MoveOnly(x), marker}; + }); + + return res; +} + +template +void run_one_test(const std::vector& x_data, + const std::vector& y_data, + AdaptXIt adaptXIt, + AdaptYIt adaptYIt, + Merger merger) { + const std::vector actual = [&] { + std::vector x_vec = make_vector_of_test_type(x_data, 0); + std::vector y_vec = make_vector_of_test_type(y_data, 1); + + x_vec.insert(x_vec.end(), std::make_move_iterator(y_vec.begin()), + std::make_move_iterator(y_vec.end())); + std::sort(x_vec.begin(), x_vec.end()); + return x_vec; + }(); + + const std::vector expected = [&] { + std::vector x_vec = make_vector_of_test_type(x_data, 0); + std::vector y_vec = make_vector_of_test_type(y_data, 1); + + std::vector res; + + auto moveXIt = [&](auto it) { + return std::make_move_iterator(adaptXIt(it)); + }; + + auto moveYIt = [&](auto it) { + return std::make_move_iterator(adaptYIt(it)); + }; + + merger(moveXIt(x_vec.begin()), moveXIt(x_vec.end()), moveYIt(y_vec.begin()), + moveYIt(y_vec.end()), std::back_inserter(res), LessFirst{}); + + return res; + }(); + + assert(expected == actual); +} + +template +void run_for_different_iterator_categories(const std::vector& x_data, + const std::vector& y_data, + Merger merger) { + auto make_input = [](auto it) { return input_iterator(it); }; + auto make_random = [](auto it) { return it; }; + + run_one_test(x_data, y_data, make_input, make_input, merger); + run_one_test(x_data, y_data, make_random, make_input, merger); + run_one_test(x_data, y_data, make_input, make_random, merger); +} + +constexpr size_t kGeneratedTestDataSize = 200; + +const std::vector& generated_test_data() { + static std::vector res = [] { + std::mt19937 g; + std::uniform_int_distribution<> dis(1, int(kGeneratedTestDataSize) * 10); + + std::vector res(kGeneratedTestDataSize); + std::generate(res.begin(), res.end(), [&]() mutable { return dis(g); }); + + return res; + }(); + return res; +} + +template +void run_generated_test(Merger merger) { + const auto& test_data = generated_test_data(); + + for (size_t total_size = 0; total_size <= kGeneratedTestDataSize; ++total_size) { + for (size_t x_size = 0; x_size <= total_size; ++x_size) { + std::vector x_data(test_data.data(), test_data.data() + x_size); + std::vector y_data(test_data.data() + x_size, test_data.data() + total_size); + + std::sort(x_data.begin(), x_data.end()); + std::sort(y_data.begin(), y_data.end()); + + run_for_different_iterator_categories(x_data, y_data, merger); + } + } +} + +template +void run_tests(Merger merger) { + run_for_different_iterator_categories({1, 1, 1, 1, 1, 1, 1, 1}, {1}, merger); + + run_generated_test(merger); +} + +} // namespace + +int main() { + run_tests([](auto f1, auto l1, auto f2, auto l2, auto o, auto cmp) { + return std::__merge_constexpr(f1, l1, f2, l2, o, cmp); + }); + + run_tests([](auto f1, auto l1, auto f2, auto l2, auto o, auto cmp) { + return std::__merge_runtime(f1, l1, f2, l2, o, cmp); + }); + + run_tests([](auto f1, auto l1, auto f2, auto l2, auto o, auto cmp) { + return std::merge(f1, l1, f2, l2, o, cmp); + }); +} Index: test/std/algorithms/alg.modifying.operations/alg.copy/copy.pass.cpp =================================================================== --- test/std/algorithms/alg.modifying.operations/alg.copy/copy.pass.cpp +++ test/std/algorithms/alg.modifying.operations/alg.copy/copy.pass.cpp @@ -18,17 +18,17 @@ #include "test_macros.h" #include "test_iterators.h" -// #if TEST_STD_VER > 17 -// TEST_CONSTEXPR bool test_constexpr() { -// int ia[] = {1, 2, 3, 4, 5}; -// int ic[] = {6, 6, 6, 6, 6, 6, 6}; -// -// auto p = std::copy(std::begin(ia), std::end(ia), std::begin(ic)); -// return std::equal(std::begin(ia), std::end(ia), std::begin(ic), p) -// && std::all_of(p, std::end(ic), [](int a){return a == 6;}) -// ; -// } -// #endif +#if TEST_STD_VER > 17 +TEST_CONSTEXPR bool test_constexpr() { + int ia[] = {1, 2, 3, 4, 5}; + int ic[] = {6, 6, 6, 6, 6, 6, 6}; + + auto p = std::copy(std::begin(ia), std::end(ia), std::begin(ic)); + return std::equal(std::begin(ia), std::end(ia), std::begin(ic), p) + && std::all_of(p, std::end(ic), [](int a){return a == 6;}) + ; + } +#endif template void @@ -83,9 +83,9 @@ test >(); test(); -// #if TEST_STD_VER > 17 -// static_assert(test_constexpr()); -// #endif +#if TEST_STD_VER > 17 && defined(__cpp_lib_is_constant_evaluated) + static_assert(test_constexpr()); +#endif return 0; } Index: test/std/algorithms/alg.sorting/alg.merge/merge.pass.cpp =================================================================== --- test/std/algorithms/alg.sorting/alg.merge/merge.pass.cpp +++ test/std/algorithms/alg.sorting/alg.merge/merge.pass.cpp @@ -25,20 +25,19 @@ #include "test_iterators.h" -// #if TEST_STD_VER > 17 -// TEST_CONSTEXPR bool test_constexpr() { -// int ia[] = {0, 1, 2, 3, 4}; -// int ib[] = {2, 4, 6, 8}; -// int ic[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; -// const int expected[] = {0, 1, 2, 2, 3, 4, 4, 6, 8}; -// -// auto it = std::merge(std::begin(ia), std::end(ia), std::begin(ib), std::end(ib), std::begin(ic)); -// return std::distance(std::begin(ic), it) == (std::size(ia) + std::size(ib)) -// && *it == 0 -// && std::equal(std::begin(ic), it, std::begin(expected), std::end(expected)) -// ; -// } -// #endif +#if TEST_STD_VER > 17 +TEST_CONSTEXPR bool test_constexpr() { + int ia[] = {0, 1, 2, 3, 4}; + int ib[] = {2, 4, 6, 8}; + int ic[] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + const int expected[] = {0, 1, 2, 2, 3, 4, 4, 6, 8}; + auto it = std::merge(std::begin(ia), std::end(ia), std::begin(ib), std::end(ib), std::begin(ic)); + return std::distance(std::begin(ic), it) == (std::size(ia) + std::size(ib)) + && *it == 0 + && std::equal(std::begin(ic), it, std::begin(expected), std::end(expected)) + ; + } +#endif std::mt19937 randomness; @@ -241,9 +240,8 @@ test >(); test(); -#if TEST_STD_VER > 17 -// Not yet - waiting on std::copy -// static_assert(test_constexpr()); +#if TEST_STD_VER > 17 && defined(__cpp_lib_is_constant_evaluated) + static_assert(test_constexpr()); #endif return 0;