Re: [PATCH] libstdc++: optimize std::for_each for segmented iterators

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.
---
 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