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
