From b1dc43aa3a05c2f14725e2e6428544208ccbe161 Mon Sep 17 00:00:00 2001 From: Nikolas Klauser Date: Wed, 31 May 2023 18:14:32 -0700 Subject: [PATCH] [libc++] Optimize for_each for segmented iterators ``` --------------------------------------------------- Benchmark old new --------------------------------------------------- bm_for_each/1 3.00 ns 2.98 ns bm_for_each/2 4.53 ns 4.57 ns bm_for_each/3 5.82 ns 5.82 ns bm_for_each/4 6.94 ns 6.91 ns bm_for_each/5 7.55 ns 7.75 ns bm_for_each/6 7.06 ns 7.45 ns bm_for_each/7 6.69 ns 7.14 ns bm_for_each/8 6.86 ns 4.06 ns bm_for_each/16 11.5 ns 5.73 ns bm_for_each/64 43.7 ns 4.06 ns bm_for_each/512 356 ns 7.98 ns bm_for_each/4096 2787 ns 53.6 ns bm_for_each/32768 20836 ns 438 ns bm_for_each/262144 195362 ns 4945 ns bm_for_each/1048576 685482 ns 19822 ns ``` Reviewed By: ldionne, Mordante, #libc Spies: arichardson, libcxx-commits Differential Revision: https://reviews.llvm.org/D151274 --- libcxx/benchmarks/CMakeLists.txt | 1 + libcxx/benchmarks/algorithms/for_each.bench.cpp | 23 ++++++++ libcxx/include/__algorithm/for_each.h | 21 ++++++- .../alg.nonmodifying/alg.foreach/for_each.pass.cpp | 67 ++++++++++++++++++++++ .../alg.nonmodifying/alg.foreach/test.pass.cpp | 56 ------------------ libcxx/utils/data/ignore_format.txt | 1 - 6 files changed, 109 insertions(+), 60 deletions(-) create mode 100644 libcxx/benchmarks/algorithms/for_each.bench.cpp create mode 100644 libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each.pass.cpp delete mode 100644 libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/test.pass.cpp diff --git a/libcxx/benchmarks/CMakeLists.txt b/libcxx/benchmarks/CMakeLists.txt index daa6fa2..99964cf 100644 --- a/libcxx/benchmarks/CMakeLists.txt +++ b/libcxx/benchmarks/CMakeLists.txt @@ -160,6 +160,7 @@ set(BENCHMARK_TESTS algorithms.partition_point.bench.cpp algorithms/equal.bench.cpp algorithms/find.bench.cpp + algorithms/for_each.bench.cpp algorithms/lower_bound.bench.cpp algorithms/make_heap.bench.cpp algorithms/make_heap_then_sort_heap.bench.cpp diff --git a/libcxx/benchmarks/algorithms/for_each.bench.cpp b/libcxx/benchmarks/algorithms/for_each.bench.cpp new file mode 100644 index 0000000..7019dc1 --- /dev/null +++ b/libcxx/benchmarks/algorithms/for_each.bench.cpp @@ -0,0 +1,23 @@ +//===----------------------------------------------------------------------===// +// +// 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 + +static void bm_deque_for_each(benchmark::State& state) { + std::deque vec1(state.range(), '1'); + for (auto _ : state) { + benchmark::DoNotOptimize(vec1); + benchmark::DoNotOptimize( + std::for_each(vec1.begin(), vec1.end(), [](char& v) { v = std::clamp(v, (char)10, (char)100); })); + } +} +BENCHMARK(bm_deque_for_each)->DenseRange(1, 8)->Range(16, 1 << 20); + +BENCHMARK_MAIN(); diff --git a/libcxx/include/__algorithm/for_each.h b/libcxx/include/__algorithm/for_each.h index 6564f31..5e273cf 100644 --- a/libcxx/include/__algorithm/for_each.h +++ b/libcxx/include/__algorithm/for_each.h @@ -10,7 +10,11 @@ #ifndef _LIBCPP___ALGORITHM_FOR_EACH_H #define _LIBCPP___ALGORITHM_FOR_EACH_H +#include <__algorithm/for_each_segment.h> #include <__config> +#include <__iterator/segmented_iterator.h> +#include <__type_traits/enable_if.h> +#include <__utility/move.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -19,14 +23,25 @@ _LIBCPP_BEGIN_NAMESPACE_STD template -inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 _Function for_each(_InputIterator __first, - _InputIterator __last, - _Function __f) { +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Function +for_each(_InputIterator __first, _InputIterator __last, _Function __f) { for (; __first != __last; ++__first) __f(*__first); return __f; } +#if _LIBCPP_STD_VER >= 20 +template + requires __is_segmented_iterator<_SegmentedIterator>::value +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _Function +for_each(_SegmentedIterator __first, _SegmentedIterator __last, _Function __func) { + std::__for_each_segment(__first, __last, [&](auto __lfirst, auto __llast) { + __func = std::for_each(__lfirst, __llast, std::move(__func)); + }); + return __func; +} +#endif // _LIBCPP_STD_VER >= 20 + _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___ALGORITHM_FOR_EACH_H diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each.pass.cpp new file mode 100644 index 0000000..6b39bcd --- /dev/null +++ b/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/for_each.pass.cpp @@ -0,0 +1,67 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +// + +// template Function> +// requires CopyConstructible +// constexpr Function // constexpr after C++17 +// for_each(Iter first, Iter last, Function f); + +#include +#include +#include + +#include "test_macros.h" +#include "test_iterators.h" + +struct for_each_test { + TEST_CONSTEXPR for_each_test(int c) : count(c) {} + int count; + TEST_CONSTEXPR_CXX14 void operator()(int& i) { + ++i; + ++count; + } +}; + +TEST_CONSTEXPR_CXX20 bool test() { + int ia[] = {0, 1, 2, 3, 4, 5}; + const unsigned s = sizeof(ia) / sizeof(ia[0]); + for_each_test f = std::for_each(cpp17_input_iterator(ia), cpp17_input_iterator(ia + s), for_each_test(0)); + assert(f.count == s); + for (unsigned i = 0; i < s; ++i) + assert(ia[i] == static_cast(i + 1)); + + return true; +} + +struct deque_test { + std::deque* d_; + int* i_; + + deque_test(std::deque& d, int& i) : d_(&d), i_(&i) {} + + void operator()(int& v) { + assert(&(*d_)[(*i_)++] == &v); + } +}; + +int main(int, char**) { + test(); +#if TEST_STD_VER >= 20 + static_assert(test()); +#endif + + // check that segmented iterators work properly + std::deque d(50); + int index = 0; + + std::for_each(d.begin(), d.end(), deque_test(d, index)); + + return 0; +} diff --git a/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/test.pass.cpp b/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/test.pass.cpp deleted file mode 100644 index d6b4655..0000000 --- a/libcxx/test/std/algorithms/alg.nonmodifying/alg.foreach/test.pass.cpp +++ /dev/null @@ -1,56 +0,0 @@ -//===----------------------------------------------------------------------===// -// -// 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 -// -//===----------------------------------------------------------------------===// - -// - -// template Function> -// requires CopyConstructible -// constexpr Function // constexpr after C++17 -// for_each(Iter first, Iter last, Function f); - -#include -#include - -#include "test_macros.h" -#include "test_iterators.h" - -#if TEST_STD_VER > 17 -TEST_CONSTEXPR bool test_constexpr() { - int ia[] = {1, 3, 6, 7}; - int expected[] = {3, 5, 8, 9}; - - std::for_each(std::begin(ia), std::end(ia), [](int &a) { a += 2; }); - return std::equal(std::begin(ia), std::end(ia), std::begin(expected)) - ; - } -#endif - -struct for_each_test -{ - for_each_test(int c) : count(c) {} - int count; - void operator()(int& i) {++i; ++count;} -}; - -int main(int, char**) -{ - int ia[] = {0, 1, 2, 3, 4, 5}; - const unsigned s = sizeof(ia)/sizeof(ia[0]); - for_each_test f = std::for_each(cpp17_input_iterator(ia), - cpp17_input_iterator(ia+s), - for_each_test(0)); - assert(f.count == s); - for (unsigned i = 0; i < s; ++i) - assert(ia[i] == static_cast(i+1)); - -#if TEST_STD_VER > 17 - static_assert(test_constexpr()); -#endif - - return 0; -} diff --git a/libcxx/utils/data/ignore_format.txt b/libcxx/utils/data/ignore_format.txt index 3e9728a..1777c1d 100644 --- a/libcxx/utils/data/ignore_format.txt +++ b/libcxx/utils/data/ignore_format.txt @@ -49,7 +49,6 @@ libcxx/include/__algorithm/fill.h libcxx/include/__algorithm/fill_n.h libcxx/include/__algorithm/find_end.h libcxx/include/__algorithm/find_first_of.h -libcxx/include/__algorithm/for_each.h libcxx/include/__algorithm/for_each_n.h libcxx/include/__algorithm/generate.h libcxx/include/__algorithm/generate_n.h -- 2.7.4