[gcc r17-3419] libstdc++: optimize std::for_each for segmented iterators

[Yuao Ma]

https://gcc.gnu.org/g:2d11dfb0e2edd9e3ea451987b844c76b12bb09af

commit r17-3419-g2d11dfb0e2edd9e3ea451987b844c76b12bb09af
Author: Yuao Ma <c8ef@outlook.com>
Date:   Mon Aug 3 23:05:04 2026 +0800

    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.

Diff:
---
 libstdc++-v3/include/bits/stl_algo.h               | 33 ++++++++++++++++++++--
 .../performance/25_algorithms/for_each.cc          | 32 +++++++++++++++++++++
 2 files changed, 63 insertions(+), 2 deletions(-)

diff --git a/libstdc++-v3/include/bits/stl_algo.h b/libstdc++-v3/include/bits/stl_algo.h
index 800c176cd5bd..6a9e133ce955 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 000000000000..37af5ab59816
--- /dev/null
+++ b/libstdc++-v3/testsuite/performance/25_algorithms/for_each.cc
@@ -0,0 +1,32 @@
+#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::min<T>(100, std::max<T>(x, 10)); });
+  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);
+}