[ping][PATCH] libstdc++: optimize ranges::for_each for segmented iterators
Yuao Ma
addr2line@gmail.com
Sun Aug 30 13:24:15 GMT 2026
On Sun, Aug 23, 2026 at 7:22 PM Yuao Ma <addr2line@gmail.com> wrote:
>
> On Fri, Aug 21, 2026 at 10:46 PM Jonathan Wakely <jwakely@redhat.com> wrote:
> >
> > On Fri, 21 Aug 2026 at 15:33, Yuao Ma <addr2line@gmail.com> wrote:
> > >
> > > On Thu, Aug 20, 2026 at 9:00 PM Yuao Ma <addr2line@gmail.com> wrote:
> > > >
> > > > On Thu, Aug 20, 2026 at 8:45 PM Jonathan Wakely <jwakely@redhat.com> wrote:
> > > > >
> > > > > On Thu, 20 Aug 2026 at 12:59, Yuao Ma <addr2line@gmail.com> wrote:
> > > > > >
> > > > > > On Thu, Aug 20, 2026 at 6:31 PM Jonathan Wakely <jwakely@redhat.com> wrote:
> > > > > > >
> > > > > > > On Thu, 20 Aug 2026 at 11:30, Jonathan Wakely <jwakely@redhat.com> wrote:
> > > > > > > >
> > > > > > > > On Wed, 19 Aug 2026 at 17:23, Yuao Ma <addr2line@gmail.com> wrote:
> > > > > > > > >
> > > > > > > > > Hi!
> > > > > > > > >
> > > > > > > > > Similar to std::for_each, this patch optimizes ranges::for_each for
> > > > > > > > > segmented iterators.
> > > > > > > >
> > > > > > > > If I understand correctly, this will break cases that require
> > > > > > > > std::invoke to invoke the function object, e.g.
> > > > > > > >
> > > > > > > > ranges::for_each(r, &T::f);
> > > > > > >
> > > > > > > A more concrete example:
> > > > > > >
> > > > > > > struct T { void f() { } };
> > > > > > > std::deque<T> d;
> > > > > > > ranges::for_each(d, &T::f);
> > > > > > >
> > > > > > > deque's _S_for_each_segment just uses __func without std::invoke, doesn't it?
> > > > > > >
> > > > > >
> > > > > > Actually this will compile and run without error, and my local check
> > > > > > verifies this. I think the reason is that what we passed to the __func
> > > > > > is the internal lambda of the std::__for_each_segmented, rather than
> > > > > > the &T::f. The only place which will be called with member function is
> > > > > > correctly handled with std::invoke.
> > > > >
> > > > > Ah yes! When ranges::__for_each stops recursing and calls the 'else'
> > > > > branch it uses std::__invoke. Nice.
> > > > >
> > > > > Is there any benefit to passing __f and __proj separately, using two
> > > > > parameter slots?
> > > > >
> > > > > ranges::__for_each could take a single __f with no proj, and then just
> > > > > call __f(*__first) in its else branch. And ranges::for_each could pass
> > > > > it a lambda which invokes proj and f. That would mean an additional
> > > > > indirection, but only passing one parameter. Maybe it's not an
> > > > > improvement.
> > > > >
> > > >
> > > > Indeed, I think the main reason here is for it to be straightforward.
> > > > Like for_each_fn itself have _Fun and _Proj.
> > > >
> > > > BTW, do you think this helper function belongs to namespace __detail
> > > > or the current location is already good?
> > > >
> > >
> > > And after the merge of the check performance patch this
> > > ranges::for_each patch is slightly rebased.
> >
> > OK for trunk.
> >
>
> Thanks for the review! Still I'm wondering about the location of the
> __for_each helper, do you think it would be better if it belongs to
> namespace __detail, like the following?
>
Hi Jonathan, would you mind revisiting this patch regarding this question?
> namespace ranges
> {
> namespace __detail
> {
> // ...
>
> // Apply __f to the result of applying __proj 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 _Sentinel, typename _Function,
> typename _Proj>
> constexpr _InputIterator
> __for_each(_InputIterator __first, _Sentinel __last, _Function&& __f,
> _Proj& __proj)
> {
> if constexpr (__segmented_iterator<_InputIterator>
> && same_as<_InputIterator, _Sentinel>)
> {
> std::__for_each_segment(__first, __last,
> [&](auto __lfirst, auto __llast)
> { return ranges::__detail::__for_each(__lfirst, __llast, __f, __proj); });
> return __last;
> }
> else
> {
> for (; __first != __last; ++__first)
> std::__invoke(__f, std::__invoke(__proj, *__first));
> return __first;
> }
> }
> } // namespace __detail
>
> > >
> > > > >
> > > > > >
> > > > > > > >
> > > > > > > > >
> > > > > > > > > Fully tested on x86_64-linux with no regressions.
> > > > > > > > >
> > > > > > > > > Using the newly added benchmark, it shows a 3x improvement when using
> > > > > > > > > ranges::for_each with std::deque.
> > > > > > > > >
> > > > > > > > > === Wed Aug 19 03:28:22 PM 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 14u 0s
> > > > > > > > > 0mem 0pf
> > > > > > > > > for_each.cc std::ranges::for_each vector<int> 2r 2u
> > > > > > > > > 0s 0mem 0pf
> > > > > > > > > for_each.cc std::ranges::for_each deque<int> 6r 5u
> > > > > > > > > 0s 0mem 0pf
> > > > > > > > > for_each.cc std::ranges::for_each list<int> 13r 14u
> > > > > > > > > 0s 0mem 0pf
> > > > > > > > > === Wed Aug 19 04:09:51 PM 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 14u 0s
> > > > > > > > > 0mem 0pf
> > > > > > > > > for_each.cc std::ranges::for_each vector<int> 2r 2u
> > > > > > > > > 0s 0mem 0pf
> > > > > > > > > for_each.cc std::ranges::for_each deque<int> 2r 1u
> > > > > > > > > 0s 0mem 0pf
> > > > > > > > > for_each.cc std::ranges::for_each list<int> 13r 14u
> > > > > > > > > 0s 0mem 0pf
> > > > > > > > >
> > > > > > > > > Please take a look when you are available, thanks!
> > > > > > > > >
> > > > > > > > > Note: after preparing this patch I found the -std=gnu++11 in the check
> > > > > > > > > performance script based on Jonathan's guidance. I can prepare a patch
> > > > > > > > > for this tomorrow and get rid of the STD in the benchmark.
> > > > > > > > >
> > > > > > > > > Yuao
> > > > > > >
> > > > > >
> > > > >
> >
More information about the Libstdc++
mailing list