Re: [PATCH] libstdc++: optimize std::for_each for segmented iterators
Yuao Ma <[email protected]> Mon, 3 Aug 2026 23:14:22 +0800
| Newsgroups | gmane.comp.gcc.patches,gmane.comp.gcc.libstdc++.devel |
|---|---|
| Message-ID | <CA+m0iR_rGvaCbBrxyvuypEwa2d7Hv5Ve0ONvE1thp74mDLGJyw@mail.gmail.com> |
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 >> > >>