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

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)

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
>