On Thu, Aug 20, 2026 at 9:00 PM Yuao Ma <[email protected]> wrote: > > On Thu, Aug 20, 2026 at 8:45 PM Jonathan Wakely <[email protected]> wrote: > > > > On Thu, 20 Aug 2026 at 12:59, Yuao Ma <[email protected]> wrote: > > > > > > On Thu, Aug 20, 2026 at 6:31 PM Jonathan Wakely <[email protected]> > > > wrote: > > > > > > > > On Thu, 20 Aug 2026 at 11:30, Jonathan Wakely <[email protected]> > > > > wrote: > > > > > > > > > > On Wed, 19 Aug 2026 at 17:23, Yuao Ma <[email protected]> wrote: > > > > > > > > > > > > Hi! > > > > > > > > > > > > Similar to std::for_each, this patch optimizes ranges::for_each for > > > > > > segmented iterators. > > > > > > > > > > If I understand correctly, this will break cases that require > > > > > std::invoke to invoke the function object, e.g. > > > > > > > > > > ranges::for_each(r, &T::f); > > > > > > > > A more concrete example: > > > > > > > > struct T { void f() { } }; > > > > std::deque<T> d; > > > > ranges::for_each(d, &T::f); > > > > > > > > deque's _S_for_each_segment just uses __func without std::invoke, > > > > doesn't it? > > > > > > > > > > Actually this will compile and run without error, and my local check > > > verifies this. I think the reason is that what we passed to the __func > > > is the internal lambda of the std::__for_each_segmented, rather than > > > the &T::f. The only place which will be called with member function is > > > correctly handled with std::invoke. > > > > Ah yes! When ranges::__for_each stops recursing and calls the 'else' > > branch it uses std::__invoke. Nice. > > > > Is there any benefit to passing __f and __proj separately, using two > > parameter slots? > > > > ranges::__for_each could take a single __f with no proj, and then just > > call __f(*__first) in its else branch. And ranges::for_each could pass > > it a lambda which invokes proj and f. That would mean an additional > > indirection, but only passing one parameter. Maybe it's not an > > improvement. > > > > Indeed, I think the main reason here is for it to be straightforward. > Like for_each_fn itself have _Fun and _Proj. > > BTW, do you think this helper function belongs to namespace __detail > or the current location is already good? >
And after the merge of the check performance patch this ranges::for_each patch is slightly rebased. > > > > > > > > > > > > > > > > > > > > > > Fully tested on x86_64-linux with no regressions. > > > > > > > > > > > > Using the newly added benchmark, it shows a 3x improvement when > > > > > > using > > > > > > ranges::for_each with std::deque. > > > > > > > > > > > > === Wed Aug 19 03:28:22 PM UTC 2026 === > > > > > > for_each.cc std::for_each vector<int> 2r 1u 0s > > > > > > 0mem 0pf > > > > > > for_each.cc std::for_each deque<int> 2r 2u 0s > > > > > > 0mem 0pf > > > > > > for_each.cc std::for_each list<int> 13r 14u 0s > > > > > > 0mem 0pf > > > > > > for_each.cc std::ranges::for_each vector<int> 2r > > > > > > 2u > > > > > > 0s 0mem 0pf > > > > > > for_each.cc std::ranges::for_each deque<int> 6r > > > > > > 5u > > > > > > 0s 0mem 0pf > > > > > > for_each.cc std::ranges::for_each list<int> 13r 14u > > > > > > 0s 0mem 0pf > > > > > > === Wed Aug 19 04:09:51 PM UTC 2026 === > > > > > > for_each.cc std::for_each vector<int> 2r 1u 0s > > > > > > 0mem 0pf > > > > > > for_each.cc std::for_each deque<int> 2r 2u 0s > > > > > > 0mem 0pf > > > > > > for_each.cc std::for_each list<int> 13r 14u 0s > > > > > > 0mem 0pf > > > > > > for_each.cc std::ranges::for_each vector<int> 2r > > > > > > 2u > > > > > > 0s 0mem 0pf > > > > > > for_each.cc std::ranges::for_each deque<int> 2r > > > > > > 1u > > > > > > 0s 0mem 0pf > > > > > > for_each.cc std::ranges::for_each list<int> 13r 14u > > > > > > 0s 0mem 0pf > > > > > > > > > > > > Please take a look when you are available, thanks! > > > > > > > > > > > > Note: after preparing this patch I found the -std=gnu++11 in the > > > > > > check > > > > > > performance script based on Jonathan's guidance. I can prepare a > > > > > > patch > > > > > > for this tomorrow and get rid of the STD in the benchmark. > > > > > > > > > > > > Yuao > > > > > > > > >
From db7b1893a0d55ee018bc303d3967497eebbbb3ef Mon Sep 17 00:00:00 2001 From: Yuao Ma <[email protected]> Date: Fri, 21 Aug 2026 22:31:19 +0800 Subject: [PATCH] libstdc++: optimize ranges::for_each for segmented iterators Similar to r17-3419-g2d11dfb0e2edd9, we can optimize std::for_each for segemented iterators. libstdc++-v3/ChangeLog: * include/bits/ranges_algo.h (ranges::__for_each): Add segemented iterators logic. Split out naive for-loop from ... (__for_each_fn::operator()): ... here. * testsuite/performance/25_algorithms/for_each.cc: Add benchmark for ranges::for_each. --- libstdc++-v3/include/bits/ranges_algo.h | 33 +++++++++++++++++-- .../performance/25_algorithms/for_each.cc | 22 ++++++++++++- 2 files changed, 51 insertions(+), 4 deletions(-) diff --git a/libstdc++-v3/include/bits/ranges_algo.h b/libstdc++-v3/include/bits/ranges_algo.h index 4330d3e70b8..f4c70dc7029 100644 --- a/libstdc++-v3/include/bits/ranges_algo.h +++ b/libstdc++-v3/include/bits/ranges_algo.h @@ -211,6 +211,33 @@ namespace ranges template<typename _Iter, typename _Fp> using for_each_result = in_fun_result<_Iter, _Fp>; + // Apply __f to the result of applying __proj to each element in + // [__first, __last). + // Dispatches to __for_each_segment for segmented iterators + // (e.g. deque::iterator). + // Returns an iterator equal to __last. + template<typename _InputIterator, typename _Sentinel, typename _Function, + typename _Proj> + constexpr _InputIterator + __for_each(_InputIterator __first, _Sentinel __last, _Function&& __f, + _Proj& __proj) + { + if constexpr (__segmented_iterator<_InputIterator> + && same_as<_InputIterator, _Sentinel>) + { + std::__for_each_segment(__first, __last, + [&](auto __lfirst, auto __llast) + { return ranges::__for_each(__lfirst, __llast, __f, __proj); }); + return __last; + } + else + { + for (; __first != __last; ++__first) + std::__invoke(__f, std::__invoke(__proj, *__first)); + return __first; + } + } + struct __for_each_fn { template<input_iterator _Iter, sentinel_for<_Iter> _Sent, @@ -219,9 +246,9 @@ namespace ranges constexpr for_each_result<_Iter, _Fun> operator()(_Iter __first, _Sent __last, _Fun __f, _Proj __proj = {}) const { - for (; __first != __last; ++__first) - std::__invoke(__f, std::__invoke(__proj, *__first)); - return { std::move(__first), std::move(__f) }; + auto __end = ranges::__for_each(std::move(__first), std::move(__last), __f, + __proj); + return { std::move(__end), std::move(__f) }; } template<input_range _Range, typename _Proj = identity, diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc b/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc index 37af5ab5981..65b13be6c21 100644 --- a/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc +++ b/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc @@ -15,7 +15,20 @@ void bench_seq(const char* label, __gnu_test::time_counter& time, start_counters(time, resource); for (int i = 0; i < 20000; ++i) std::for_each(c.begin(), c.end(), - [](T& x) { x = std::min<T>(100, std::max<T>(x, 10)); }); + [](T& x) { x = std::clamp<T>(x, 10, 100); }); + stop_counters(time, resource); + report_performance(__FILE__, label, time, resource); + clear_counters(time, resource); +} + +template <typename Container> +void bench_seq_ranges(const char* label, __gnu_test::time_counter& time, + __gnu_test::resource_counter& resource) { + using T = typename Container::value_type; + Container c(size, 1); + start_counters(time, resource); + for (int i = 0; i < 20000; ++i) + std::ranges::for_each(c, [](T& x) { x = std::clamp<T>(x, 10, 100); }); stop_counters(time, resource); report_performance(__FILE__, label, time, resource); clear_counters(time, resource); @@ -29,4 +42,11 @@ int main() { bench_seq<std::vector<int>>("std::for_each vector<int>", time, resource); bench_seq<std::deque<int>>("std::for_each deque<int>", time, resource); bench_seq<std::list<int>>("std::for_each list<int>", time, resource); + + bench_seq_ranges<std::vector<int>>("std::ranges::for_each vector<int>", time, + resource); + bench_seq_ranges<std::deque<int>>("std::ranges::for_each deque<int>", time, + resource); + bench_seq_ranges<std::list<int>>("std::ranges::for_each list<int>", time, + resource); } -- 2.54.0
