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

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.

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

>+
>+#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
>