[PATCH] libstdc++: optimize ranges::for_each for segmented iterators
Yuao Ma
addr2line@gmail.com
Fri Aug 21 14:33:29 GMT 2026
On Thu, Aug 20, 2026 at 9:00 PM Yuao Ma <addr2line@gmail.com> wrote:
>
> On Thu, Aug 20, 2026 at 8:45 PM Jonathan Wakely <jwakely@redhat.com> wrote:
> >
> > On Thu, 20 Aug 2026 at 12:59, Yuao Ma <addr2line@gmail.com> wrote:
> > >
> > > On Thu, Aug 20, 2026 at 6:31 PM Jonathan Wakely <jwakely@redhat.com> wrote:
> > > >
> > > > On Thu, 20 Aug 2026 at 11:30, Jonathan Wakely <jwakely@redhat.com> wrote:
> > > > >
> > > > > On Wed, 19 Aug 2026 at 17:23, Yuao Ma <addr2line@gmail.com> 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
> > > >
> > >
> >
-------------- next part --------------
From db7b1893a0d55ee018bc303d3967497eebbbb3ef Mon Sep 17 00:00:00 2001
From: Yuao Ma <c8ef@outlook.com>
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
More information about the Libstdc++
mailing list