On Mon, Aug 3, 2026 at 9:56 PM Tomasz Kaminski <[email protected]> wrote:
>
>
>
> On Mon, Aug 3, 2026 at 3: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.
>
> Out of curiostity, do you see similar benefit for join_view or concat_view
> over vectors?
Interesting question, and the result is also interesting. In theory
join_view should benefit from segmented iterators. But when I actually
tested them, it turned out that for join_view we need -O3 to actually
benefit from the optimization, but for plain containers like
std::deque -O2 is enough. I suspect it has something to do with the
vectorizers cost model.
>>
>> >
>> > === 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)
>>
>> 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?
>>
>> > 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
>> >
>>
