On Tue, Aug 4, 2026 at 11:13 AM Patrick Palka <[email protected]> wrote:
>
> On Tue, 4 Aug 2026, Yuao Ma wrote:
>
> > On Tue, Aug 4, 2026 at 1:00 AM Patrick Palka <[email protected]> wrote:
> > >
> > > On Mon, 3 Aug 2026, 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.
> > >
> > > Ah good point. Alternatively I think we could pass std::ref(__f)
> > > in the recursive for_each calls. I'm not sure which approach is
> > > preferable.
> > >
> >
> > Indeed std::ref(__f) will work with stateful functor. I came up with
> > another reason: the return value. The std::for_each returns __f
> > whereas __for_each returns the _last, which might be useful for
> > adoption by some algorithms.
> >
> > > > 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.
> > >
> > > Makes sense.
> > >
> > > >
> > > > > > 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
> > > > > >
> > > > >
> > > >
> >
> >
> > 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.
>
> LGTM
>
Thanks for the review!
Hi Jonathan, would you mind also taking a look at this patch? Thanks!
> > ---
> > 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.
> > +#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
> > +
> > +#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
> >
