On Wed, Aug 19, 2026 at 7:38 PM Jonathan Wakely <[email protected]> wrote:
>
> On Mon, 03 Aug 2026 at 23:11 +0800, Yuao Ma wrote:
> >On Mon, Aug 3, 2026 at 9:22 PM Patrick Palka <[email protected]> wrote:
> >>
> >> On Sun, 2 Aug 2026, Yuao Ma wrote:
> >>
> >> > Hi!
> >> >
> >> > Similar to ranges::distance, this patch optimizes std::for_each for
> >> > segmented iterators.
> >>
> >> Thanks for working on this.
> >>
> >> >
> >> > Fully tested on x86_64-linux with no regressions.
> >> >
> >> > Using the newly added benchmark, it shows a 3x improvement when using
> >> > std::for_each with std::deque.
> >> >
> >> > === Sun Aug 2 09:30:52 AM UTC 2026 ===
> >> > for_each.cc std::for_each vector<int> 2r 1u 0s
> >> > 0mem 0pf
> >> > for_each.cc std::for_each deque<int> 6r 6u 0s
> >> > 0mem 0pf
> >> > for_each.cc std::for_each list<int> 13r 13u 0s
> >> > 0mem 0pf
> >> > === Sun Aug 2 09:31:08 AM 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 13u 0s
> >> > 0mem 0pf
> >>
> >> Interesting that even for_each benefits from this! So this assumes
> >> it's significantly cheaper to iterate over the inner/local iterators
> >> than over the segmented iterators in general, makes sense.
> >>
> >> >
> >> > Please take a look when you are available, thanks!
> >> >
> >> > Yuao
> >> >
> >>
> >> > Subject: [PATCH] libstdc++: optimize std::for_each for segmented
> >> > iterators
> >> >
> >> > Similar to r17-2859-g15505d012872dd, we can optimize std::for_each for
> >> > segemented iterators.
> >> >
> >> > libstdc++-v3/ChangeLog:
> >> >
> >> > * include/bits/stl_algo.h (__for_each): Add segemented
> >> > iterators logic. Split out naive for-loop from ...
> >> > (for_each): ... here.
> >> > * testsuite/performance/25_algorithms/for_each.cc: New test.
> >> > ---
> >> > libstdc++-v3/include/bits/stl_algo.h | 29 ++++++++++++++--
> >> > .../performance/25_algorithms/for_each.cc | 34 +++++++++++++++++++
> >> > 2 files changed, 61 insertions(+), 2 deletions(-)
> >> > create mode 100644
> >> > libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc
> >> >
> >> > diff --git a/libstdc++-v3/include/bits/stl_algo.h
> >> > b/libstdc++-v3/include/bits/stl_algo.h
> >> > index 800c176cd5b..54d73ae8c62 100644
> >> > --- a/libstdc++-v3/include/bits/stl_algo.h
> >> > +++ b/libstdc++-v3/include/bits/stl_algo.h
> >> > @@ -132,6 +132,32 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> >> > return __first;
> >> > }
> >> >
> >> > + /// Apply __f 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 _Function>
> >> > + _GLIBCXX20_CONSTEXPR
> >> > + _InputIterator
> >> > + __for_each(_InputIterator __first, _InputIterator __last,
> >> > _Function& __f)
> >> > + {
> >> > +#if __cplusplus >= 201703L
> >> > + if constexpr (__enable_for_each_segment<_InputIterator>)
> >> > + {
> >> > + std::__for_each_segment(__first, __last,
> >> > + [&](auto __lfirst, auto __llast)
> >> > + { return std::__for_each(__lfirst, __llast, __f); });
> >> > + return __last;
> >> > + }
> >> > + else
> >> > +#endif // C++17
> >>
> >> I think we could enable this optimization as far back as C++11 if we
> >> use a lambda template here (and #pragma GCC diagnostic ignored etc):
> >>
> >> [&]<template _It>(_It __lfirst, _It __llast)
> >>
> >
> >Thanks for the suggestions. I use this approach in the new patch.
> >
> >> Besides that, looks good.
> >>
> >> (GCC and Clang accept lambda templates even in C++98 mode so in theory
> >> we could enable the optimization unconditionally if we resort to using
> >> C++98 compatible SFINAE, but I don't think it's worth it personally.)
> >>
> >> > + {
> >> > + for (; __first != __last; ++__first)
> >> > + __f(*__first);
> >> > + return __first;
> >> > + }
> >> > + }
> >> > +
> >> > // set_difference
> >> > // set_intersection
> >> > // set_symmetric_difference
> >> > @@ -3813,8 +3839,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> >> > // concept requirements
> >> > __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
> >> > __glibcxx_requires_valid_range(__first, __last);
> >> > - for (; __first != __last; ++__first)
> >> > - __f(*__first);
> >> > + std::__for_each(__first, __last, __f);
> >>
> >> I guess you're factoring this out to use elsewhere, e.g. ranges::for_each?
> >>
> >
> >Hmm, it is mostly for support the stateful functor passed in the
> >std::for_each, in which case we really need the parameter to be a
> >reference type. To use it for ranges::for_each at least it needs two
> >refactor: for function parameter it needs _Sentinel and _Proj, for the
> >function body it needs std::invoke. Not sure how to correctly includes
> >these given the current header structure, I think I will have a
> >standalone optimization for ranges::for_each, and let other algorithms
> >that could benefit from segmented iterators depend on either of them.
> >
> >> > return __f; // N.B. [alg.foreach] says std::move(f) but it's
> >> > redundant.
> >> > }
> >> >
> >> > diff --git
> >> > a/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc
> >> > b/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc
> >> > new file mode 100644
> >> > index 00000000000..22981eb9b64
> >> > --- /dev/null
> >> > +++ b/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc
> >> > @@ -0,0 +1,34 @@
> >> > +// STD=gnu++17
> >> > +
> >> > +#include <testsuite_performance.h>
> >> > +
> >> > +#include <algorithm>
> >> > +#include <deque>
> >> > +#include <list>
> >> > +#include <vector>
> >> > +
> >> > +const std::size_t size = 8192;
> >> > +
> >> > +template <typename Container>
> >> > +void bench_seq(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::for_each(c.begin(), c.end(),
> >> > + [](T& x) { x = std::clamp<T>(x, 10, 100); });
> >> > + stop_counters(time, resource);
> >> > + report_performance(__FILE__, label, time, resource);
> >> > + clear_counters(time, resource);
> >> > +}
> >> > +
> >> > +int main() {
> >> > + using namespace __gnu_test;
> >> > + time_counter time;
> >> > + resource_counter resource;
> >> > +
> >> > + 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);
> >> > +}
> >> > --
> >> > 2.54.0
> >> >
> >>
>
> >From a8dc4e6bf0304ccf27b408a50ead08d3aff21d66 Mon Sep 17 00:00:00 2001
> >From: Yuao Ma <[email protected]>
> >Date: Mon, 3 Aug 2026 23:05:04 +0800
> >Subject: [PATCH] libstdc++: optimize std::for_each for segmented iterators
> >
> >Similar to r17-2859-g15505d012872dd, we can optimize std::for_each for
> >segemented iterators.
> >
> >libstdc++-v3/ChangeLog:
> >
> > * include/bits/stl_algo.h (__for_each): Add segemented
> > iterators logic. Split out naive for-loop from ...
> > (for_each): ... here.
> > * testsuite/performance/25_algorithms/for_each.cc: New test.
>
> OK for trunk with one change requested below ...
>
> >---
> > libstdc++-v3/include/bits/stl_algo.h | 33 ++++++++++++++++--
> > .../performance/25_algorithms/for_each.cc | 34 +++++++++++++++++++
> > 2 files changed, 65 insertions(+), 2 deletions(-)
> > create mode 100644
> > libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc
> >
> >diff --git a/libstdc++-v3/include/bits/stl_algo.h
> >b/libstdc++-v3/include/bits/stl_algo.h
> >index 800c176cd5b..3cd204dd871 100644
> >--- a/libstdc++-v3/include/bits/stl_algo.h
> >+++ b/libstdc++-v3/include/bits/stl_algo.h
> >@@ -132,6 +132,36 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
> > return __first;
> > }
> >
> >+ /// Apply __f to each element in [__first, __last)
> >+ /// Dispatches to __for_each_segment for segmented iterators
> >+ /// (e.g. deque::iterator).
> >+ /// Returns an iterator equal to __last.
>
> Just "//" for these comments please, we don't need Doxygen to process
> this internal implementation details.
>
Fixed.
> >+#pragma GCC diagnostic push
> >+#pragma GCC diagnostic ignored "-Wc++17-extensions" // if constexpr
> >+#pragma GCC diagnostic ignored "-Wc++20-extensions" // template lambda
> >+ template<typename _InputIterator, typename _Function>
> >+ _GLIBCXX20_CONSTEXPR
> >+ _InputIterator
> >+ __for_each(_InputIterator __first, _InputIterator __last, _Function&
> >__f)
> >+ {
> >+#if __cplusplus >= 201103L
> >+ if constexpr (__enable_for_each_segment<_InputIterator>)
> >+ {
> >+ std::__for_each_segment(__first, __last,
> >+ [&]<typename _Iter>(_Iter __lfirst, _Iter __llast)
> >+ { return std::__for_each(__lfirst, __llast, __f); });
> >+ return __last;
> >+ }
> >+ else
> >+#endif // C++11
> >+ {
> >+ for (; __first != __last; ++__first)
> >+ __f(*__first);
> >+ return __first;
> >+ }
> >+ }
> >+#pragma GCC diagnostic pop
> >+
> > // set_difference
> > // set_intersection
> > // set_symmetric_difference
> >@@ -3813,8 +3843,7 @@ _GLIBCXX_BEGIN_NAMESPACE_ALGO
> > // concept requirements
> > __glibcxx_function_requires(_InputIteratorConcept<_InputIterator>)
> > __glibcxx_requires_valid_range(__first, __last);
> >- for (; __first != __last; ++__first)
> >- __f(*__first);
> >+ std::__for_each(__first, __last, __f);
> > return __f; // N.B. [alg.foreach] says std::move(f) but it's
> > redundant.
> > }
> >
> >diff --git a/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc
> >b/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc
> >new file mode 100644
> >index 00000000000..22981eb9b64
> >--- /dev/null
> >+++ b/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc
> >@@ -0,0 +1,34 @@
> >+// STD=gnu++17
>
> This is for std::clamp, right?
>
> We should probably remove the -std=gnu++11 in
> scripts/check_performance and just use the default -std option
> (currently gnu++20). I think the -std=gnu++11 was added when the
> default was still -std=gnu++98, so that we could test "new" C++11
> features. That can be a separate patch though.
>
I replaced the std::clamp with min/max, the STD is also removed.
Pushed as r17-3419-g2d11dfb0e2edd9, thanks for the review!
> >+
> >+#include <testsuite_performance.h>
> >+
> >+#include <algorithm>
> >+#include <deque>
> >+#include <list>
> >+#include <vector>
> >+
> >+const std::size_t size = 8192;
> >+
> >+template <typename Container>
> >+void bench_seq(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::for_each(c.begin(), c.end(),
> >+ [](T& x) { x = std::clamp<T>(x, 10, 100); });
> >+ stop_counters(time, resource);
> >+ report_performance(__FILE__, label, time, resource);
> >+ clear_counters(time, resource);
> >+}
> >+
> >+int main() {
> >+ using namespace __gnu_test;
> >+ time_counter time;
> >+ resource_counter resource;
> >+
> >+ 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);
> >+}
> >--
> >2.54.0
> >
>
